Find The Height Of a Binary Tree

Difficulty: Easy

Asked in: Amazon, Goldman Sachs

Understanding The Problem

Problem Description

Given a binary tree, write a program to find the maximum depth of the binary tree.

Problem Note

The maximum depth is the number of nodes along the longest path from the root node to the leaf node.
A leaf is a node with no child nodes.

Example

Input: Given binary tree, 
[5, 3, 6, 2, 4, -1, -1, 1, -1, -1, -1, -1, -1]
      5
     / \
    3   6
   / \
  2   4
 /
1
Output: return its depth = 4

Solutions

The height of a binary tree is the maximum distance from the root node to the leaf node. We can find the height of the binary tree in two ways.

Recursive Solution : In a recursive function, for each child of the root node, we can increment height by one and recursively find the height of the child tree.
Iterative Solution : We can do a level order traversal and for each new level, we can increment the height by one.

The node structure passed to the function is:

struct TreeNode{
    int val
    TreeNode left
    TreeNode right
}

You can try practising this problem here.

1. Recursive Solution

To solve a tree's problems, recursive solutions are very intuitive. Like in this case, a very intuitive approach is to find the maximum of height from the left subtree and the right subtree of the root node and return the maximum height + 1.

In other words, We can define a subproblem as, If the root node has left child or right child then find the maximum height of the trees whose root is the left child and the right child. Add 1 to the maximum height of the children tree (Why?).

Solution Steps

Check if the root is NULL then return 0
Return the maximum(left subtree of root, right subtree of root) + 1

Pseudo Code

int maxDepth(TreeNode root) {
    if(root){
        height = max(maxDepth(root.left), maxDepth(root.right))
        return height + 1
    }
    return 0
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Critical Ideas To Think

Why did we add 1 with the height in pseudocode? Answer : The root node itself contributes to the path of maximum height from root to leaf node.
Why space complexity is O(n)? Answer : The tree can be skew, in such cases the recursion stack uses the space.
What is the base case for the recursion? Answer: If the root is NULL then we return 0. (Why?)

2. Iterative Solution

One can think of an iterative solution if you consider solving this problem using BFS traversal or Level Order Traversal. For each new level encountered while traversing from the root node, we can increment the height of the tree by one.

How can we implement level order traversal to find height?

We will take a Queue and add root to it. And we can initialize a variable height to maintain the maximum height of the tree.

Now, we will dequeue all the nodes of the Queue from the front and will enqueue the left and right child of the dequeued nodes in the rear which represent the next level of the tree. For each such cycle, we can increment the height by one. We will continue doing this until no nodes left in the Queue.

Solutions Steps

Create a Queue and push the root node in it
Dequeue all the nodes of Queue and enqueue all the children of the dequeued nodes —

For each such step, increment the height by 1

3. Repeat step 2 until the Queue becomes empty.

Pseudo Code

int maxDepth(TreeNode *root) { 
    // Base Case 
    if (root is NULL) 
        return 0
    // Create an empty queue for level order tarversal 
    Queue q
    q.push(root)
    int height = 0
    while (true) { 
        int currLevelNodes = q.size()
        if (currLevelNodes == 0) 
            return height
        height = height + 1
        while (currLevelNodes > 0) 
        { 
            TreeNode node = q.front()
            q.pop()
            if (node.left is not NULL) 
                q.push(node.left)
            if (node.right is not NULL) 
                q.push(node.right)
            currLevelNodes = currLevelNodes - 1
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Critical Ideas To Think

Why did we return the height only when currLevelNode is 0?
Why did we pop all the nodes inside the Queue? How did that help us to filter the nodes of the current level and the next level of the tree?