Finding Height of a Tree (Recursive and Iterative)

1. Recursive Method

                                                                                     Figure 1

We use the tree shown above as our example for better understanding and  height of the tree is 3.

The following are the steps to find the height recursively: 

1. Calculate the height of left subtree and right subtree.
2. Find the maximum height out of the two.
3. Add 1 (in order to include the root) to the value which gives the answer.

The below diagram gives clear explanation of the recursion:

                                   height('1') = max(height('2'), height('3')) + 1
                                                             = 2 + 1
                                                                 /    \
                                                               /         \
                                                             /             \
                                                           /                 \
                                                          /                     \
                                             height('1')                  height('3') = 1
                    = max(height('4'), height('5')) + 1
                              = 1 + 1   = 2
                                   /    \
                                 /        \
                               /            \
                             /                \
                           /                    \
            height('4') = 1     height('5') = 1

The following code shows the function which calculates the height recursively:

 int height(node * root)
{
    struct node * curr=root;
    if(curr==NULL)   //base condition
        return 0;
    else
        return(1+max(height(curr->left),height(curr->right)));
  }

For the complete code of recursive method visit here.

2. Iterative Method

In an Iterative method we can use level order to find the height of the tree. The idea is to traverse level by level.

The following are the steps to find the height iteratively:

1. Create a queue and push the root node into it.
2. Whenever we reach next level we add NULL node to the queue and increment 'height' variable.
3. Otherwise, we add left and right nodes of the current node into queue
4. Steps 2 and 3 are repeated until the queue is empty.

The following figure shows the steps in detail to calculate height for tree shown in Figure 1.

                                                                             Figure 2        

              

The following code shows the function which calculates the height iteratively:

 int heightoftree(struct node* root) {
 int h = 0;
 if (root == NULL)
  return 0;
 queue<node *> q;
 q.push(root);
 q.push(NULL);
 while (!q.empty()) {

  struct node *curr = q.front();
  q.pop();

  if (curr == NULL) {
   h++;
   if (!q.empty())
    q.push(NULL);
   cout << h << " ";
  }

  else {
   if (curr->left != NULL)
    q.push(curr->left);
   if (curr->right != NULL)
    q.push(curr->right);
  }

 }
 return h;
}

For the complete code of iterative method visit here.