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).

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of
abhijit jena