Minimum Depth of Binary Tree
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.
Solution
Typical Recursive Solution
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
}
}
Analysis
A very general recursive way to find number of nodes in a depth
The only tricky part can be the last line
If either left
or right
is 0
, we return the opposite depth + 1 which is left + right + 1
This is because we must count nodes from root to leaf, cannot consider null leaf
as real leaf