Level Order Traversal is the problem that teaches BFS on trees, and it has one line in it that everything depends on: capture the queue's size before draining the level. Miss that and you get every node in the right order but no idea where one level ends and the next begins.
The problem
Given the root of a binary tree, return its node values level by level, left to right, as a list of lists.
3
/ \ -> [[3], [9,20], [15,7]]
9 20
/ \
15 7
[] -> []
[1] -> [[1]]Note the shape of the answer. A flat list of values would be a much easier problem; the grouping is what forces you to know the level boundaries.
A queue gives you the order for free
Push the root, then repeatedly pop a node and push its children. Because children are always pushed behind everything already queued, nodes come out in exactly level order:
queue [3] pop 3 push 9, 20
queue [9, 20] pop 9 (no children)
queue [20] pop 20 push 15, 7
queue [15, 7] pop 15, pop 7That much is easy. The problem is that [3, 9, 20, 15, 7] comes out as one stream —
nothing in it says where level 1 stops.
The line that creates the levels
int levelSize = queue.size(); // BEFORE the inner loop
for (int i = 0; i < levelSize; i++) { ... }At the top of each outer iteration the queue contains exactly one complete level and nothing else. Snapshot that count, then pop precisely that many nodes — the children pushed during the loop go to the back and belong to the next level, and they do not affect a count already taken.
Writing for (int i = 0; i < queue.size(); i++) instead is the bug. The queue grows
while you drain it, so the condition is re-evaluated against a moving target and the loop takes a
partial, meaningless slice. It is a one-word difference and it fails on any tree deeper than two
levels.
Java
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<>();
if (root == null) return levels;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size(); // snapshot: one whole level
List<Integer> level = new ArrayList<>(levelSize);
for (int i = 0; i < levelSize; i++) { // NOT queue.size() -- it grows
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
levels.add(level);
}
return levels;
}
}Null children are filtered on the way in rather than on the way out. That keeps the queue holding
only real nodes, so queue.size() is genuinely the level width —
ArrayDeque would reject a null anyway, which turns the mistake into an exception rather
than a wrong answer.
The early return for a null root matters: without it the loop would push a null and dereference it. It is the only special case in the method.
Python
from collections import deque
class Solution:
def levelOrder(self, root: TreeNode) -> list[list[int]]:
if root is None:
return []
levels, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)): # len() evaluated ONCE, before the loop
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.append(level)
return levelsrange(len(queue)) is evaluated once when the loop starts, so Python gets the snapshot
for free where Java needs an explicit variable — but only because range is built
eagerly. Knowing that is the difference between it being correct and it being lucky.
Use collections.deque, not a list. list.pop(0) is O(n)
because it shifts every remaining element, which turns the whole traversal into
O(n²) — a genuine performance bug that passes every correctness test.
The recursive alternative
Levels can also be built by DFS, passing the depth down and appending into the list for that depth:
def levelOrderDfs(self, root: TreeNode) -> list[list[int]]:
levels: list[list[int]] = []
def walk(node: TreeNode, depth: int) -> None:
if node is None:
return
if depth == len(levels):
levels.append([]) # first node seen at this depth
levels[depth].append(node.val)
walk(node.left, depth + 1)
walk(node.right, depth + 1)
walk(root, 0)
return levelsIt produces the same answer, which surprises people — a depth-first walk yielding level order.
The reason is that depth indexes the destination, so ordering within a level comes from
visiting left before right, not from the traversal order overall.
Prefer BFS as the answer, because it is what the problem is teaching and because it is the one that generalises to "stop at the first level satisfying X" without walking the whole tree.
Complexity
| Time | Space | |
|---|---|---|
| BFS | O(n) | O(w), the widest level |
| DFS by depth | O(n) | O(h) stack |
For a complete tree the last level holds about half the nodes, so O(w) is
O(n) — BFS is not the cheap option on wide trees. On a degenerate tree it is the other
way round: width 1, height n. Which to prefer depends on the tree's shape, and saying
that is better than calling either one "the efficient version".
The pattern
The level-size snapshot is the reusable piece. Zigzag Level Order (103) is this with alternating direction. Right Side View (199) takes the last node of each level. Average of Levels (637) reduces each level instead of collecting it. Minimum Depth (111) returns as soon as it meets a leaf, which is where BFS genuinely beats DFS.
All five are the same loop with a different line inside it.
What the interviewer is checking
- The level-size snapshot before draining, and that you can say why.
- That children are enqueued left before right.
- Null children filtered on the way into the queue.
- The empty tree returning
[], not[[]]. dequeover a list in Python, and whypop(0)isO(n).- That
O(w)can beO(n), so BFS is not automatically the light one.