Trees · LC #102
Binary Tree Level Order Traversal
Return all node values grouped by level as a list of lists. BFS with a size-snapshot per iteration naturally separates levels, making this the canonical BFS tree pattern.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level) as a list of lists.
Sample I/O
Input: [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]
Time: O(n) · Space: O(w)
Intuition
How to Think About It
Intuition
BFS naturally processes nodes level by level. The key insight is to snapshot the queue's current size before processing each level - that count tells you exactly how many nodes belong to the current level, separating it cleanly from the next.
Core Concept
Initialize queue with root. Each outer loop iteration: capture `size = queue.length`. Inner loop runs exactly `size` times, dequeuing each node, recording its value, and enqueuing its non-null children. After the inner loop, push the collected level to result.
When to use
Any problem requiring layer-by-layer processing: level averages, right-side view, zigzag traversal, minimum depth, connect next pointers.
When NOT to use
When you only need values without level grouping - a simple DFS is simpler. Also avoid when memory is tight and the tree is wide (queue holds an entire level).
Key Insights
What to Know Cold
- The size-snapshot trick is the core pattern: capture queue.length before the inner loop.
- All BFS tree variants (zigzag, right-side view, level averages) build on this exact template.
- The queue never mixes levels because children are enqueued AFTER the size snapshot.
- Maximum queue size equals the maximum width of the tree (leaf level for perfect trees).
- DFS alternative: pass depth as parameter and push to result[depth] list.
1 example
Worked Examples
Three-level tree
[3,9,20,null,null,15,7] - root, two children, two grandchildren.
Queue=[3], size=1 → level=[3], enqueue 9,20. Queue=[9,20], size=2 → level=[9,20], enqueue 15,7. Queue=[15,7], size=2 → level=[15,7].
function levelOrder(root: TreeNode | null): number[][] {
if (!root) return [];
const res: number[][] = [];
const q: TreeNode[] = [root];
while (q.length) {
const size = q.length;
const level: number[] = [];
for (let i = 0; i < size; i++) {
const node = q.shift()!;
level.push(node.val);
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
res.push(level);
}
return res;
}Output: [[3],[9,20],[15,7]]
Template for all level-order variants - memorise the size-snapshot pattern.