STEP 13 · BINARY TREES · DIRECTION IS A FUNCTION OF DEPTH · MEDIUM

Zigzag (Spiral) Level Order Traversal

WHAT IT SAYS

Traverse the tree level by level, but alternate direction: the first level left-to-right, the second right-to-left, and so on.

WHAT IT'S REALLY ASKING

"The zigzag is not a property of how you WALK the tree — it is a property of how you WRITE each level down. The walk can stay a plain BFS forever; the direction is just the parity of the depth, known before the level starts. So why would you ever bend the traversal when you can bend the output?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Actually traverse in alternating directions

O(n) time — but the constant is in your head, not the machine

Try to make the queue itself run backwards on odd levels — enqueue children in reversed order, or switch between two stacks that push children in opposite orders depending on the level's parity.

WHERE THE WORK IS WASTED — The two-stack dance is solving a problem that does not exist. It entangles two independent concerns — WHICH nodes form a level (a fact about the tree) and WHAT ORDER to report them (a fact about the output format) — into one fragile mechanism where the child-push order flips with parity and an off-by-one produces garbage that still looks tree-shaped. Nothing about the tree changes on odd levels; only the report does. Machinery that rebuilds the traversal to change the report is machinery you will misremember in an interview.

KEY OBSERVATION — THE UNLOCKlink

The walk is fixed; only the writing direction alternates.

Separate the two things this problem is made of, because they are genuinely independent. Thing one: grouping nodes into levels. Standard BFS does this with one idiom — snapshot the queue's size at the start of each round, and pop exactly that many nodes; those are precisely one level, because everything you push during the round is the NEXT level. This part has nothing to do with zigzag and never changes. Thing two: the direction of each level's report. Look at what determines it: level 0 goes left-to-right, level 1 right-to-left, level 2 left-to-right. It is the parity of the depth — a pure function of a counter, decided before the level is even popped, independent of the tree's contents entirely. When a requirement is a pure function of something you already know, it belongs at the OUTPUT, not in the engine. Keep the BFS untouched, and on odd levels either reverse the collected list before appending it, or — to avoid the reversal — write into a preallocated array back-to-front (index = size - 1 - position). Both are one line, and the correctness argument is one sentence: BFS delivers each level in true left-to-right order, and a reversed true order is exactly the required order. The deeper habit this trains: when a problem says 'like X, but with a twist', first ask whether the twist lives in the traversal or in the presentation. Twists of presentation are one line at the boundary. Dragging them into the engine — the two-stack version — is how a five-minute problem becomes a debugging session.

Plain BFS, flip on write

O(n) time — each node enqueued once, each level reversed once — O(w) queue space for the widest level

BFS with the level-size snapshot. Collect each level left-to-right as always. If the level index is odd, reverse the level (or fill its output slots right-to-left) before appending. Increment the level counter. That is the entire delta from ordinary level-order traversal.

WHAT YOU TRADED — The reverse costs O(level width) per odd level, which sums to at most O(n) across the tree — you pay a tiny, bounded cost at the output boundary to keep the engine completely standard. The back-to-front write avoids even that at the price of index arithmetic. The transferable lesson: keep traversal engines canonical and push formatting to the edge — the same BFS skeleton then serves level order, zigzag, right view, and level averages without modification.

WATCH THE IDEA RUN

OUTPUT SO FAR (rows written)

—

dequeue order always left → right

write direction as read

One temptation here is to try to make the traversal itself zigzag — to walk right-to-left on odd levels. Resist it. Watch what actually has to change.

step 1 / 8

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Bend the Output, Not the Engine

YOU'LL SEE IT AGAIN WHEN

The twist on a standard traversal is a pure function of the level or step index — parity, every-k-th, last-of-each — not of the data.
You can state the requirement as 'normal order, then transform each group', which means it belongs at the output boundary.
The tempted 'clever' version alters child-visit order or juggles two containers, entangling grouping with formatting.

SAME BLUEPRINT, DIFFERENT PROBLEM

Binary Tree Level Order TraversalRight View of Binary TreeReverse Odd Levels of Binary TreeAverage of Levels in Binary Tree

The bar isn't "solved it once." It's "could rebuild it from the observation."