Binary Tree Level Order Traversal: The BFS Queue Pattern
Traverse a binary tree level by level with a BFS queue. Intuition, a worked walkthrough, JavaScript code, complexity analysis, and the levelSize trick explained.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Most tree problems you meet first are solved with recursion that dives straight to the bottom. Level order traversal refuses to. It walks the tree the way you'd read a org chart — the CEO, then every VP, then every director — one horizontal slice at a time.
That "one slice at a time" requirement is exactly what a queue is built for. Get comfortable with the pattern here and you've learned the engine behind shortest-path BFS, right-side views, zigzag traversal, and minimum-depth checks. They're all the same loop with a different thing pushed into the result.
The problem
Given the root of a binary tree, return its level order traversal: a list of levels, where each level is a list of the node values from left to right at that depth.
Input:
3
/ \
9 20
/ \
15 7
Output: [[3], [9, 20], [15, 7]]Two things in that output shape the solution:
- The result is a list of lists, not one flat array. You have to know where each level ends.
- Within a level, order is left to right — the order in which you enqueue children has to be preserved exactly.
The brute force baseline
You could avoid a queue. Compute the height of the tree, then run one depth-limited walk per level, collecting only the nodes that sit at that exact depth.
function levelOrder(root) {
const height = getHeight(root);
const result = [];
for (let depth = 0; depth < height; depth++) {
const level = [];
collectAtDepth(root, depth, level);
result.push(level);
}
return result;
}
function collectAtDepth(node, depth, level) {
if (!node) return;
if (depth === 0) { level.push(node.val); return; }
collectAtDepth(node.left, depth - 1, level);
collectAtDepth(node.right, depth - 1, level);
}It returns the right answer, but it re-walks the tree from the root once for every level. A tree of height h gets traversed h times, and each traversal revisits every ancestor of the target level. For a skewed tree that's O(n²) — you touch the top nodes again and again just to reach the bottom row. There's a way to visit each node exactly once.
The key insight: process one level, then the next
A queue naturally holds nodes in the order you'll visit them. If you always add children to the back and remove from the front (FIFO), nodes come out top-to-bottom, left-to-right — which is level order for free.
The one wrinkle: you need to know where a level ends. The trick is to snapshot the queue length before you start draining a level:
levelSize = queue.length // exactly the nodes at this depthAny children you enqueue while processing those levelSize nodes belong to the next level. By looping exactly levelSize times, you drain the current level cleanly and leave the next level sitting in the queue, ready to go. That single line is what separates level order from a plain flat BFS.
The optimal solution
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}The outer while runs once per level. The inner for runs levelSize times — one dequeue per node at this depth. Push the left child before the right child so left-to-right order survives. When the queue empties, every node has been visited and every level is in result.
Walkthrough
Tracing root = [3, 9, 20, null, null, 15, 7]. The queue is shown front-to-back; levelSize is captured at the top of each while iteration.
| Step | Action | queue (front → back) | levelSize | level | result |
|---|---|---|---|---|---|
| 1 | init | [3] | — | — | [] |
| 2 | start level 0 | [3] | 1 | [] | [] |
| 3 | dequeue 3, push 9, 20 | [9, 20] | 1 | [3] | [] |
| 4 | level 0 done | [9, 20] | 1 | [3] | [[3]] |
| 5 | start level 1 | [9, 20] | 2 | [] | [[3]] |
| 6 | dequeue 9 (no children) | [20] | 2 | [9] | [[3]] |
| 7 | dequeue 20, push 15, 7 | [15, 7] | 2 | [9, 20] | [[3]] |
| 8 | level 1 done | [15, 7] | 2 | [9, 20] | [[3], [9, 20]] |
| 9 | start level 2 | [15, 7] | 2 | [] | [[3], [9, 20]] |
| 10 | dequeue 15, dequeue 7 | [] | 2 | [15, 7] | [[3], [9, 20]] |
| 11 | level 2 done | [] | 2 | [15, 7] | [[3], [9, 20], [15, 7]] |
| 12 | queue empty → return | [] | — | — | [[3], [9, 20], [15, 7]] |
Watch step 5. When we enter level 1, 9 and 20 are already sitting in the queue — they were enqueued back in step 3 while we processed level 0. Snapshotting levelSize = 2 there tells the inner loop to drain exactly those two, so the 15 and 7 they add land in level 2 instead of leaking into level 1.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Depth-by-depth recursion | O(n²) | O(h) | re-walks ancestors once per level; worst case skewed |
| BFS with a queue | O(n) | O(n) | each node enqueued and dequeued exactly once |
Every node enters and leaves the queue a single time, and does O(1) work in between, so time is O(n). Space is the queue itself: at its peak it holds one full level, and the widest level of a balanced tree has up to n/2 nodes — so O(n) in the worst case. h in the recursion column is the tree height.
Common mistakes
- Forgetting to snapshot
levelSize. Readingqueue.lengthinside the loop condition means it grows as you enqueue children, and every node collapses into one giant "level." Capture the count before the inner loop. - Pushing right before left. The queue preserves insertion order; enqueue left first or your levels come out mirror-reversed.
- Not handling an empty tree. If
rootisnull, return[]immediately — otherwisequeue = [root]seeds the queue withnulland you dereference it. - Using
queue.shift()and calling it O(1). In JavaScript, arrayshift()is O(n) because it re-indexes. For huge trees, track a head pointer or use a real deque to keep the traversal genuinely O(n). - Recording
nullchildren. Only enqueue a child when it exists; pushingnullplaceholders pollutes both the queue and the level arrays.
Where this pattern shows up next
This is the same tree, walked in different orders. Compare the queue-based BFS here against the stack- and recursion-based depth-first traversals:
- Binary Tree Preorder Traversal — root, then left subtree, then right, via recursion.
- Binary Tree Inorder Traversal — left, root, right — the order that sorts a BST.
- Binary Tree Preorder Traversal - Iterative — the same preorder with an explicit stack instead of the call stack.
- Binary Tree Inorder Traversal - Iterative — inorder unrolled into a manual stack loop.
You can also step through level order traversal interactively to watch the queue fill and drain one level at a time.
FAQ
Why does level order traversal use a queue instead of a stack?
A queue is first-in-first-out, so nodes leave in the same order they arrived — top to bottom, left to right — which is exactly level order. A stack is last-in-first-out, so the most recently pushed child comes out first, sending you deep down one branch before finishing a level. That LIFO behavior is what powers depth-first traversals like preorder; BFS needs the FIFO discipline a queue provides.
What is the time and space complexity of BFS level order traversal?
Time is O(n): each of the n nodes is enqueued once, dequeued once, and does constant work in between. Space is O(n) in the worst case, because the queue can hold an entire level, and the widest level of a balanced tree contains up to n/2 nodes. One caveat: JavaScript's Array.shift() is O(n) under the hood, so a naive queue.shift() can quietly make the whole traversal O(n²) on very large inputs.
How does the levelSize variable separate one level from the next?
Before draining a level, you record levelSize = queue.length. At that moment the queue holds exactly the nodes at the current depth. The inner loop runs precisely that many times, so it removes only the current level's nodes. Any children enqueued during those iterations stay in the queue for the next outer pass, cleanly forming the next level. Without that snapshot, newly added children get mixed into the level you're still building.
How do I return a flat list instead of a list of levels?
Drop the per-level bookkeeping entirely. Skip the levelSize snapshot and the inner level array, and just push node.val straight into a single flat result while you dequeue. That gives you a plain BFS order — all node values top-to-bottom, left-to-right, in one array. The list-of-lists structure exists only because this specific problem asks you to group values by depth.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.