Find height of the Binary Tree

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 the below tree below is 5.

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.

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.

    /** 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);
    }