Calculate the height of a binary tree – Iterative and Recursive

Google Translate Icon

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

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

Practice this problem

Recursive Solution

The idea is to traverse the tree in a postorder fashion and calculate the height of the left and right subtree. The height of a subtree rooted at any node will be one more than the maximum height of its left and right subtree. Recursively apply this property to all tree nodes in a bottom-up manner (postorder fashion) and return the subtree’s maximum height rooted at that node.

The algorithm can be implemented as follows in C++, Java, and Python:

C++


Download  Run Code

Output:

The height of the binary tree is 3

Java


Download  Run Code

Output:

The height of the binary tree is 3

Python


Download  Run Code

Output:

The height of the binary tree is 3

The time complexity of the above iterative solution is O(n), where n is the total number of nodes in the binary tree. The auxiliary space required by the program is O(h) for the call stack, where h is the height of the tree.

Iterative Solution

In an iterative version, perform a level order traversal on the tree. Then the height of a tree is equal to the total number of levels in it. Following is the C++, Java, and Python program that demonstrates it:

C++


Download  Run Code

Output:

The height of the binary tree is 3

Java


Download  Run Code

Output:

The height of the binary tree is 3

Python


Download  Run Code

Output:

The height of the binary tree is 3

The time complexity of the above recursive solution is O(n), where n is the total number of nodes in the binary tree. The auxiliary space required by the program is O(n) for the queue data structure.

Rate this post

Average rating 4.59/5. Vote count: 219

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?




Thanks for reading.

Please use our online compiler to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

Like us? Refer us to your friends and help us grow. Happy coding :)



Subscribe
Notify of
guest
14 Comments
Most Voted
Newest Oldest
Inline Feedbacks
View all comments
Do NOT follow this link or you will be banned from the site!