Find Height of a Binary Tree

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

Key takeaway: A fundamental tree problem to learn problem-solving using DFS 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

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!

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.

One idea would be to calculate the height of the left and right sub-tree recursively. Whichever sub-tree has the max 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 to the leaf node = 1 + max (height of the left subtree, height of the right subtree). Before calculating the height of the tree, we need to calculate the height of the left and right sub-trees. So this is the idea similar to post-order traversal!

Solution steps

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

• If tree is empty or tree has only one node, return 0. This is 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.
• 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.

Solution pseudocode

treeHeight(root)
    if root is null or root is a leaf
        return 0

    leftHeight = treeHeight(root.left)
    rightHeight = treeHeight(root.right)

    if leftHeight > rightHeight
        return leftHeight + 1
    else
        return rightHeight + 1

Solution analysis

We are visiting each node using post-order and doing O(1) operation with each node. So time complexity = n*O(1) = O(n). Space complexity = Size of the recursion call stack = O(h).

• The best-case scenario occurs when the tree is balanced, or the tree height is O(logn). So best case space complexity = O(logn).
• The worst-case occurs when the tree is highly unbalanced, 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? As we know, the height of the binary tree = Total number of levels - 1. So one idea is: traverse the tree using level order, count the 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 the new level x + 1.

To implement this, we count the nodes at the current level x and, using a loop, process all the nodes at the current level and add all next level nodes to the queue. Now all current-level nodes are removed from the queue, and next level nodes are inside the queue. It means: We are at the start of the next level x + 1. So at this stage, we increment the level count by 1. We keep repeating this process whenever we encounter a new level.

Solution steps

1. We create a queue Q and push the root node into it.
2. We also initialize a variable levelCount with 0 to track the level count.

3. Run a loop till Q becomes empty. One iteration of this loop will explore one level. So at each iteration:

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

treeHeight(root)
    if root is null or root is a leaf
        return 0

    levelCount = 0
    queue = empty queue
    enqueue root

    while queue is not empty
        levelCount = levelCount + 1
        nodeCount = size of queue
        // Process all nodes at the current level
        for i from 0 to nodeCount - 1
            node = dequeue queue
            if node.left is not null
                enqueue node.left
            if node.right is not null
                enqueue node.right

    // Height is measured in edges
    // so subtract one from the level count
    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) 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:

treeHeight(root)
    if root is null
        return 0

    queue = empty queue
    enqueue root
    enqueue null  // Marks the end of the current level
    height = 0

    while queue is not empty
        node = dequeue queue
        if node is null
            // Finished processing one level
            height = height + 1
            // Mark the end of the next level, if nodes remain
            if queue is not empty
                enqueue null
        else
            if node.left is not null
                enqueue node.left

            if node.right is not null
                enqueue node.right

    return height

Similar coding questions to practice

• Find min depth of a binary tree
• Merge two binary tree
• Count half nodes in a Binary tree
• Count full nodes in a Binary tree
• Deepest right leaf node in a binary tree
• Get the level of a node in a binary tree
• Check if two trees are identical
• Print all nodes at distance K from a given node

Enjoy learning! Enjoy algorithms!