Find Minimum Depth of Binary Tree

Difficulty: Easy, Asked-in: Facebook, Amazon

Key takeaway: An excellent problem to learn problem-solving using both recursive and iterative tree traversal. This is also a question to understand efficient problem solving using BFS when the solution node is nearest to the root node.

Let's understand the problem!

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. The path has to end on a leaf node.

Example

Discussed solution approaches

• Using depth-first Search: Recursive tree traversal
• Using breadth-first search: Iterative tree traversal

Using depth-first Search: Recursive tree traversal

We can find the solution by solving the two smaller subproblems: finding the minimum depth of the left subtree and finding the minimum depth of the right subtree. Here's an idea: If we know the minimum depth of both the left and right subtrees, then the minimum depth of the entire tree = 1 + min (min depth of the left subtree, min depth of the right subtree).

• Suppose function treeMinDepth(root) will return the value of the min-depth of the overall tree.
• if(root == NULL), return 0. This is the base case which is the smallest version of the problem where recursion will backtrack and return the value directly.
• if(root->left == NULL), we recursively call the same function for the right subtree and calculate the min-depth. In other words, there is no left sub-tree and min-depth of the tree = 1 + min-depth of the right subtree. treeMinDepth(root) = 1 + treeMinDepth(root->right)
• if(root->right == NULL), we recursively call the same function for the left subtree and calculate the min-depth i.e. there is no right sub-tree and min-depth of the tree = 1 + min-depth of the left subtree. treeMinDepth(root) = 1 + treeMinDepth(root->left)
• If both the children are not NULL, then we recursively call the same function for the left and right subtree, calculate the min-depth and get minimum of both to calculate the min-depth of the overall tree. treeMinDepth(root) = 1 + min (treeMinDepth(root->left), treeMinDepth(root->right))

Solution code C++

int treeMinDepth(TreeNode* root)
{
    if(root == NULL)
        return 0;
        
    if(root->left == NULL)
        return 1 + treeMinDepth(root->right);
        
    if(root->right == NULL)
        return 1 + treeMinDepth(root->left);
        
    return 1 + min(treeMinDepth(root->left), treeMinDepth(root->right));    
}

Time and space complexity analysis

We are traversing each node of the tree only once. Time complexity = O(n)

Space complexity = O(h) for recursion call stack. Space complexity is equal to the maximum depth of the recursion tree which is equal to the height of the tree (h), where O(log n) < h < O(n).

Using breadth-first search: Iterative tree traversal

Now critical questions are: Can we think to solve this problem iteratively using the BFS traversal? How do we calculate the min-depth using this idea? or, do we really need to calculate the min-depth for each node? Is there some information hidden in the problem which could help us to solve the problem efficiently?

Here is an observation: the node with a minimum depth would be always the first leaf node if we traverse the tree level by level. In other words, if we traverse the tree level by level, we need to return the depth of the first encountered leaf node. Think!

In a practical scenario, this idea would be much more efficient in comparison to the DFS approach because, in the DFS approach, we may end up with a complete traversal of the tree even when the topmost leaf is close to the root. But BFS traversal can access the node from top to bottom in level by order and we can get the topmost leaf quickly in fewer steps.

For example, If we have a tree where the left subtree has a depth of 100 and the right subtree has a depth of 1. The DFS will first traverse all the way down the 100 left subtree nodes before finally traversing the right subtree with a small depth of 1 and figuring out it as a min depth. But in BFS, instead of traversing 101 nodes to figure out the min depth, we can get the value in two steps. Now imagine the comparison of efficiency if there are thousands of nodes in the left subtree!

Solution code C++

struct QueueNode 
{
    TreeNode *node;
    int depth;
    QueueNode(TreeNode *n, int d)
    {
        node = n;
        depth = d;
    }
};

int treeMinDepth(TreeNode *root) 
{
    if (root == NULL)
        return 0;
    else 
    {
        queue<QueueNode> q;
        QueueNode tempQNode(root, 1);
        q.push(tempQNode);
        while (!q.empty()) 
        {
            tempQNode = q.front();
            q.pop();
            TreeNode *temp = tempQNode.node;
            int depth = tempQNode.depth;

            if (temp->left == NULL && temp->right == NULL)
                return depth;
            else 
            {
                if (temp->left != NULL) 
                {
                    tempQNode.node = temp->left;
                    tempQNode.depth = 1 + depth;
                    q.push(tempQNode);
                }

                if (temp->right != NULL) 
                {
                    tempQNode.node = temp->right;
                    tempQNode.depth = 1 + depth;
                    q.push(tempQNode);
                }
            }
        }
    }
    
    return 0;
}

Time and space complexity analysis

In the worst case, The total number of queue operations = 2n, because each node gets inserted and deleted only once in BFS traversal. Time complexity = O(n), where n is the total number of nodes.

Space complexity = O(w) because BFS traversal requires queue size proportional to the max-width of the tree (w). Think!

Critical ideas to think!

• Why do we need queue data structure in the level order traversal? What is the worst and best-case space complexity in the BFS approach?
• Can we solve this problem using all DFS traversals?
• Why do we prefer the BFS when the solution node is closer to the root? In which scenario, we prefer the DFS approach?

Suggested coding problems to practice

• Max depth of the binary tree
• Find the diameter of a binary tree
• Count all leaf nodes in a binary tree
• Root to leaf paths with the sum
• Count all nodes with one child
• Depth of the deepest odd level node

Enjoy learning, Enjoy coding, Enjoy problem-solving!