Minimum Depth of Binary Tree
Maximum Depth Of Binary Tree: find the length of the shortest path from the root to any leaf.
- 0 <= number of nodes <= 10⁵
- -1000 <= node value <= 1000
- A node with one child is not a leaf — the shallow side must be ignored
Intuition
Minimum depth of binary tree asks for the shortest path from the root down to a leaf. It looks like Maximum Depth with max swapped for min, and that substitution is wrong — this is the trap the problem exists to test.
Consider a root with only a left child. Mirroring maxDepth gives 1 + min(depth(left), depth(right)). The missing right child reports depth 0, min happily picks it, and the function returns 1 — claiming the root is a leaf when it plainly is not:
- A leaf is a node with no children at all, not a node with one missing child.
So min must only be taken when both children exist. With one child, the answer is that child's depth plus one, no minimum involved.
The recursive fix works, but BFS suits this problem better. Breadth-first search reaches nodes in order of increasing depth, so the first leaf it encounters is the shallowest one — and it can return immediately.
That matters on a badly skewed tree. Imagine a leaf at depth 2 and a chain 10,000 nodes deep on the other side. DFS may descend the entire chain before finding the shallow leaf; BFS stops at depth 2 having touched a handful of nodes.
So the early exit is not a micro-optimisation here — it is the difference between touching a few nodes and traversing the whole tree.
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.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(n) space.
Reject the mirrored maxDepth
1 + min(left, right) returns 1 for a root with a single child, because the missing side reports 0. A leaf has no children at all, and this distinction is the entire difficulty of the problem.
Prefer BFS for the early exit
Breadth-first search reaches nodes in increasing depth order, so the first leaf found is the shallowest. On a tree with one shallow leaf and one very deep branch, this touches a handful of nodes where DFS walks thousands.
Seed the queue with depth 1
Push the root paired with depth 1, since the problem counts nodes on the path rather than edges. Return 0 immediately for an empty tree, which has no path at all.
Return at the first true leaf
When a dequeued node has neither child, its depth is the answer — return at once. Testing both children is what prevents a one-child node being mistaken for a leaf.
Enqueue only existing children
Push each non-null child at depth + 1 and continue. A node with one child is not a leaf and simply extends the search rather than terminating it.
Handle the DFS version correctly if used
With recursion, take the minimum only when both children exist; with one child, return that child's depth plus one. Writing it as a plain min is the classic wrong answer.
Cost of the traversal
BFS visits nodes only down to the shallowest leaf, so it is O(n) worst case but often far less. Space is O(w) for the queue, where w is the widest level reached.
Solution & live demo
Common pitfalls
Using the max-depth recurrence with min
return 1 + min(minDepth(root.left), minDepth(root.right))
if not node.left and not node.right:
return depthFor 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
if not node.left or not node.right:
return depthif 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
# full DFS, tracking the minimum leaf depth
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).
Edge cases
Return 0 immediately, no nodes to search.
Root is dequeued first and has no children -- min depth 1.
BFS still finds the single leaf at the true bottom; a min()-based DFS would wrongly report 1.
First level with any leaf ends the search, often well before reaching every node.