LeetCode 111 – Minimum Depth of Binary Tree

This is the payoff for the trap set in Maximum Depth. The obvious edit — swap max for min — is wrong, and it is wrong for a reason worth understanding rather than patching: a node with one child is not a leaf, but its missing side still reports a depth of zero.

The problem

Return the minimum depth of a binary tree: the number of nodes along the shortest path from the root down to the nearest leaf. A leaf is a node with no children.

      3
     / \        -> 2      the leaf 9 is two nodes down
    9   20
       /  \
      15   7

    1
     \         -> 2      NOT 1 -- node 1 has a child, so it is not a leaf
      2

  []           -> 0
  [1]          -> 1
  [1,2,null,3] -> 3      a chain: the only leaf is at depth 3

Why min does not simply replace max

    1
     \
      2

1 + min(depth(null), depth(2))
= 1 + min(0, 1)
= 1                             the answer is 2

The null branch returns 0, min happily takes it, and the recursion reports a path that stops in mid-air rather than at a leaf. max never hits this because the null side is exactly the side it discards — the asymmetry was hiding in problem 104 the whole time.

The fix is not a bigger base case; it is recognising that a missing child means "no path this way", which is infinity, not zero. Either write that literally, or branch on it:

no children      -> 1                          a real leaf
left missing     -> 1 + minDepth(right)        only one way down
right missing    -> 1 + minDepth(left)
both present     -> 1 + min(left, right)

Java

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

        // A node with ONE child is not a leaf, so the missing side must not win
        // the min -- take the side that actually leads somewhere.
        if (root.left == null) return 1 + minDepth(root.right);
        if (root.right == null) return 1 + minDepth(root.left);

        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
}

There is no explicit leaf case, and there does not need to be: a leaf has both children null, so the first guard fires, recurses into a null, and gets 1 + 0 = 1. Convincing yourself of that rather than adding a fourth branch is worth the ten seconds.

The two guards look like duplication and are not — they handle mirror-image situations and collapsing them would reintroduce the bug.

Python

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0

        if root.left is None:
            return 1 + self.minDepth(root.right)
        if root.right is None:
            return 1 + self.minDepth(root.left)

        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

BFS is the better answer here

For maximum depth, DFS and BFS both have to visit every node, so the choice was about stack versus queue. For minimum depth that changes completely: BFS meets the shallowest leaf first and can stop there.

    def minDepthBfs(self, root: TreeNode) -> int:
        from collections import deque

        if root is None:
            return 0

        depth, queue = 0, deque([root])

        while queue:
            depth += 1
            for _ in range(len(queue)):          # one whole level, as in problem 102
                node = queue.popleft()

                if node.left is None and node.right is None:
                    return depth                 # first leaf reached IS the answer

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return depth

On a tree with a leaf near the root and a million nodes hanging off the other side, DFS explores the whole thing and BFS returns almost immediately. The worst case is still O(n) — a perfect tree, where the shallowest leaf is on the last level — but the typical case is dramatically better, and this is the clearest example in the tree set of "same complexity, different algorithm to actually run".

Note the early return sits before the children are enqueued. Checking after would still be correct but would push a level of nodes you are about to discard.

Complexity

	Time	Space
DFS	`O(n)` always	`O(h)`
BFS	`O(n)` worst, often far less	`O(w)`

Both are O(n) on paper. Saying "they are the same complexity but BFS stops at the first leaf, so it wins on any tree that is not perfectly balanced" is a more useful answer than either the complexity alone or the preference alone.

The pattern

The transferable lesson is not about trees. It is that a symmetric-looking problem is not always symmetric: max and min behave differently over a set that includes a sentinel, because one of them ignores the sentinel and the other is captured by it. The same asymmetry shows up wherever an "absent" value is encoded as a number rather than as absence.

Path Sum (112) has the same leaf-versus-null distinction and the same class of bug. Sum Root to Leaf Numbers (129) and Binary Tree Paths (257) both hinge on getting "what counts as a complete path" right.

What the interviewer is checking

That you catch the one-child case rather than mirroring problem 104.
That a missing child is infinity, not zero — and can say why.
[1,null,2] returning 2, which is the whole test.
Empty tree returning 0 and a single node returning 1.
That no explicit leaf branch is needed, and why.
That BFS can return at the first leaf, and that this is where it genuinely beats DFS.