Minimum Depth of Binary Tree

The shortest path counts only when it reaches a leaf. That one condition is what breaks the tempting min(left, right) solution.

For the stated input range, I would submit an iterative breadth-first search (BFS): visit the tree level by level and return when the first leaf appears. The recursive depth-first search (DFS) recurrence is still the best way to derive the rule and explain why it is correct.

Read the contract before choosing the traversal

The function receives the root of a binary tree and returns the number of nodes on the shortest path from the root to a leaf.

The important conditions are:

• An empty tree has depth 0.
• Depth counts nodes, not edges.
• A leaf has no left child and no right child.
• A node with only one child is not a leaf.
• The path must end at a leaf.

For this tree:

        3
       / \
      9   20
         /  \
        15   7

The path 3 → 9 reaches a leaf and contains two nodes, so the minimum depth is 2.

Now consider a one-sided tree:

2
 \
  3
   \
    4

The root has no left child, but it is not a leaf. The path must continue through the right child. The answer is 3, not 1.

That gives us the central recognition cue:

A shortest root-to-leaf problem can be solved by either aggregating valid subtree results with DFS or searching outward by depth with BFS.

The word leaf decides the details. Ignore it, and the algorithm can return a path that stops in midair.

The tempting shortcut fails

A natural recurrence is:

return 1 + min(min_depth(node.left), min_depth(node.right))

This is wrong when one child is missing.

Take the smallest counterexample:

    2
     \
      3

If an empty subtree returns depth 0, the formula computes:

1 + min(0, 1) = 1

But the root is not a leaf. The only valid path is 2 → 3, whose depth is 2.

The bug is subtle but fundamental: an empty subtree is useful as a recursion base case, but it is not a valid path to a leaf. It must not compete with a real child subtree.

At every non-empty node, the algorithm has two obligations:

1. Count the current node.
2. Continue through a child that can actually lead to a leaf.

Therefore:

• If both children exist, compare their depths.
• If only one child exists, follow that child.
• If neither child exists, the current node is a leaf.

This is the difference between calculating a small number and calculating a valid answer.

Derive the DFS recurrence

Define:

min_depth(node)

as the number of nodes on the shortest path from node to a leaf in that subtree.

Derive the cases directly from that definition.

Empty subtree

If node is empty:

min_depth(None) = 0

This terminates the recursion. The value 0 does not mean that an empty subtree is a leaf path.

Leaf

If the node has no children, the path contains only that node:

min_depth(leaf) = 1

Exactly one child

If the left child is missing, every valid path must go right:

min_depth(node) = 1 + min_depth(node.right)

If the right child is missing, every valid path must go left:

min_depth(node) = 1 + min_depth(node.left)

Two children

If both children exist, both sides contain valid paths to leaves:

min_depth(node) = 1 + min(
    min_depth(node.left),
    min_depth(node.right)
)

The + 1 counts the current node.

The complete decision table is:

Node shape	Return value
Empty node	0
Leaf	1
Left child only	1 + left_depth
Right child only	1 + right_depth
Both children	1 + min(left_depth, right_depth)

The useful invariant is:

Every positive depth returned by min_depth describes a path that ends at a real leaf.

That invariant tells us when min() is legal. It is legal only when both child results represent valid paths.

Prove the recurrence

We can prove the recurrence by considering every possible shape of the current subtree.

• For an empty subtree, returning 0 matches the base definition.
• For a leaf, returning 1 counts the only node on the path.
• For a node with one child, every root-to-leaf path must use that child. Adding 1 to the child's minimum depth is exact.
• For a node with two children, every valid path belongs to either the left subtree or the right subtree. Taking the smaller valid depth selects the shortest path, and adding 1 counts the current node.

These cases cover every binary-tree node. Therefore, the recurrence returns the minimum depth for the entire tree.

The proof exposes the implementation rule: missing children affect which branch is valid before they affect any numeric comparison.

Trace the recurrence on an example

For the tree:

        3
       / \
      9   20
         /  \
        15   7

Evaluate from the leaves upward:

1. Node 9 is a leaf, so it returns 1.

2. Nodes 15 and 7 are leaves, so they each return 1.

3. Node 20 has two children:

   1 + min(1, 1) = 2
   

4. Node 3 compares the left depth 1 with the right depth 2:

   1 + min(1, 2) = 2
   

The result is 2.

For the right-only chain:

2
 \
  3
   \
    4
     \
      5

