Find the Maximum Depth or Height of a Tree

EnjoyAlgorithms Blog Cover Image

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

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

Let’s understand the problem

Given a binary tree, write a program to find the height of it.

  • The height or the depth of a binary tree is the total number of nodes or 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 largest number of edges or nodes from the root to the most distant leaf node.
  • The height of an empty tree is 0, and the height of a tree with one node is 1. 

Example

find the height of a tree example

The leaf nodes of the binary tree are 5, 8, and 9.

  • For leaf node 5, the number of nodes along the edges is 4. 
  • For leaf node 8, the number of nodes along the edges is 4. 
  • For leaf node 9, the number of nodes along the edges is 3. 

The maximum number of nodes from root to farthest leaf = max(4, 4, 3) = 4. Hence, the height of the binary tree is 4. 

Discussed Solution Approaches

  • Recursive approach: Using DFS or Post-order traversal
  • Iterative approach: Using BFS or Level order traversal

Recursive approach: Using DFS or 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: left sub-tree and 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. Here is a clear insight:

The height of the tree = the longest path from the root node to the leaf node = 1 + max (longest path from the left-child to the leaf node, longest path from the right-child 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. But one idea would be clear: before calculating the height of the tree, we must know the height of the left and right sub-tree. For this, we can use the post-order traversal. Think!

Solution Steps

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

  • If the tree is empty or root == NULL, we return 0 as the height of the given binary tree. 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) 
        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 for finding the height of the tree. So time complexity = 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)

Explore this blog for better understanding: Recursive Tree Traversals of a Binary Tree

Iterative approach: Using BFS or 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!

The idea is: while doing the level order traversal, whenever we move down to a level, we increase height by 1. We count the number of nodes at the current level, and using a loop, we start adding next-level nodes to the queue till the count of nodes at the current level is 0.

After this, we move to the next level and again increase the height by 1. In simple words, we continue a similar process whenever we encounter a new level in the tree. At the start, the value of height is initialized as 0.

Solution Steps

  1. We create a queue Q and push the root node into it. We also initialize a variable height with 0 to track the height of the tree.

    if(root == NULL)
       return 0
    int height = 0
    Queue Q
    Q.enqueue(root)
    
  2. Now we run a while loop till the Q becomes empty. In other words, this loop will explore every level. At each iteration of this loop:

    • We increase the height by 1 and store the count of the number of nodes at the current level in a variable nodeCount (equal to the current size of the queue).
    height = height + 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)
    }
    
  3. If the queue is empty, it implies that the last level of the tree has been completely processed, and we return the value stored in the variable height.

Solution Pseudocode

int treeHeight(TreeNode root)
{
    if(root == NULL)
        return 0
    int height = 0
    Queue Q
    Q.enqueue(root)
    while(Q.empty() == false)
    {
        height = height + 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 height
}

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.

Explore this blog for better understanding: Level Order Traversal of a Binary Tree

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? Can we use a NULL value to identify the new level in the tree?

Similar coding questions to practice

Enjoy learning! Enjoy algorithms!

We'd love to hear from you

More content from EnjoyAlgorithms

Our weekly newsletter

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!