Minimum Depth of a Binary Tree (Nearest Leaf via BFS)

• BFS advantage – BFS explores strictly in order of increasing depth, so the first leaf encountered is the shallowest.
• Leaf test – a leaf has both children null; check this for every dequeued node.
• Early exit – return the current depth immediately when a leaf is found, avoiding deeper levels.
• Depth counter – increment once per level, not per node.
• Complexity – O(n) worst case, but short-circuits for shallow leaves; O(w) space.

What is the Minimum Depth problem?

The minimum depth of a binary tree is the number of nodes along the shortest path from the root to the nearest leaf. A leaf is a node with both children null. The minimum depth is at least 1 (the root alone is a leaf if it has no children).

This problem is best solved with BFS because BFS visits nodes in order of increasing depth, guaranteeing the first leaf found is the shallowest.

Why is BFS better than DFS for minimum depth?

BFS short-circuits: the moment it finds a leaf, it returns the current depth without visiting any deeper levels. DFS must explore every path to every leaf and take the minimum, visiting the entire tree. For trees where the nearest leaf is shallow, BFS is significantly faster.

package com.bank.service;

import java.util.*;

public class ShortestApprovalPath {

    static class TreeNode {
        int approverLevel;
        TreeNode left, right;
        TreeNode(int val) { this.approverLevel = val; }
    }

    public static int minDepth(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                // Leaf test: both children null
                if (node.left == null && node.right == null) {
                    return depth;
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            depth++;
        }
        return depth; // should not reach here for non-null root
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        // Right child (3) is a leaf at depth 2
        System.out.println("Minimum depth: " + minDepth(root));
    }
}

Minimum depth: 2

How is minimum depth different from maximum depth?

| Aspect | Minimum Depth | Maximum Depth |
|---|---|---|
| Goal | Shortest root-to-leaf path | Longest root-to-leaf path |
| BFS advantage | Short-circuits at first leaf | No short-circuit, must visit all |
| DFS approach | Must visit all paths (no early exit) | 1 + max(left, right) |
| Best algorithm | BFS | Either BFS or DFS |

For minimum depth, BFS is strictly better. For maximum depth, both are equivalent because every node must be visited regardless.

// DFS for minimum depth (less efficient, no early exit)
public static int minDepthDFS(TreeNode node) {
    if (node == null) return 0;
    if (node.left == null) return 1 + minDepthDFS(node.right);
    if (node.right == null) return 1 + minDepthDFS(node.left);
    return 1 + Math.min(minDepthDFS(node.left), minDepthDFS(node.right));
}

What is the single-child trap in the DFS version?

The classic bug in the DFS version is treating a node with one child as a leaf. A node with only a left child is not a leaf; its minimum depth comes from the left subtree, not from the missing right subtree.

// WRONG: treats one-child node as leaf
public static int minDepthBuggy(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.min(minDepthBuggy(node.left), minDepthBuggy(node.right));
}
// For tree: 1 -> 2 -> 3 (right-skewed)
// minDepthBuggy(1) = 1 + min(0, minDepthBuggy(2))
// = 1 + min(0, ...) = 1 -- WRONG! Should be 3.
// The null left child returns 0, but null is not a leaf.

// CORRECT: guard single-child nodes
public static int minDepthCorrect(TreeNode node) {
    if (node == null) return 0;
    if (node.left == null) return 1 + minDepthCorrect(node.right);
    if (node.right == null) return 1 + minDepthCorrect(node.left);
    return 1 + Math.min(minDepthCorrect(node.left), minDepthCorrect(node.right));
}

What are the edge cases?

• Null root – return 0.
• Single node (root is a leaf) – return 1.
• Left-skewed tree – minimum depth equals n (every node has only a left child).
• Balanced tree – minimum depth is log(n) + 1.

// Edge case: root is a leaf
TreeNode leaf = new TreeNode(100);
System.out.println(minDepth(leaf)); // 1

// Edge case: left-skewed tree (depth = n)
// 1 -> 2 -> 3 -> 4
// minDepth = 4 (must go all the way down)

What are common mistakes?

Besides the single-child trap in DFS, a common BFS mistake is incrementing depth per node instead of per level.

// WRONG: depth++ inside the inner loop
for (int i = 0; i < levelSize; i++) {
    depth++; // increments per NODE, not per LEVEL
}

// CORRECT: depth++ after the entire level is processed
depth++; // outside the for loop

What is the time and space complexity?

BFS: O(n) worst case (no leaf until the last level), but short-circuits for shallow leaves. Space is O(w) for the queue. DFS: O(n) always (visits every node). Space is O(h) for the recursion stack.

For a banking approval tree with 10,000 nodes but a leaf at depth 3, BFS processes only the first three levels (about 7 nodes), while DFS processes all 10,000.

What should a senior engineer know?

A senior engineer should articulate why BFS is strictly better here: the shortest-path guarantee of level-by-level exploration gives an early exit that DFS cannot match. They should also explain the single-child guard in the DFS version and why BFS naturally avoids it (the leaf test checks both children explicitly).