Calculate height of binary tree | Iterative & Recursive

Write an efficient algorithm to compute the height of binary tree. The height or depth of a tree is number of edges or nodes on longest path from root node to leaf node.

 
The program should consider number of nodes in the longest path. For example, height of an empty tree is 0 and height of tree with only one node is 1.


 

The idea is to traverse the tree in post-order fashion and calculate the height of left and right subtree. The height of the subtree rooted at any node will be equal to maximum height of its left and right subtree plus one. We recursively apply this property to all tree nodes in bottom-up manner (post-order fashion) and return maximum height of the subtree rooted at that node.

 
C++ implementation –
 

Download   Run Complete Code

 


 
Iterative solution –
 
In iterative version, we perform level order traversal of the tree. The height of the tree is equal to number of levels in the tree.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of both recursive and iterative solution is O(n).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz