Overview
Zigzag level-order traversal visits a binary tree row by row, like a normal breadth-first walk, but alternates direction on each level: the first row reads left to right, the second right to left, the third left to right again.
The trap is trying to reverse the traversal itself. The clean version keeps the standard queue walk exactly as it is — always enqueue left child then right child — and only reverses the collected row before appending it. Changing the enqueue order instead corrupts the level structure, because the children of a reversed row do not come out in the order the next level needs.
How Zigzag Level-order works
- Put the root into a queue and set a direction flag to left-to-right.
- Record the current queue size — that count is exactly one level, captured before any children are added.
- Dequeue that many nodes into a row list, enqueueing each node's left child then right child as you go.
- If the direction flag says right-to-left, reverse the row list before appending it to the result.
- Flip the direction flag and repeat until the queue is empty.
When to use it
- Rendering a tree as a boustrophedon layout — org charts and tournament brackets that read back and forth.
- A standard interview variation that checks whether you understand level-boundary detection rather than memorised BFS.
- Any serialisation format that stores a tree level by level with alternating row order.
- The level-size trick generalises: it is the same technique used for level averages, right-side views and maximum-per-level.
Complexity analysis
Every node is enqueued once and dequeued once, so time is O(n). The per-level reversal touches each element at most once more across the whole traversal, so it does not change the bound. Space is O(n): the queue holds at most one level at a time, and the widest level of a balanced tree is about n/2 nodes.
Frequently asked questions
Why capture the queue size before the loop instead of checking emptiness?
Because children are being pushed onto the same queue while you drain it. Reading the size up front freezes the boundary of the current level; without it, the loop would run straight into the next level and the rows would merge.
Can a deque replace the reversal?
Yes — pushing to the front or the back of a double-ended queue depending on direction avoids the explicit reverse. It is a constant-factor improvement, not an asymptotic one, and most people find the reverse easier to read.
Does it still work on an unbalanced tree?
Yes. Levels are defined by depth, not by shape, so a tree that is a single long chain simply produces n levels of one node each — where the direction flag has no visible effect.