LeetCode #111 Easy

Minimum Depth of Binary Tree

Find the length of the shortest path from the root to any leaf.

treebfs

02

Intuition

Mirroring maxDepth with min(depth(left), depth(right)) looks natural but breaks the moment a node has only ONE child: the missing side reports depth 0, and min() happily returns 0, claiming a leaf exists where there is none. A leaf is a node with NO children at all -- when only one child is present you must recurse into that side exclusively and ignore the missing one. BFS sidesteps the whole trap: walking level by level, the very first leaf you dequeue is guaranteed to be at the minimum depth, since BFS never explores a deeper level before a shallower one is exhausted.

How to spot this pattern

BFS returns on the first leaf it meets, which is by construction the shallowest — so the search stops early instead of exploring the whole tree. This is the case where BFS strictly beats DFS, since DFS must visit every node before it can be sure.

03

Approach

1

BFS level by level

Seed a queue with the root at depth 1. Process nodes in FIFO order, tracking each node's depth alongside it.

2

Stop at the first true leaf

The instant a dequeued node has no left AND no right child, its depth is the answer -- return immediately, no need to drain the rest of the queue.

3

Otherwise keep expanding

Push any existing children with depth + 1 and continue; a node with only one child is not a leaf and must not be mistaken for one.

04

Solution & live demo

▶1from collections import deque
▶2 
▶3class Solution:
▶4    def minDepth(self, root):
▶5        if not root:
▶6            return 0
▶7        queue = deque([(root, 1)])
▶8        while queue:
▶9            node, depth = queue.popleft()
▶10            if not node.left and not node.right:
▶11                return depth
▶12            if node.left:
▶13                queue.append((node.left, depth + 1))
▶14            if node.right:
▶15                queue.append((node.right, depth + 1))

05

Common pitfalls

Using the max-depth recurrence with min

✗ Wrong

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

✓ Right

if not node.left and not node.right:
    return depth

For a node with one child, the missing side returns 0 and min picks it — reporting a depth that ends at a non-leaf. The recursive version needs an explicit single-child case; BFS sidesteps it entirely.

Returning at the first node with a missing child

✗ Wrong

if not node.left or not node.right:
    return depth

✓ Right

if not node.left and not node.right:

A node with exactly one child is internal, not a leaf. The or version stops at the first such node and reports a depth shorter than any real root-to-leaf path.

Using DFS and scanning every path

✗ Wrong

# full DFS, tracking the minimum leaf depth

✓ Right

queue = deque([(root, 1)])

Correct but visits every node even when a leaf sits one level down. BFS reaches the shallowest leaf first and returns immediately, which on a deep skewed tree is the difference between O(1) and O(n).

06

Edge cases

Empty tree

Return 0 immediately, no nodes to search.

Single node

Root is dequeued first and has no children -- min depth 1.

One-sided chain (e.g. only right children)

BFS still finds the single leaf at the true bottom; a min()-based DFS would wrongly report 1.

Balanced tree

First level with any leaf ends the search, often well before reaching every node.

07

Complexity

Time

O(n)

Space

O(n)

Worst case visits every node; typically stops much earlier at the first leaf.