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.

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

python

▶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

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.

06

Complexity

Time

O(n)

Space

O(n)

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