Introduction - Tree

Definition

• A tree is a data structure that is commonly used in computer science to store and organize data in a hierarchical manner. At the top of the tree is a root node, which branches out into multiple child nodes. Each child node can then have its own child nodes, creating a tree-like structure.

• Special directed/undirected graph with N nodes and N-1 edges.

• Each node is can be reached from other nodes by some path.

• No cycles.

• Directed when you can only go from parent to child.

public class TreeNode {
  private int value;
  List<TreeNode> children;
}

• Usually tree problems are asked for binary tree.

Binary Tree

• It is a hierarchical structure consisting of nodes, where each node has at most two children. The children of a node are referred to as the left child and the right child.

public class BinaryTreeNode {
  private int data;
  private BinaryTreeNode left;
  private BinaryTreeNode right;

  public BinaryTreeNode(int data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  public int getData() {
    return this.data;
  }

  public void setData(int data) {
    this.data = data;
  }

  public BinaryTreeNode getLeft() {
    return this.left;
  }

  public void setLeft(BinaryTreeNode left) {
    this.left = left;
  }

  public BinaryTreeNode getRight() {
    return this.right;
  }

  public void setRight(BinaryTreeNode right) {
    this.right = right;
  }
}

• Special binary trees

  • Complete binary tree.

  • Full binary tree.

    • No of nodes in a full binary tree

    • Height of full binary tree - log (number of nodes)

    • 2^H - 1 = total nodes

    • H = log (total nodes)

  • Binary search tree (Explained in another blog)

  • Balanced binary tree (AVL , Red black)

Operations on Binary Tree or detailed explanation of Binary and Binary Search Tree will be in next blog. Keep in touch.

So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.

Thank you, Have a nice day !!