Zigzag Level Order is Level Order Traversal with the direction alternating, and there are three ways to do it. Two are correct. The one people reach for first — reversing the queue — is the one that breaks, and knowing why is more interesting than the problem itself.
The problem
Return the level order traversal, but alternate direction each level: left to right, then right to left, then left to right again.
3
/ \ -> [[3], [20,9], [15,7]]
9 20
/ \
15 7
level 0 -> [3] left to right
level 1 <- [20, 9] right to left
level 2 -> [15, 7] left to rightLevel 2 is the one to check against your intuition. It is left to right again, and the children
of 20 come after nothing else — the alternation is by level, not a running reversal of
everything.
The tempting mistake
"Alternate the direction of the traversal" sounds like it should mean reversing the queue, or enqueueing children right-before-left on odd levels. Both go wrong, and the reason is worth stating: the traversal order and the output order are different things.
The queue must always be filled left to right, or the parent-child relationships that produce the next level get scrambled — a node's children must stay adjacent and in order for the following level to come out correctly. What alternates is only how you write down a level you have already collected.
So: BFS exactly as before, and reverse at the point of recording. That separation is the whole answer, and saying it before writing code is what the problem is really testing.
Two ways to record it backwards
1. collect the level, then reverse it O(w) extra work per level
2. write into a deque, addFirst on odd rows O(1) per node, no reversalThe second is nicer and is the one to reach for. A Deque lets you append at either
end in constant time, so "right to left" becomes "push each node to the front instead of the back"
— the level is built in the right order rather than fixed afterwards.
Both are O(n) overall. Reversing is not asymptotically worse, since each element is
touched a constant number of times either way. The deque version is a constant-factor improvement and
a clearer expression of the intent; say that rather than claiming it is faster in a way it is
not.
Java
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<>();
if (root == null) return levels;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int levelSize = queue.size();
// A deque so an odd level can be built back-to-front with no reversal.
Deque<Integer> level = new ArrayDeque<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (leftToRight) {
level.addLast(node.val);
} else {
level.addFirst(node.val);
}
// The QUEUE is always filled left to right. Only the output flips.
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
levels.add(new ArrayList<>(level));
leftToRight = !leftToRight;
}
return levels;
}
}Two deques doing different jobs — one is the BFS frontier, the other is the level being written.
Giving them names that say so (queue and level) is worth more than it
sounds; conflating them is how the reverse-the-queue bug gets in.
new ArrayList<>(level) converts to the required return type and copies, so the
deque can be reused conceptually per level without aliasing the stored result.
Python
from collections import deque
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> list[list[int]]:
if root is None:
return []
levels, queue = [], deque([root])
left_to_right = True
while queue:
level = deque()
for _ in range(len(queue)):
node = queue.popleft()
if left_to_right:
level.append(node.val)
else:
level.appendleft(node.val)
if node.left:
queue.append(node.left) # always left before right
if node.right:
queue.append(node.right)
levels.append(list(level))
left_to_right = not left_to_right
return levelsPython makes the simpler version tempting: collect into a list and write
level if left_to_right else level[::-1]. That is perfectly acceptable and one line
shorter — mention that you chose appendleft to avoid building a second list per level,
so the choice reads as deliberate rather than accidental.
Complexity
| Time | Space | |
|---|---|---|
| Deque, no reversal | O(n) | O(w) |
| Collect then reverse | O(n) | O(w) |
Identical bounds. The deque version does one pass per node instead of two, which is a real but constant saving.
The two-stack variant
There is a well-known version using two stacks: pop from one, push children onto the other, and swap the child order on alternate levels. It works and it is the answer some interviewers are fishing for.
It is also harder to get right, because both the pop order and the push order flip, and getting one of the two backwards produces output that is correct on a symmetric test tree and wrong on a real one. The queue-plus-deque version has a single flipping variable and one place that reads it. Prefer fewer moving parts.
The pattern
The reusable lesson is not about zigzag. It is that in a BFS, how you traverse and how you report are independent, and modifying the traversal to change the reporting is a category error. The same separation makes Right Side View (199) trivial — do not traverse differently, just record the last node of each level — and it is why 102, 103, 199 and 637 are one algorithm with four different lines inside the loop.
What the interviewer is checking
- That the queue keeps its left-to-right fill order and only the output flips.
- The level-size snapshot, carried over from problem 102.
- A single flag flipped once per level, rather than a parity test scattered around.
- That reversing is
O(n)overall too, so the deque is a constant-factor choice. - Empty tree, single node, and a three-level tree so the alternation is actually exercised.
- That you do not conflate the frontier queue with the level being built.