Binary Tree Zigzag Level Order Traversal: BFS With a Direction Flip
Solve Binary Tree Zigzag Level Order Traversal with BFS and an alternating direction flag — intuition, JavaScript code, a worked walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Plain level-order traversal reads a tree top to bottom, always left to right. Zigzag traversal keeps the top-to-bottom part but snakes across each level: row 0 left to right, row 1 right to left, row 2 left to right again, and so on down the tree.
The trap most people fall into is reversing every other level after they build it — an extra pass, extra code, and easy to get off-by-one. The clean solution never reverses anything. It runs an ordinary breadth-first search and flips a single boolean that decides whether each dequeued value gets appended or prepended.
Master this and you own the whole family of BFS-on-a-tree problems, because the only new idea here is how you write into the current level's array.
The problem
Given the root of a binary tree, return its zigzag level order traversal — the node values grouped by depth, where the direction alternates each level. The top level goes left to right, the next goes right to left, and it keeps switching.
Input: root = [3, 9, 20, null, null, 15, 7]
3
/ \
9 20
/ \
15 7
Output: [[3], [20, 9], [15, 7]]Level 0 is just [3]. Level 1's nodes in natural order are 9, 20, but this level runs right to left, so it becomes [20, 9]. Level 2's nodes are 15, 7, and direction has flipped back to left to right, so it stays [15, 7].
The brute force baseline
The intuitive first attempt: do a normal left-to-right level-order traversal, then reverse every odd-indexed level afterward.
function zigzagLevelOrder(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);
}
// second pass: flip every other row
for (let i = 1; i < result.length; i += 2) {
result[i].reverse();
}
return result;
}This is correct, but it does redundant work. You build each level in natural order and then walk half of them again to reverse. Reversing a level of w nodes costs O(w), and across the whole tree that second pass is another O(n). It also leaks the zigzag concept out of the traversal and into a cleanup loop, which is exactly the kind of two-stage logic that breaks when you tweak it. You can do the reversal while you build.
The key insight
The nodes come out of a BFS queue in the same left-to-right order at every level — that never changes. What changes is where you place each value inside the level array.
- Left-to-right level: append with
push, so values land in dequeue order. - Right-to-left level: prepend with
unshift, so each new value slides to the front and the level ends up reversed for free.
So you carry one boolean, leftToRight, and flip it after finishing each level. The queue mechanics stay identical to standard BFS; only the insert method toggles. Children are always enqueued left child then right child regardless of direction — the zigzag comes entirely from push versus unshift, not from the enqueue order.
The optimal solution
This is the algorithm the visualizer animates line by line.
function zigzagLevelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
let leftToRight = true;
while (queue.length > 0) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
if (leftToRight) {
level.push(node.val);
} else {
level.unshift(node.val);
}
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
leftToRight = !leftToRight;
}
return result;
}The levelSize = queue.length snapshot taken before the inner loop is what pins the boundary of the current level. You process exactly that many nodes, and any children pushed during the loop belong to the next level, waiting behind them in the queue. Flipping leftToRight after result.push(level) sets up the opposite direction for that next batch.
Walkthrough
Tracing root = [3, 9, 20, null, null, 15, 7]. The Insert column shows the direction-dependent write; the queue holds values in front-to-back order.
| Step | leftToRight | Node dequeued | Insert | level so far | queue after | result |
|---|---|---|---|---|---|---|
| init | true | — | — | [] | [3] | [] |
| L0 | true | 3 | push | [3] | [9, 20] | [] |
| L0 done | true → false | — | — | [3] | [9, 20] | [[3]] |
| L1 | false | 9 | unshift | [9] | [20] | [[3]] |
| L1 | false | 20 | unshift | [20, 9] | [15, 7] | [[3]] |
| L1 done | false → true | — | — | [20, 9] | [15, 7] | [[3], [20, 9]] |
| L2 | true | 15 | push | [15] | [7] | [[3], [20, 9]] |
| L2 | true | 7 | push | [15, 7] | [] | [[3], [20, 9]] |
| L2 done | true → false | — | — | [15, 7] | [] | [[3], [20, 9], [15, 7]] |
The one row that shows the trick is L1's second node. When 20 is dequeued it gets unshifted to the front, pushing the earlier 9 to index 1 — so [9] becomes [20, 9] without any explicit reverse. The queue empties after L2, the while exits, and the final result is [[3], [20, 9], [15, 7]].
Complexity
| Metric | Value | Why |
|---|---|---|
| Time (push version) | O(n) | Each of the n nodes is enqueued and dequeued exactly once; push is O(1). |
| Space | O(n) | The queue holds at most one full level — up to n/2 nodes in a wide tree — plus the O(n) result. |
One caveat on the write step: unshift on a JavaScript array is O(w) for a level of width w, because every existing element shifts over. For a tree that's O(n) overall in the worst wide level, matching the reverse-afterward approach. If you want a strict O(1) insert on right-to-left levels, use a doubly-ended structure or push to the end and reverse the single level — but for interview-scale trees the unshift form is the cleanest to write and reason about.
Common mistakes
- Reversing the enqueue order. Trying to enqueue right-then-left on flipped levels scrambles the parent-child relationships for the next level. Always enqueue left then right; only the insert into
levelchanges. - Reading
queue.lengthinside the loop. You must snapshotlevelSizebefore the inner loop. If you loop on the livequeue.length, newly enqueued children get pulled into the current level and the depth grouping collapses. - Flipping the direction at the wrong time. Toggle
leftToRightonce per level, after pushing the completed level — not per node. Flipping per node produces garbage. - Forgetting the empty-tree guard. A
nullroot should return[], not[[]]. The earlyif (!root) return []handles it before the queue is ever seeded.
Where this pattern shows up next
The BFS-with-a-per-level-array skeleton here is the backbone of most tree-traversal questions — you swap what you compute per level, keep the queue loop:
- Maximum Depth of Binary Tree — the same level loop, but you count levels instead of collecting values.
- Maximum Depth of Binary Tree - Top Down — the recursive DFS counterpart to the depth question.
- Balanced Binary Tree — depth as a subroutine, checking height differences at every node.
- Diameter of Binary Tree — post-order height tracking to find the longest path.
You can also step through the zigzag traversal interactively to watch the queue drain, the direction flip, and each level assemble one value at a time.
FAQ
How is zigzag traversal different from normal level order traversal?
Normal level order reads every level left to right and returns the values grouped by depth. Zigzag traversal groups by depth the same way but alternates direction: the first level is left to right, the second right to left, the third left to right, and so on. The traversal engine — a breadth-first search over a queue — is identical; zigzag only changes how each level's array is assembled.
Why use unshift instead of reversing every other level afterward?
Prepending with unshift builds the reversed level in a single pass as nodes are dequeued, so there's no second cleanup loop over the result. Reversing afterward works and is easy to reason about, but it's a separate O(n) pass and splits the zigzag logic into two stages. The unshift form keeps the alternating behavior inside the one BFS loop where it belongs.
Do I enqueue children left-to-right or right-to-left on flipped levels?
Always left child first, then right child, on every level regardless of direction. The enqueue order determines the natural left-to-right ordering of the next level, and you never want to disturb that. The zigzag effect comes only from choosing push versus unshift when writing a value into the current level's array — not from the order you enqueue children.
What is the time and space complexity of zigzag level order traversal?
Time is O(n): every node is enqueued and dequeued exactly once. Space is O(n) for the result plus the queue, which holds at most one full level (up to about n/2 nodes in a wide tree). The one subtlety is that unshift costs O(w) for a level of width w; if that matters, push to the end and reverse the single level instead, which keeps the overall bound the same while making the per-insert cost O(1).
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.