15. Minimum Depth of Binary Tree
easyAsked at ExpediaFind the depth of the shallowest leaf in a binary tree.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
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.
Constraints
Number of nodes in [0, 10^5]-1000 <= Node.val <= 1000
Examples
Example 1
Input
root = [3,9,20,null,null,15,7]Output
2Example 2
Input
root = [2,null,3,null,4,null,5,null,6]Output
5Approaches
1. DFS all leaves
DFS, collect all leaf depths, take min.
- Time
- O(n)
- Space
- O(h)
let best=Infinity; function dfs(n,d){if(!n)return;
if(!n.left&&!n.right){best=Math.min(best,d);return;}
dfs(n.left,d+1);dfs(n.right,d+1);} dfs(root,1);Tradeoff:
2. BFS early exit
BFS level by level, return first leaf depth. Expedia uses BFS for shortest-itinerary lookups against destination graphs.
- Time
- O(n)
- Space
- O(n)
function minDepth(root) {
if (!root) return 0;
const q = [[root, 1]];
while (q.length) {
const [n, d] = q.shift();
if (!n.left && !n.right) return d;
if (n.left) q.push([n.left, d + 1]);
if (n.right) q.push([n.right, d + 1]);
}
}Tradeoff:
Expedia-specific tips
Expedia interviewers favor BFS here because early-exit is huge; the analogy is shortest connecting-flight path through hub airports.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.