Problem
Given the root of a binary tree, return 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. A leaf node is a node with no left or right child.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Output
2Solution
This solution uses Breadth-First Search (BFS) with a queue. Since BFS traverses the tree level by level, the first leaf node encountered will always be at the minimum depth.Each node is added to the queue along with its current depth. When a node with no left or right child is found, its depth is returned immediately.
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
depth++;
}
return depth;
}
Complexity
In the worst case, every node may be visited before reaching the nearest leaf node, resulting in a time complexity ofO(n).
The queue may contain up to an entire level of the tree, resulting in an extra space complexity of
O(n).