Zigzag Level Order Traversal
Zigzag Level Order Traversal: level order, but alternate left→right and right→left per level.
- The number of nodes in the tree is in the range [0, 2000].
- -100 <= Node.val <= 100
Intuition
Zigzag level order traversal asks for the tree level by level, but with the direction alternating — the first level left to right, the second right to left, and so on. The instinct is to build a traversal that somehow changes direction as it descends, and that instinct leads to unnecessarily complicated code. Step back and notice what is actually being asked. The set of nodes on each level does not depend on direction at all; level 3 contains the same nodes whether you read it forwards or backwards. Only the order within each row differs. That means the zigzag is a presentation detail applied after the fact, not a property of the traversal itself. So run a completely ordinary level-order BFS — the same one you would write for the plain level order problem — and then: - Reverse every other level's list before adding it to the result. That is the whole solution. Keep a boolean that flips after each level, and reverse when it says to. The traversal stays untouched and obviously correct, and the alternating order becomes a one-line concern that is hard to get wrong. Trying instead to alternate the traversal direction itself means alternating the order children are enqueued, which is genuinely easy to botch and gives no advantage in either time or space.
Zigzag level order traversal of binary tree is standard level-order plus an alternating flag — the traversal never changes, only the presentation of each finished row. That's the lazy read: don't reverse the traversal, reverse the output. Resist the urge to alternate the enqueue order, which complicates the code and gets the children's order wrong.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(w) space.
Start from plain level-order BFS
Use a queue seeded with the root. At the top of each round, record size = len(queue) — the number of nodes on the current level — and dequeue exactly that many. Snapshotting the size before the loop is what separates one level from the next, since children get enqueued while you are still processing the parents.
Collect one level into a list
Dequeue size nodes, appending each value to a list for this level and enqueuing its non-null children. When the inner loop finishes, that list holds the level in natural left-to-right order, regardless of what direction the output eventually needs.
Track the direction with a boolean
Keep a flag such as left_to_right, starting true for the root's level. Flip it at the end of every level. This is the only piece of state the zigzag requires — the queue itself never learns about direction.
Reverse when the flag says so
If the flag is false, reverse the level list before appending it to the result. Reversing after collection keeps the BFS untouched and obviously correct. The alternative — enqueuing children in alternating order — changes the traversal and is far easier to get subtly wrong.
Use a deque to skip the reverse
Instead of building then reversing, append to a deque and use appendleft on right-to-left levels. This writes each value directly into its final position and avoids the reversal pass. Same asymptotic cost, marginally fewer operations, and a nice detail to mention in an interview.
Confirm the reversals are effectively free
Reversing a level of size m costs O(m), and the level sizes sum to n across the whole tree. So all the reversals together add O(n) work — the same order as the traversal itself, which is why the straightforward version is not worth optimising away.
Cost of the traversal
Every node is enqueued and dequeued once, giving O(n) time. Space is O(w) where w is the maximum width of the tree, since the queue holds at most one full level. For a complete binary tree the widest level is about n/2 nodes, so the space bound is O(n) in the worst case.
Solution & live demo
Common pitfalls
Alternating the order children are enqueued
if ltr:
q.append(node.left); q.append(node.right)
else:
q.append(node.right); q.append(node.left)if node.left: q.append(node.left) if node.right: q.append(node.right) ... res.append(level if ltr else level[::-1])
Flipping the enqueue order scrambles the next level rather than reversing the current one, because each parent's children reverse locally while the parents themselves stay in order. Reverse the completed row instead — the traversal stays untouched.
Forgetting to flip the flag
res.append(level if ltr else level[::-1])
res.append(level if ltr else level[::-1]) ltr = not ltr
Without the toggle every level uses the same direction and the output is a plain level-order traversal. The flip is what makes it zigzag.
Using a deque and appendleft per node
if ltr: level.append(node.val) else: level.appendleft(node.val)
res.append(level if ltr else level[::-1])
It works and is marginally faster, but it mixes the presentation concern into the traversal loop. Reversing once per level is clearer and the cost is the same O(n) overall.
Edge cases
Reversing a singleton is a no-op — direction only matters visually for wide levels.
[].