Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Thinking Process

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

  • Trees have no cycles — recursion is natural.
  • Combine results from left and right subtrees at each node.
  • Base case is usually null; height drives stack space.
Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2
Explanation: The minimum depth is 2, which is the path: 3 → 9.

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Explanation: The minimum depth is 5, which is the path: 2 → 3 → 4 → 5 → 6.

Constraints

  • The number of nodes in the tree is in the range [0, 10^5].
  • -1000 <= Node.val <= 1000

Key Differences from Maximum Depth

Aspect Maximum Depth Minimum Depth
Formula 1 + max(left, right) 1 + min(left, right)
Null Handling Can use max(0, depth) Must skip null children
Single Child Works with max(0, child) Must only consider non-null child
Early Termination No early exit possible BFS can stop at first leaf

Common Mistakes

  1. Empty tree: root = null → return 0
  2. Single node: root = [1] → return 1
  3. Skewed tree: [2,null,3,null,4] → return 3 (must follow the only path)
  4. Balanced tree: [3,9,20,null,null,15,7] → return 2 (shortest path: 3 → 9)

  5. One child only: [1,2,null] → return 2 (can’t use null as depth 0)

  6. Wrong null handling: Using min(minDepth(left), minDepth(right)) when one is null 
    // WRONG:
return 1 + min(minDepth(root->left), minDepth(root->right));
// If left is null, minDepth(left) = 0, min(0, right) = 0 ❌
  7. Not checking leaf: Forgetting to return 1 for leaf nodes
  8. Base case error: Returning wrong value for null node
  9. Off-by-one: Counting edges instead of nodes
  10. Missing single-child check: Not handling nodes with only one child

Key Takeaways

  • Trees have no cycles — recursion is natural.
  • Combine results from left and right subtrees at each node.
  • Base case is usually null; height drives stack space.

References

Template Reference