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.