Minimum Depth Binary Tree LeetCode 111

LeetCode 111 Minimum Depth of Binary Tree asks you to find the minimum depth of a binary tree — defined as the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf is a node with no children: both its left and right pointers are null.

This problem is a staple of tree traversal interviews. It tests whether you understand the difference between depth (counting nodes) and the subtlety of what constitutes a leaf. Many candidates rush to write min(left, right) + 1 without thinking about single-child nodes, leading to wrong answers on unbalanced trees.

The constraints span trees from 0 to 100,000 nodes, with values between -1000 and 1000. An empty tree (null root) has minimum depth 0. A single-node tree has minimum depth 1. These edge cases must be handled explicitly in any correct implementation.

BFS processes the tree level by level, from the root outward. The first leaf node encountered during BFS is guaranteed to be the nearest leaf — because BFS visits all nodes at depth d before visiting any node at depth d+1. There is no need to explore deeper levels once the first leaf is found.

This early termination property makes BFS strictly superior to DFS for minimum depth. On a highly unbalanced tree where the minimum depth leaf is on the left at depth 3 but the right subtree extends to depth 10,000, BFS stops at depth 3 while DFS may traverse the entire right subtree before returning the correct answer.

Early termination also has practical implications for large inputs. In competitive programming and production systems, BFS for minimum depth can save orders of magnitude of computation on pathological inputs. Always prefer BFS when you need the shortest path or earliest occurrence in a level-order sense.

The BFS approach uses a queue that stores nodes paired with their current depth. Start by enqueueing the root at depth 1. On each dequeue, check whether the current node is a leaf — that means both left and right children are null. If it is a leaf, immediately return the current depth. Otherwise, enqueue any non-null children with depth incremented by 1.

This implementation correctly handles all edge cases. An empty root is checked before the loop begins and returns 0. Single-child nodes are enqueued normally — only when both children are null does a node qualify as a leaf, triggering early return. The loop terminates as soon as the shallowest leaf is found.

Time complexity is O(n) in the worst case (a fully right-skewed tree where the minimum leaf is the last node visited), but in practice BFS terminates far earlier on balanced or left-heavy trees. Space complexity is O(w) where w is the maximum width of the tree — the maximum queue size equals the widest level.

The naive DFS formula — return min(minDepth(left), minDepth(right)) + 1 — is WRONG for trees with single-child nodes. If a node has only a left child and a null right child, the naive formula computes min(leftDepth, 0) + 1 = 0 + 1 = 1, treating the null side as a valid leaf path with depth 0. But null is not a leaf — it is the absence of a node entirely.

The correct DFS must detect the single-child case explicitly. If the left child is null, the minimum depth must go through the right subtree: return minDepth(right) + 1. If the right child is null, return minDepth(left) + 1. Only when both children exist do you take the minimum of both recursive calls.

This is the single most common mistake on LeetCode 111. Candidates who ace the BFS solution but implement the naive DFS formula will fail on test cases like [2, null, 3, null, 4] — a right-skewed tree where the naive formula returns 1 instead of the correct answer of 4.

The correct DFS builds on four cases handled in order. First, the null base case: if the current node is null, return 0 (no contribution to depth). Second, the leaf base case: if both children are null, return 1 (this node is a leaf at depth 1 relative to itself). These two cases handle the termination conditions.

Third, the single-left-child case: if only the right child is null, recurse only on the left child and return that depth plus 1. Fourth, the single-right-child case: if only the left child is null, recurse only on the right child and return that depth plus 1. Only when both children exist do you recurse on both and return the minimum plus 1.

This explicit four-case structure is verbose but unambiguous. Some implementations combine cases 3 and 4 using conditional logic, but writing them out explicitly during an interview demonstrates thorough understanding and reduces the chance of bugs from clever-but-incorrect condensing of the logic.

In Python, BFS uses collections.deque for O(1) popleft. Append (root, 1) as a tuple, popleft each iteration, check for leaf, and extend with non-null children. The DFS version uses an explicit four-case conditional: check null, check leaf, check single-child, then recurse on both. Both implementations are under 15 lines each.

In Java, BFS uses a LinkedList as a Queue storing TreeNode objects alongside their depth as a separate int array or a custom pair. The DFS implementation mirrors Python's structure with if-else chains. Java's verbosity makes the four-case DFS more natural to write fully — each case is a clear if-statement with an early return.

Both BFS and DFS run in O(n) time — every node is visited at most once. BFS uses O(w) space for the queue where w is maximum tree width. DFS uses O(h) space for the recursion stack where h is tree height. For a balanced tree, O(w) ≈ O(n/2) and O(h) ≈ O(log n), so DFS is more space-efficient on balanced inputs.

Minimum Depth (111) and Maximum Depth (104) are natural complements. Maximum depth uses DFS with max(left, right) + 1 and does not have the single-child trap because the deepest path always exists — you never mistakenly follow a null branch when maximizing. Comparing the two problems side by side solidifies your understanding of both.

Balanced Binary Tree (110) builds on max depth: a tree is balanced if the absolute difference between the max depths of left and right subtrees is at most 1 at every node. Diameter of Binary Tree (543) uses max depth as a subroutine — the diameter through a node equals left max depth plus right max depth. Mastering depth computation unlocks all three problems.

The depth family — Minimum Depth (111), Maximum Depth (104), Balanced Binary Tree (110), and Diameter (543) — forms a coherent study cluster. The recursive patterns are closely related: depth from leaves upward, combining subtree results at each node. Solve them in order and each subsequent problem becomes a natural extension of the previous.