Height of a Binary Tree

By | October 23, 2015

Height of a Binary Tree

Given a Binary Tree, we need to print the height of the tree (or the maximum depth).

Example:

             80                 
           /     \        
          60      110     
         /  \    /       
       35   40  85   
      /  \
     64   72

For the tree shown above, the output should be 4.

height of tree = max { height of left subtree ,  height of right subtree } + 1

height() is a recursive function that return the height of the tree

Finding the Depth (or height) of a Binary Tree solution:

Video Explanation:

Algorithm to find height of a Binary Tree :

  1. If the root is null ( the tree is empty) then return 0.
  2. Else
    1. Find the height of the left subtree
      height(root->left).
    2. Find the size of the right subtree
      height(root->right).
    3. Return max(height(root->left) + height(root->right)) + 1

Depth of Binary Tree solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*Structure for each node of the tree*/
struct node
{
   int data;
   node *right,*left;
};


/*Function that allocates memory for
each new node and initialises it*/
node * newNode(int data)
{
   node *temp=new node;
   temp->data=data;
   temp->left=NULL;
   temp->right=NULL;
   
   return temp;
}

/*The function that returns the number of nodes
int the tree*/
int height(node *root)
{
   /*Base case when the tree is NULL*/
   if(!root)
      return 0;
   /*Calculating recursively for left subtree
   right subtree and adding 1 to it for present node*/	
   return (max(height(root->left),height(root->right)) +1);
}

int main()
{
  /*        
  We are making the following tree
  	        80                 
            /    \        
          60      110     
         /  \    /       
       35   40  85 
      /  \
     64  72
  */
  node *root               = newNode(80);
  root->left               = newNode(60);
  root->right              = newNode(110);
  root->left->left         = newNode(35);
  root->left->right        = newNode(40);   
  root->right->left 	   = newNode(85);  
  root->left->left->left   = newNode(64);
  root->left->left->right  = newNode(72);
  
  
  cout<<"height of the tree is \n"<<height(root);  
  
  return 0;
}

Output:

height of the tree is 
4

Time Complexity: O(n) as all nodes are visited once