Minimum Depth of Binary Tree
Mahabharata — The Nearest Leaf — How Short is the Shortest Path to a Leaf?
सबसे पास की पत्ती — कितनी दूर?। एक ओर खाली हो — दूसरी ओर जाओ॥
*The nearest leaf — how far away? If one side is empty — go the other way.*
The Story
Find the minimum depth of a binary tree (minimum number of nodes from root to nearest leaf).
A **leaf** is a node with NO children.
For tree `[3,9,20,null,null,15,7]`: min depth=2 (path 3→9 or 3→20... wait, 9 and 20 are leaves? Yes, 9 has no children → depth=2). For tree `[2,null,3,null,4,null,5,null,6]` (right-skewed chain): min depth=5 (only one leaf at the bottom).
**The key trap:** If one child is null, DON'T take min with the null side (that's not a leaf path!). Take min only between subtrees where both children exist; otherwise take the non-null side.
```java public int minDepth(TreeNode root) { if (root == null) return 0; if (root.left == null) return 1 + minDepth(root.right); // Must go right if (root.right == null) return 1 + minDepth(root.left); // Must go left return 1 + Math.min(minDepth(root.left), minDepth(root.right)); // Both exist } ```
Trace `[2,null,3,null,4,null,5,null,6]`: - At 2: left=null → 1+minDepth(3) - At 3: left=null → 1+minDepth(4) - ... continues to 6: leaf, return 1 - Total: 5 ✓ (not 1 like Math.min with null would give!)
**BFS alternative (optimal for early termination):** ```java // BFS stops at FIRST leaf encountered = minimum depth! Queue<TreeNode> q = new LinkedList<>(); q.offer(root); int depth=0; while (!q.isEmpty()) { depth++; int size=q.size(); for (int i=0;i<size;i++) { TreeNode n=q.poll(); if (n.left==null && n.right==null) return depth; // First leaf found! if (n.left!=null) q.offer(n.left); if (n.right!=null) q.offer(n.right); } } return depth; ``` BFS is better for very deep trees where the minimum leaf is near the top.
The Wrong Min-with-Null Approach
Using Math.min without null checks gives wrong answer for skewed trees. The null-check recursive is already optimal.
// WRONG: ignores null child = non-leaf path
// int minDepth(TreeNode root) {
// if (root==null) return 0;
// return 1 + Math.min(minDepth(root.left), minDepth(root.right));
// }
// For [1,2]: returns 1+min(1,0)=1 — WRONG! 2 is the only leaf, depth=2The Null-Check Min-Depth Wisdom
public int minDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null) return 1 + minDepth(root.right);
if (root.right == null) return 1 + minDepth(root.left);
return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}Step-by-Step Walkthrough
Single leaf [1]: left==null→1+minDepth(null)=1+0=1. Wait: both null. right==null check first: 1+minDepth(null)... Actually: left==null AND right==null → take right null branch: 1+0=1. ✅ (leaf has depth 1)
Deep Insight
**The classic trap:** `1 + Math.min(minDepth(left), minDepth(right))` seems right but fails when one side is null. `minDepth(null)=0` which looks like depth 0, making it seem like a shorter path exists — but null is NOT a leaf.
**BFS finds min depth faster** for wide trees: as soon as BFS encounters the first leaf, that's the minimum depth. No need to explore the rest of the tree. For trees where the minimum leaf is near the top, BFS is much faster than DFS.
**Maximum depth (tr-19) has no null-child trap:** `Math.max(left, right)` with null=0 is always correct because we want the maximum.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(h) | DFS visits all nodes in worst case |
| Optimal | O(n) | O(w) | BFS: stops at first leaf; width w ≤ n/2 for last level |
Pattern Recognition
✅ Min depth: null-child trap — don't take min with null side ✅ If one child null: return 1 + minDepth(other child) ✅ BFS stops at first leaf (better for shallow min depth) ✅ Contrast with max depth: Math.max always works **LeetCode Trigger Phrases:** → "minimum depth of binary tree" → Distance to nearest leaf → BFS for early leaf termination
Bhagavad Gita 2.20
न जायते म्रियते वा कदाचिन्नायं भूत्वा भविता वा न भूयः। अजो नित्यः शाश्वतोऽयं पुराणो न हन्यते हन्यमाने शरीरे॥
It is never born, nor does it die; it has not come into being, does not come into being, and will not come into being. It is unborn, eternal, ever-existing, and primeval. It is not slain when the body is slain.
Connection: The minimum depth seeks the shortest path to a leaf — the most direct connection between root and a terminal node. But the algorithm must be careful: an empty branch (null) is not a leaf. Like the eternal soul that is not the same as the absence of a body, a null pointer is not a leaf node. The deepest truth about a tree's minimum depth requires careful distinction between what exists (a leaf) and what is merely absent.