Minimum Depth of Binary Tree — Solution

Problem

Given a binary tree, find the length of the shortest path from the root down to a leaf node — where a leaf is defined as a node with no children. This is the minimum depth: counting every node along the path, including the root and the leaf.

[3,9,20,null,null,15,7]

• Input: root = [3, 9, 20, null, null, 15, 7]
• Output: 2
• Explanation: the shortest root-to-leaf path is 3 → 9 (node 9 has no children)

A useful counter-example — a tree with only a right child at the root:

[2,null,3]

• Input: root = [2, null, 3]
• Output: 2
• Explanation: node 2 has a right child, so it is not a leaf; the only leaf is 3 at depth 2, not 1

Intuition

The minimum depth is the fewest hops to any leaf. The tricky part is that a node with only one child is not a leaf — you must keep descending into that child. This asymmetry between "one child" and "no children" is what separates correct solutions from ones that look almost right.

A recursive DFS naturally handles this case-by-case. A BFS level scan is also natural because the first leaf encountered during level-order traversal is guaranteed to be the shallowest.

Approach 1 — DFS (Recursive)

Recurse into the tree. At each node, handle three cases: only a left child (must go left), only a right child (must go right), or both children (take the minimum of the two depths).

1. If root is null, return 0.
2. If only the right child exists, return 1 + minDepth(right) — the current node is not a leaf.
3. If only the left child exists, return 1 + minDepth(left) — the current node is not a leaf.
4. If both children exist, recurse into each and return 1 + min(left_depth, right_depth).
5. If neither child exists (leaf), both earlier checks are skipped and step 4 returns 1 + min(0, 0) = 1.

1class Solution:
2    def minDepth(self, root):
3        if not root:
4            return 0
5        # Node with only a right child is not a leaf; must go right
6        if not root.left:
7            return 1 + self.minDepth(root.right)
8        # Node with only a left child is not a leaf; must go left
9        if not root.right:
10            return 1 + self.minDepth(root.left)
11        left_depth = self.minDepth(root.left)
12        right_depth = self.minDepth(root.right)
13        return 1 + min(left_depth, right_depth)

Time: O(n) — visits every node in the worst case (e.g., a right-skewed tree where the only leaf is the deepest node).

Space: O(h) — the recursion stack depth equals the tree height, which is O(log n) for balanced trees and O(n) for skewed trees.

Approach 2 — BFS (Level Order)

Scan the tree level by level. The first leaf found is the minimum-depth leaf — there is no need to continue. This avoids traversing the entire tree when the shallowest leaf is close to the root.

1. If root is null, return 0.
2. Initialize a queue with (root, 1) — the root is at depth 1.
3. Dequeue a node. If it is a leaf (no children), return its depth immediately.
4. Otherwise, enqueue existing children with depth incremented by 1.
5. Repeat until a leaf is found.

1from collections import deque
2
3class Solution:
4    def minDepth(self, root):
5        if not root:
6            return 0
7        queue = deque([(root, 1)])  # each entry is (node, depth_of_that_node)
8        while queue:
9            node, current_depth = queue.popleft()
10            # BFS guarantees this is the shallowest leaf we'll ever see
11            if not node.left and not node.right:
12                return current_depth
13            if node.left:
14                queue.append((node.left, current_depth + 1))
15            if node.right:
16                queue.append((node.right, current_depth + 1))
17        return 0

Time: O(n) worst case, but often much less — stops as soon as the first leaf is found, so a tree with a shallow leaf on the left avoids visiting the right subtree entirely.

Space: O(w) — the queue holds at most one full level of nodes, where w is the maximum width. This is O(n) for a complete binary tree's last level.

Complexity Summary

Common Mistakes

• Skipping the null-child guards and writing min(minDepth(left), minDepth(right)) + 1 directly: When one child is null, minDepth(null) returns 0, and min(depth, 0) collapses to 0 — making the function return 1 for a non-leaf node, as if the null branch were a valid path to a leaf.

• Using or instead of and for the leaf check in BFS: The correct leaf condition is node.left is None and node.right is None. Using or triggers a return for any node missing at least one child, including nodes that have exactly one child and are not leaves.

• Initializing BFS depth at 0 instead of 1: The root is at depth 1. Starting at 0 and returning current_depth when a leaf is found gives an answer one too small. Either initialize to 1 before enqueueing the root, or store depth alongside each node in the queue.

• Forgetting to handle a root with exactly one null child in DFS: Descending into a null node without a guard causes a null pointer exception. The single-child checks (if not root.left and if not root.right) must come before any recursive call on the other child.

Related Problems

• maximum-depth-of-binary-tree — the same tree traversal logic reversed to find the longest path
• balanced-binary-tree — computes heights at each node using the same recursive depth pattern
• binary-tree-level-order-traversal — the BFS level-by-level scan used in Approach 2
• diameter-of-binary-tree — combines left and right depths at each node, similar structure to the DFS approach
• path-sum — another root-to-leaf traversal that must also distinguish true leaves from single-child nodes