Tree – Implementation

Tree is the most widely used data structure for representing hierarchical data.

Tree Terminology

  • Root – The top node in a tree.
  • Child – A node directly connected to another node when moving away from the Root.
  • Parent – The converse notion of a child.
  • Siblings – Nodes with the same parent.
  • Descendant – A node reachable by repeated proceeding from parent to child.
  • Ancestor – A node reachable by repeated proceeding from child to parent.
  • Leaf – A node with no children.
  • Internal node – A node with at least one child
  • External node – A node with no children.
  • Degree – Number of sub trees of a node.
  • Edge – Connection between one node to another.
  • Path – A sequence of nodes and edges connecting a node with a descendant.
  • Level – The level of a node is defined by 1 + (the number of connections between the node and the root).
  • Height of node – The height of a node is the number of edges on the longest path between that node and a leaf.
  • Height of tree – The height of a tree is the height of its root node.
  • Depth – The depth of a node is the number of edges from the node to the tree’s root node.
  • Forest – A forest is a set of n ≥ 0 disjoint trees.

Applications

  • Represent Hierarchical data e.g File System, ancestory etc
  • Router algorithm
  • Easy Searching (Traversal)

Tree representation

1

//Have left and right node
//Have a value to store the value of the current node
class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int val){
        this.val = val;
    }
}
public static void main(String args[]){
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
}

Tree Traversal

  • Level Order (Breadth first) (Visit each level at a time)
    • All the nodes of the current level will be visited first before going to the next level
    • In the above tree, the level order will display the node values in this order
      • 1234567

1

To find the levels we need to get the height of the tree

//if root is null then return 0
//find the left and right node height by recursing
//find the max of left and right node 
public static int height(TreeNode root){
        if(root == null)
            return 0;
        int lheight = height(root.left) + 1;
        int rheight = height(root.right) + 1;
        int height = Math.max(lheight,rheight);
        return height;
    }

//get the level order
//decrease the level and recurse, return if the level is 1    
public static void bfs(TreeNode root, int level){
        if(root == null)
            return;
        if(level == 1)
            System.out.println(root.val);
        else{    
                bfs(root.left,level-1);
                bfs(root.right,level-1);
            }
    }
  • InOrder Traversal (left-root-right)
    • left node will be visited first and then the root node and then the right node
      • the above tree will return 4251637

1

    //left root right
    //4251637
    public static void inOrder(TreeNode root){
        if(root == null)
            return;
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }
  • PreOrder Traversal (root-left-right)
    • root node will be visited first and then the left node and then the right node
      • the above tree will return 1245367

1

//root left right
    //1245367
    public static void preOrder(TreeNode root){
        if(root == null)
            return;
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
  • PostOrder Traversal (left-right-root)
    • left node will be visited first and then the right node and then the root node
      • the above tree will return 4526731

1

//left right root
    //4526731
    public static void postOrder(TreeNode root){
        if(root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: