Find Height of a Binary Tree

Difficulty: Medium, Asked-In: Amazon, VMWare, Zoho, Synopsys.

Key takeaway: One of the fundamental tree problems to learn problem-solving using DFS (Postorder) and BFS traversal.

Let’s understand the problem

Given a binary tree, write a program to find its height. In other words, we need to calculate the maximum depth of the binary tree.

The height or maximum depth of a binary tree is the total number of edges on the longest path from the root node to the leaf node. In other words, the height of a binary tree is equal to the maximum number of edges from the root to the most distant leaf node.
The height of an empty tree or tree with one node is 0.

Example

find the height of a tree example

In the above diagram, 5, 8, and 9 are leaf nodes.

Count of edges from root to node 5 = 3.
Count of edges from root to node 8 = 3.
Count of edges from root to node 9 = 2.

The maximum count of edges from root to farthest leaf = max(3, 3, 2) = 3.

So, the height of the given binary tree = 3.

Discussed solution approaches

Recursive approach: Using DFS (post-order) traversal
Iterative approach: Using BFS (level order) traversal

Recursive approach: Using DFS (post-order) traversal

Solution idea

A binary tree is a recursive structure where we can solve the problem using the solution of two smaller subproblems: the left sub-tree and the right sub-tree. So how can we apply this idea to find the height of a binary tree? Let's think!

Based on the definition, for finding the height, we should know the path length of the root to the deepest leaf node, which can be either present in the left-subtree or right sub-tree. In other words, the longest path from the root to the deepest leaf can go through either the left or right child of the root.

So the best idea would be to calculate the height of the left and right sub-tree recursively. Whichever sub-tree has the maximum height, we take that value and add 1 to get the height of the tree. The height of the tree = The longest path from the root node to the leaf node = 1 + max (height of the left sub-tree, height of the right sub-tree).

So if we know the height of the left and right sub-tree then we can easily find the height of the tree. In other words, before calculating the height of the tree, we should calculate the height of the left and right sub-trees. So we need to apply the idea of post-order traversal. Explore and think!

Solution steps

Suppose we are using the function int treeHeight(TreeNode root).

If tree is empty or tree has only one node, we return 0. This would be our base case. Otherwise, we traverse the tree in a post-order fashion and call the same function for the left and right child to calculate the height of the left and right sub-tree.
```
int leftHeight = treeHeight(root->left)
int rightHeight = treeHeight(root->right)
```
Now after calculating the height of the left and right subtree, we take the maximum height among both and return the value by adding one to it.
```
if (leftHeight > rightHeight) 
  return (leftHeight + 1)
else 
  return (rightHeight + 1)
```

Solution pseudocode

int treeHeight(TreeNode root)
{
    if(root == NULL || (root->left == NULL && root->right == NULL))
        return 0
    else
    {
        int leftHeight = treeHeight(root->left)
        int rightHeight = treeHeight(root->right)
        
        if(leftHeight > rightHeight)
            return (leftHeight + 1)
        else
            return (rightHeight + 1)
    }
}

Solution analysis

We are doing post-order traversal to find the height i.e. visiting each node using post-order and doing O(1) operation with each node. So time complexity = n*O(1) = O(n). Space complexity is equal to the size of the recursion call stack, which is equal to the height of the tree.

The best-case scenario occurs when the tree is balanced, or the tree's height is O(logn). So best case space complexity = O(logn).
The worst-case scenario occurs when the tree is highly unbalanced or skewed, i.e., there is only one node at each level. In this case, the height of the tree is O(n). So worst-case space complexity = O(n).

Iterative approach: Using BFS (level order) traversal

Solution idea

Now a critical question is: Can we find the height of the tree without recursion? Can we use level order traversal to find height? Let's think! As we know, the height of the binary tree = The total number of levels in the binary tree - 1. So one idea is: We traverse the tree using level order traversal, count the total number of levels and calculate the height.

Here we traverse the tree level by level and increment a level count by 1 whenever we reach a new level. So how do we identify the situation when we reach a new level? Here is the idea: Suppose level order traversal is at the start of some level x. Now after processing all the nodes at level x, we will reach new level x + 1.

