Binary Tree Level Order Traversal
Problem Statement
Given the root of a binary tree, return the values of its nodes level by level from top to bottom, and from left to right within each level.
Input
The root of a binary tree, usually shown in level order such as [3,9,20,null,null,15,7].
Output
A list of lists where each inner list contains the node values from one level of the tree.
Constraints
- •
0 <= number of nodes <= 2000 - •
-1000 <= Node.val <= 1000
Examples
Example 1
root = [3,9,20,null,null,15,7]
[[3],[9,20],[15,7]]Example 2
root = [1]
[[1]]Example 3
root = []
[]Learning Objectives
- Recognise the level-sweep signal in binary tree prompts.
- Use a queue to preserve left-to-right breadth-first order.
- Process exactly the current queue size so each output list represents one level.
- Use the base BFS template that zigzag, right-side view, and level aggregates specialise.
Intuition
Pattern Recognition
The signal is any tree prompt that asks for nodes level by level, top to bottom, breadth first, or asks you to do something once per depth. Depth-first recursion is good for subtree answers, but this problem cares about horizontal layers. A queue naturally stores the frontier in the same order we should visit it.
The common trap is letting levels bleed together. If you keep polling until the queue is empty, newly enqueued children are processed in the same pass as their parents. The fix is the canonical BFS template: record the queue size at the start of a level, process exactly that many nodes, and enqueue their children for the next level.
Common mistakes
- ×Using one flat list and losing where each level starts and ends.
- ×Looping until the queue is empty inside a level, which mixes children into the parent level.
- ×Forgetting to return an empty list when **root** is **null**.
- ×Enqueuing right before left when the required output is left-to-right.
Algorithm Explanation
Key idea
The queue represents the next nodes to process in breadth-first order. At the start of each outer loop, the queue contains exactly one full level. Save that size, remove exactly those nodes, collect their values, and enqueue their non-null children. After those fixed removals, the queue contains exactly the next level.
Level-by-level walkthrough
Use the tree [3,9,20,null,null,15,7]. Start with queue [3]. The level size is 1, so remove only 3, collect [3], and enqueue its children 9 and 20. The queue becomes [9,20] for the next level.
Now the level size is 2. Remove 9 first, collect it, and enqueue no children. Remove 20, collect it, and enqueue 15 then 7. The level output is [9,20], and the queue for the next round is [15,7].
The last level size is 2. Remove 15 and 7, collect [15,7], and enqueue no children. The queue is empty, so the traversal ends with [[3],[9,20],[15,7]].
Algorithm
- Create an empty answer list.
- If root is null, return the empty answer.
- Add root to a queue.
- While the queue is not empty, store levelSize = queue.size().
- Poll exactly levelSize nodes, append their values to the current level, and enqueue their left child then right child when present.
- Append the completed level list to the answer.
- Return the answer after all levels are processed.
Solutions
Solution: Queue BFS by fixed level size
Use this as the default template for binary tree BFS. It is simple, iterative, and keeps each level separated without storing depth on every node.
Run breadth-first search with a queue. Before processing a level, snapshot the current queue size; those nodes are the entire current level, while any children enqueued during the loop belong to the next level.
Step-by-step
- Return an empty list when root is null.
- Add root to the queue.
- While the queue has nodes, save the current queue size as levelSize.
- Poll exactly levelSize nodes, add each value to a fresh level list, and enqueue children left-to-right.
- Add level to the answer and continue until the queue is empty.
O(n)
O(width)
Every node is visited once, and the queue holds at most one level plus part of the next level.
Java implementation
Dry Run
Sample input
root = [3,9,20,null,null,15,7]. Track the queue at the start of each level and the answer after that level is completed.
| level | queue before level | nodes processed | level output | result so far |
|---|---|---|---|---|
| 0 | [3] | 3 | [3] | [[3]] |
| 1 | [9,20] | 9, 20 | [9,20] | [[3],[9,20]] |
| 2 | [15,7] | 15, 7 | [15,7] | [[3],[9,20],[15,7]] |
Each row processes exactly the queue size captured at the start of that level. Children are saved for the following row, which keeps the level boundaries clean.
Interview Tips
Say the invariant before coding: at the start of the outer loop, the queue contains the current level. Then save queue.size() and process exactly that many nodes. This one sentence prevents the most common bug and sets up every BFS follow-up in this module.
Likely follow-ups
- How would you print the same levels from bottom to top?
- How would you return the largest value on each level?
- How would you include **null** placeholders to preserve the exact tree shape?
- How would this change for an n-ary tree?
Similar Problems
Key Takeaways
- Level-order traversal is the base BFS pattern for binary trees.
- Snapshot **queue.size()** before the inner loop to isolate one level.
- Enqueue children left-to-right to preserve the required output order.
- Most tree BFS variants keep this skeleton and change what is collected per level.