# Calculate the height of a binary tree – Iterative and Recursive 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++

Output:

The height of the binary tree is 3

## Java

Output:

The height of the binary tree is 3

## Python

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++

Output:

The height of the binary tree is 3

## Java

Output:

The height of the binary tree is 3

## Python

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? 