111 · Minimum Depth of Binary Tree

The shortest root-to-leaf path — which sounds like a one-line min(left, right) + 1 away, until a node with only one child quietly breaks that formula.

1 — The problem, and the trap inside it

Find the number of nodes along the shortest path from the root to any leaf. A leaf is a node with no children at all — not a node with only one child. That single clause is the entire difficulty of this problem: it makes the depth-first recurrence non-trivial, and it's precisely what the visualiser below is built to make obvious.

The trap. minDepth(node) = 1 + min(minDepth(left), minDepth(right)) looks right and is wrong the moment one side is null: minDepth(null) returns 0, so a node with a missing left child would report a fake depth-1 path through a subtree that doesn't exist. A one-sided node must forward to its only real child instead of taking a minimum with a phantom zero.

The example below is deliberately the pathological case: every node has exactly one child until the very last one. Naive top-down reasoning says "depth 1, root has a null side!" — the correct answer is 5.

2 — Visualizing the search

2.1 BFS finds it without the trap at all

Breadth-first search sidesteps the recurrence entirely: walk level by level, and the instant you dequeue a node with no children, its level number is the answer — guaranteed minimal, because BFS reaches every node at the smallest depth first, and it stops at the very first leaf it meets.

Queue<TreeNode> q = new LinkedList<>();q.add(root);int depth = 1;while (!q.isEmpty()) {    int sz = q.size();    for (int i = 0; i < sz; i++) {        TreeNode nd = q.poll();        if (nd.left == null && nd.right == null)            return depth;        if (nd.left  != null) q.add(nd.left);        if (nd.right != null) q.add(nd.right);    }    depth++;}

Notice how long the queue stays at size 1: because every node here has only a right child, each level contributes exactly one node to inspect, and none of them qualify as a leaf until 6, four levels down from the root.

2.2 The DFS fix, for comparison

The corrected recursive version explicitly checks for a missing side before taking a minimum:

int minDepth(TreeNode nd) {
    if (nd == null) return 0;
    if (nd.left == null && nd.right == null) return 1;
    if (nd.left == null) return 1 + minDepth(nd.right); // one-sided: forward, don't min-with-zero
    if (nd.right == null) return 1 + minDepth(nd.left);
    return 1 + Math.min(minDepth(nd.left), minDepth(nd.right));
}

Both approaches visit the same nodes in the worst case (a tree with no early leaf, like this one, forces BFS to walk every level and DFS to walk every branch) — but BFS has a structural advantage: it can stop the instant it meets the first leaf, while the naive-looking DFS recurrence above still has to fully return from both children before it can compare. A DFS with manual pruning (aborting once a running best beats the remaining possible depth) can close that gap, but it's more code for the same worst case.

3 — Complexity and edge cases

• Time: O(n) worst case for both approaches — a tree with the shallowest leaf at the bottom (like the one above) offers no early exit.
• Time: O(k) best case for BFS, where k is the number of nodes at or above the shallowest leaf's level — often far less than n.
• Space: O(w) for BFS's queue (w = widest level encountered before stopping), O(h) for DFS's call stack.
• Empty tree: depth 0 by convention.
• Single node: depth 1 — it's a leaf immediately.
• The one-sided chain shown above is the canonical stress test for this problem: it's the input that silently breaks the naive min(left, right) + 1 recurrence, since a null side would otherwise contribute a false 0.

4 — Reference implementation

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    int depth = 1;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode nd = q.poll();
            if (nd.left == null && nd.right == null) return depth;
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
        depth++;
    }
    return depth; // unreachable for a non-empty tree
}