Minimum Depth of Binary Tree

Problem Statement

The task is to determine the minimum depth of a binary tree, which is defined as the number of nodes along the shortest path from the root node to the nearest leaf node. A leaf node is a node without any children. Your goal is to compute this minimum depth efficiently.

Examples

Example 1

Input:

root = [3,9,20,null,null,15,7]

Output:

2

Explanation:

The binary tree can be visualized as:

    3
   / \
  9  20
     / \
    15  7

The shortest path to a leaf is from node 3 → 9, which has a depth of `2`.

Example 2

Input:

root = [2,null,3,null,4,null,5,null,6]

Output:

5

Explanation:

The binary tree is skewed to the right:

2
 \
  3
   \
    4
     \
      5
       \
        6

There is only one leaf (node 6). The path to the leaf is 2 → 3 → 4 → 5 → 6, with depth `5`.

Constraints

• The number of nodes in the tree is in the range [0, 10^5].
• -1000 <= Node.val <= 1000.

Approach and Intuition

The problem requires us to compute the shortest path from the root to any leaf. There are two common strategies:

1. Breadth-First Search (BFS) Approach (Recommended):

• BFS allows us to explore the tree level by level.
• The first time we encounter a leaf node, we can return the depth of that level.
• This guarantees an optimal early exit since BFS explores level by level.

Algorithm steps:

1. Initialize a queue with the root node and depth = 1.

2. While the queue is not empty:

   • Dequeue a node and its associated depth.
   • If this node is a leaf, return its depth.
   • Otherwise, enqueue its non-null children with depth + 1.

2. Depth-First Search (DFS) Approach:

• DFS explores deeper into each path first.
• We recursively compute the minimum depth of left and right subtrees.
• The minimum depth is:

minDepth(root) = 1 + min(minDepth(left subtree), minDepth(right subtree))

• Special case: if one child is null, we must not take the min of 0, but instead consider only the valid subtree.

Edge Cases:

• If the tree is empty (root == null), return 0.

Summary:

• BFS is often faster for this problem because it stops early once it finds the first leaf.
• DFS also works well but explores all paths, which is sometimes less optimal for wide trees.

Both methods can handle the constraints (up to 10^5 nodes) if implemented carefully.

Solutions

class Solution {
public:
    int minimumDepth(TreeNode* rootNode) {
        if (!rootNode) return 0;
    
        queue<TreeNode*> nodesQueue;
        nodesQueue.push(rootNode);
        int level = 1;
    
        while (!nodesQueue.empty()) {
            int levelSize = nodesQueue.size();
    
            while (levelSize--) {
                TreeNode* currentNode = nodesQueue.front();
                nodesQueue.pop();
    
                if (!currentNode) continue;
    
                if (!currentNode->left && !currentNode->right) {
                    return level;
                }
    
                nodesQueue.push(currentNode->left);
                nodesQueue.push(currentNode->right);
            }
    
            level++;
        }
    
        return -1;
    }
};