To implement this, we count nodes at the current level x, and using a loop, we add the next-level nodes to the queue until the count of nodes at the current level is 0. Now level order traversal has processed all the nodes at level x and it is at the start of the next level x + 1. At this stage, we increment the level count by 1. We keep repeating this process whenever we encounter a new level. At the start, the value of the level count is initialized to 0.

Solution steps

We create a queue Q and push the root node into it.
We also initialize a variable levelCount with 0 to track the level count of the tree.
Now we run a while loop till the Q becomes empty. At each iteration of this loop will explore one level of the binary tree.
- We increase levelCount by 1 and store the count of nodes at the current level in a variable nodeCount (equal to the current size of the queue).
```
levelCount = levelCount + 1
int nodeCount = queue.size()
```
- Now we insert children of all the nodes in the current level into the queue. For this, we run another loop till the nodeCount at the current level is 0. We check if the current node has the left and right children. If yes, we insert it into the queue.
```
for(int i = 0; i < nodeCount; i = i + 1)
{
    TreeNode temp = Q.dequeue()
    if(temp->left != NULL)
        Q.enqueue(temp->left)
    if(temp.right != NULL)
        Q.enqueue(temp->right)
}
```
If the queue is empty, it implies that the last level of the tree has been completely processed, and we return levelCount - 1 as the height of the tree.

Solution pseudocode

int treeHeight(TreeNode root)
{
    if (root == NULL || (root->left == NULL && root->right == NULL))
        return 0

    int levelCount = 0
    queue<TreeNode> Q
    Q.enqueue(root)
    
    while(Q.empty() == false)
    {
        levelCount = levelCount + 1
        int nodeCount = Q.size()
        
        for(int i = 0; i < nodeCount; i = i + 1)
        {
            TreeNode temp = Q.dequeue()
            
            if(temp->left != NULL)
                Q.enqueue(temp->left)
                
            if(temp->right != NULL)
                Q.enqueue(temp->right)
        }
    }
    
    return levelCount - 1
}

Solution analysis

Time complexity = Time complexity of the level order traversal = O(n).

Space complexity = Space complexity of the level order traversal.

The worst-case space complexity = O(n), when the tree is balanced.
The best-case space complexity = O(1), when the tree is highly un-balanced or there is only one node at each tree level.

Critical ideas to think!

How can we solve this problem using iterative traversal using stack?
Can we solve this problem using pre-order or in-order traversal?
Can we think of implementing the BFS approach using some other technique? Here is another idea: During the normal level order traversal, we can use a marker (NULL or none) to track the end of each level. Whenever we encounter NULL, we increment the height by 1 and insert NULL into the queue to mark the end of the next level. Otherwise, we proceed to insert left and right child nodes into the queue. Think and explore about application of this solution in tree problem solving. Here is the pseudocode:

int treeHeight(TreeNode root) 
{
    if (root == NULL)
        return 0

    queue<TreeNode> Q
    Q.enqueue(root)
    // Marker for the end of the current level
    Q.enqueue(NULL) 
    int height = 0

    while (Q.empty() == false) 
    {
        TreeNode temp = Q.dequeue()
        if (temp == NULL) 
        {
            // Finished traversing the current level
            height = height + 1
            // If there's more to process, add another NULL marker
            if (Q.empty() == false)
                Q.enqueue(NULL)
        } 
        else 
        {
            // Enqueue left and right children if they exist
            if (temp->left)
                Q.enqueue(node->left) 
            if (temp->right)
                Q.enqueue(node->right)
        }
    }

    return height
}

Find Height of a Binary Tree

Let’s understand the problem

Example

Discussed solution approaches

Recursive approach: Using DFS (post-order) traversal

Solution idea

Solution steps

Solution pseudocode

Solution analysis

Iterative approach: Using BFS (level order) traversal

Solution idea

Solution steps

Solution pseudocode

Solution analysis

Critical ideas to think!

Similar coding questions to practice

More from EnjoyAlgorithms

Self-paced Courses and Blogs