Minimum Depth of Binary Tree

Minimum Depth of Binary Tree

1. What is this problem about?

The Minimum Depth of Binary Tree is the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf node is a node with no children. Unlike the "Maximum Depth" (height), which is simply the longest path, the minimum depth requires finding the very first leaf you encounter.

2. Why is this asked in interviews?

This "Easy" problem is a classic at almost every major tech company, including Microsoft, Amazon, and Meta. The Minimum Depth of Binary Tree interview question tests your understanding of tree traversals and your ability to correctly identify the "leaf" condition. It also highlights the efficiency difference between Depth-First Search (DFS) and Breadth-First Search (BFS) for finding the "nearest" target.

3. Algorithmic pattern used

While both DFS and BFS can be used, BFS (Level-Order Traversal) is generally more efficient for finding the minimum depth.

• BFS: Explore the tree level by level. The first time you find a node where left == NULL and right == NULL, that node is the nearest leaf. The current level number is the minimum depth.
• DFS: Recursively find the depth of subtrees. Crucially, if a node has only one child, you must follow that child's path (you can't just return 1). This "BFS, DFS, Binary Tree interview pattern" is fundamental for any developer.

4. Example explanation

Consider a tree: 1 /
2 3
4

• Root (1) has children (2, 3).
• Node 2 is a leaf! (Depth = 2).
• Node 3 has a child 4.
• Node 4 is a leaf! (Depth = 3). The minimum depth is 2 (path 1 -> 2).

5. Common mistakes candidates make

The most common pitfall in the Minimum Depth of Binary Tree coding problem is the "one-child" case. If the root has only a left child, the minimum depth is NOT 1 (the root is not a leaf!). Many candidates incorrectly return 1 + min(depth(left), depth(right)), which yields 1 if one child is null. The correct logic must only consider non-null children unless both are null.

6. Interview preparation tip

Always remember the definition of a leaf node: "no children." For finding the "shortest" or "nearest" something in a graph or tree, BFS is usually the superior choice because it stops as soon as the target is found, whereas DFS might explore much deeper paths first. This "BFS for Shortest Path interview pattern" is a core concept to master.