Node 5 returns 1. Node 4 has only a right child, so it returns 2. The same rule continues upward until node 2 returns 4.

At no point does a missing left child become a candidate path.

The recursive Python implementation

This version maps directly to the recurrence:

from typing import Optional


class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        if root.left is None:
            return 1 + self.minDepth(root.right)

        if root.right is None:
            return 1 + self.minDepth(root.left)

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

Each branch has a precise job:

• root is None handles the empty subtree.
• root.left is None forces the path through the right subtree.
• root.right is None forces the path through the left subtree.
• The final branch means both children exist, so min() is safe.

I prefer this explicit branching in an interview. A compressed expression may be shorter, but it hides the exact condition that prevents the classic bug. The extra lines make the invariant visible.

You can also write the leaf case explicitly:

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        if root.left is None and root.right is None:
            return 1

        if root.left is None:
            return 1 + self.minDepth(root.right)

        if root.right is None:
            return 1 + self.minDepth(root.left)

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

The two versions are equivalent. The explicit leaf branch can make the definition easier to explain while you are learning the pattern.

Why BFS is the safer submission for the stated constraints

The problem allows a tree with up to 10^5 nodes. A highly skewed tree can have height n, so recursive DFS may create one Python call frame per node. The recurrence remains correct, but the implementation now depends on recursion depth for a valid input shape.

BFS avoids that recursive call stack and matches the shortest-path interpretation directly:

1. Process the root.
2. Process every node at depth 2.
3. Process every node at depth 3.
4. Stop at the first leaf.

Because BFS processes levels in increasing order, the first leaf it encounters has minimum depth. No deeper leaf can be a better answer because every shallower level has already been processed.

Use a queue whose entries store:

(node, depth)

When removing an entry:

• If the node is a leaf, return its depth.
• Otherwise, enqueue its existing children with depth increased by 1.

The iterative Python solution is:

from collections import deque
from typing import Optional


class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

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

        while queue:
            node, depth = queue.popleft()

            if node.left is None and node.right is None:
                return depth

            if node.left is not None:
                queue.append((node.left, depth + 1))

            if node.right is not None:
                queue.append((node.right, depth + 1))

        return 0

The final return 0 is unreachable for a valid non-empty tree, because every finite tree has a leaf. It keeps the function structurally complete.

The queue has one clear obligation: it stores nodes in nondecreasing depth order. That ordering is what makes the first discovered leaf the answer.

For the canonical example, the queue evolves like this:

Removed node	Depth	New queue contents
3	1	(9, 2), (20, 2)
9	2	—

Node 9 is the first leaf removed, so BFS returns 2 without exploring the deeper subtree below 20.

Complexity

Let n be the number of nodes and h the tree height.

Recursive DFS

Every node is visited at most once:

• Time: O(n)
• Auxiliary space: O(h) for the recursion stack

A skewed tree can make h = n, so the worst-case auxiliary space is O(n).

Iterative BFS

BFS also visits each node at most once:

• Time: O(n)
• Auxiliary space: O(w), where w is the maximum number of nodes held in one level

In the worst case, w can be O(n). The tradeoff is operational: BFS avoids recursive stack depth and may stop as soon as it finds the nearest leaf.

For Python and the given maximum input size, iterative BFS is the more dependable implementation choice. DFS is the cleaner recurrence; BFS is the safer execution strategy.

Edge cases that expose incorrect solutions

Test the tree shapes that challenge the contract:

Case	Expected behavior
Empty tree	Return 0
Single-node tree	Return 1
Root with only a left child	Continue left
Root with only a right child	Continue right
Shallow leaf beside a deeper subtree	Return the shallow leaf's depth
Completely skewed tree	Count every node in the chain

The smallest debugging test for the common min() mistake is:

    1
     \
      2

A naive implementation may return 1 by treating the missing left subtree as the winner. The correct result is 2.

Before submitting, ask:

• Am I counting nodes rather than edges?
• Does an empty tree return 0?
• Does a single-node tree return 1?
• Can a node with one child be mistaken for a leaf?
• Do I call min() only when both child subtrees are valid candidates?
• If I use recursion, can the input height exceed a safe recursion depth?
• If I use BFS, does the queue preserve increasing depth order?

The transferable move is simple: when a recursive tree problem asks for the shortest path to a leaf, define exactly what a subtree result means, then make invalid branches ineligible before comparing values.

Read the leaf condition. Name the invariant. Test the one-child tree. That sequence catches the bug before the judge does.