Height of a Binary tree : Recursive and Iterative Approach

Problem : Given a Binary Tree , find the height of the tree. 

 Example:

Height of above Tree = 3

Explanation:

 Height of a binary tree is  the number of nodes along the longest path from the root node down to the farthest leaf node. The Height of the empty tree is 0, the Height of the tree in the above example is 3

Solution : 

There can be two approach to solve this problem : 

1. Recursive : using recursive calls to find heights of left and right subtress 

2. Iterative : using level order traversal 

Let us have a look at both the approaches one by one : 

A. Recursive Solution :  

   1. if the root ==null , return 0

Else : perform 2 -->4

   2. find height of left subtree , say LH 

   3. find height of right subtree , say RH

   4. if LH >RH, return LH +1 , else return RH+1

B. Iterative Solution :

 Do a level order traversal, increment height at each level. Return height at the end.

Implementation : 

Following are the java implementations for both solutions 

A. RECURSIVE :

 int height(Node root){

        

         if(root==null) return 0;

       

       else{

            int lh= height(root.left);

            int rh= height(root.right);

       

       if(lh>rh) return lh+1;

       else return rh+1;

       }

          

    }

B. ITERATIVE :

 int height(Node root)

    {

         if(root==null) return 0;

       Node node=root;

       int height=0;

       Queue<Node> q= new LinkedList<Node>();

       q.add(node);

       

       while(true){

            // nodeCount (queue size) indicates number of nodes

            // at current lelvel.

            int nodeCount = q.size();

            if (nodeCount == 0) {

                return height;

            }

            height++;

            // Dequeue all nodes of current level and Enqueue all

            // nodes of next level

            while (nodeCount > 0) {

                Node newnode = q.peek();

                q.remove();

                if (newnode.left != null) {

                    q.add(newnode.left);

                }

                if (newnode.right != null) {

                    q.add(newnode.right);

                }

                nodeCount--;

            }

        }

           

           

           

       }

    

________________________________________________________________________________

REFERENCES : 

http://cslibrary.stanford.edu/110/BinaryTrees.html

https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree