Minimum Depth of Binary Tree: Finding the Nearest Leaf

You are given the root of a binary tree. Return its minimum depth, which is the number of nodes along the shortest path from the root down to the nearest leaf node. A leaf is a node with no children.

This is LeetCode 111: Minimum Depth of Binary Tree. It looks like a trivial twist on Maximum Depth, but there is a subtle trap that catches most people on their first attempt. Swapping max for min does not work, and the reason why teaches you something important about how leaf nodes behave in tree recursion.

Why this problem matters

The trap is the one-child case. If a node has only one child, its minimum depth is NOT 1. You cannot count the missing child as a path, because a path must end at a leaf. A null pointer is not a leaf. You have to go through the existing child and keep looking.

This forces you to think carefully about what "leaf" actually means in your code, and that awareness carries over to every tree problem that involves root-to-leaf paths: Path Sum, Binary Tree Paths, Sum Root to Leaf Numbers, and many others.

The key insight

Consider this skewed tree: [2, null, 3, null, 4, null, 5, null, 6]. Every node has only a right child. The only leaf is node 6, all the way at the bottom. The minimum depth is 5, not 1.

If you naively take min(left_depth, right_depth), the missing left subtree returns 0, and you get min(0, something) + 1 = 1. That is wrong. You need to skip the missing side entirely and only recurse through the child that actually exists.

BFS avoids this issue naturally. You process the tree level by level and return the moment you find the first leaf. Since BFS explores shallow nodes before deep ones, the first leaf you encounter is guaranteed to be at minimum depth. No special-casing needed.

The BFS solution

from collections import deque

def min_depth(root):
    if not root:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

The logic is clean. Process one level at a time. For each node, check if it is a leaf. If yes, return the current depth immediately. If not, add its children to the queue for the next level.

This is BFS with early termination. You never visit a single node deeper than the answer requires.

Visual walkthrough

Let's trace the BFS on the tree [3, 9, 20, null, null, 15, 7]. Watch how BFS processes level by level and stops the instant it finds a leaf.

At depth 2, BFS dequeues node 9. Node 9 has no left child and no right child, so it is a leaf. BFS returns 2 immediately. It never even looks at nodes 15 and 7. That is the power of BFS early termination: you stop as soon as you have the answer, without exploring the rest of the tree.

The DFS alternative (and its trap)

You can solve this with DFS, but you must handle the one-child case explicitly:

def min_depth(root):
    if not root:
        return 0
    if not root.left:
        return 1 + min_depth(root.right)
    if not root.right:
        return 1 + min_depth(root.left)
    return 1 + min(min_depth(root.left), min_depth(root.right))

The first two if checks are the one-child guards. If the left child is missing, you can only go right. If the right child is missing, you can only go left. Only when both children exist do you take the minimum of both sides.

Without those guards, a skewed tree like [2, null, 3, null, 4] would incorrectly return 1 instead of 3. The null left side returns 0, and min(0, 2) + 1 = 1, which counts a non-existent path.

DFS works correctly with the guards, but it always visits every node in the tree. BFS can stop early, which makes it the better choice for this problem.

Complexity analysis

Time is O(n) worst case for both. BFS can terminate early when the nearest leaf is shallow, but if the tree is balanced, the first leaf is at the bottom level and you visit every node. DFS always visits every node regardless.

Space is O(n) for both. BFS holds up to one full level in the queue. For a balanced tree, the widest level has roughly n/2 nodes, so that is O(n). DFS uses O(h) call stack space where h is the height, and in the worst case (skewed tree) h = n.

In practice, BFS is preferred here. Its early termination gives it a real-world advantage on trees where the nearest leaf is close to the root, and the level-by-level logic maps directly to the definition of minimum depth.

Edge cases to watch for

• Empty tree (root is None): return 0. There is no path at all.
• Single node (root is a leaf): return 1. The root is both the start and end of the only path.
• Skewed tree (every node has one child): the only leaf is at the very bottom. Minimum depth equals the total number of nodes. This is where the one-child trap bites if you do not handle it.
• Balanced tree: every leaf is at the same depth. BFS finds the first leaf at the last level.

The building blocks

This problem is built on two fundamental building blocks:

BFS early termination. Standard BFS processes every node in the graph or tree. But when you are searching for the first occurrence of some condition (in this case, the first leaf), you can return the moment you find it. BFS guarantees that the first match is at the shallowest depth. This same technique appears in Word Ladder (find shortest transformation), Shortest Path in Binary Matrix, and any problem that asks for the minimum number of steps.

Leaf detection. A leaf node has no left child and no right child. The check not node.left and not node.right appears in every root-to-leaf problem. Getting this wrong (for example, treating a null node as a leaf) is one of the most common tree bugs.

From understanding to recall

You now understand why BFS is the natural fit for minimum depth, and why the one-child case breaks naive DFS. The BFS solution is short and the logic is clean. It makes sense right now.

But next time you see a tree problem that asks for a shortest path or minimum level, will you instinctively reach for BFS with early termination? Will you remember to check for leaves with not node.left and not node.right instead of checking at null? Those are the details that separate understanding from recall.

Spaced repetition builds recall. You practice typing the BFS solution from memory at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the queue setup, the level-by-level loop, and the leaf check from scratch. After a few repetitions, BFS early termination becomes automatic.

BFS early termination and leaf detection are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Maximum Depth of Binary Tree - The mirror problem. Max depth uses DFS naturally because you need to explore the entire tree. Min depth uses BFS because you can stop at the first leaf. Understanding both shows you when to pick each traversal.
• Path Sum - Another root-to-leaf problem that requires correct leaf detection. The same not node.left and not node.right check that matters here is the core of Path Sum too.