#102
Binary Tree Level Order Traversal
Medium BFS by levels
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the node values level by level, from left to right.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: values row by row.
Why this works: BFS with a queue; the queue size at the start of a round is exactly one level.
Example: 3 (9, 20 (15, 7))
[3], [9, 20], [15, 7]✦Hints open one at a time
Use a queue (BFS).
At the start of each level, the queue size tells you how many nodes belong to it.
↗Approach
While the queue isn't empty, read size = queue.size(), poll exactly that many nodes into one list, and add their children.
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size(); // freeze the level size
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode n = q.poll();
level.add(n.val);
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
res.add(level);
}
return res;
}
}!Common mistake
Using queue.size() in the for-loop condition — it changes as you add children.
Complexity
- Time: O(n).
- Space: O(w), w = maximum width.
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon