Jul 312012
 

 Given a Binary Tree, write code to calculate the height of the tree. Height of the binary Tree is the total number of levels in the Binary Tree.

For example, Height of a NULL tree is 0. If a tree has only 1 node (root node) then the height is 1 and so on … height of tree on the right is 5.

Question can also be asked to find the depth (rather than height of the tree), both are same.

Solution:

Most of the Binary tree algorithms are better written recursively be it the traversal algorithms or counting number of leaf nodes  or any other tree algorithm.

In this algorithm also we will be using recursion to solve the problem, but please note that recursion comes with its side-effects.

Algorithm:

1. If root is NULL then return zero
2. Calculate the height of LEFT sub-tree recursively
3. Calculate the height of RIGHT sub-tree recursively
4. Compute maximum of step 2 & 3 and add 1 to it and return the value.

Code:

    /** Function to compute the height of the tree.
     *  root is a pointer to the root of the tree
     */
    int height(Node* root) 
    {
       if (root == NULL) 
           return 0;

       // Compute height of each tree
       int heightLeft = height(root->lptr);
       int heightRight = height(root->rptr);

       /* use the larger one */
       if (heightLeft > heightRight) 
           return(heightLeft + 1);
       else 
           return(heightRight + 1);
    }

Let me know your comments.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)