Algorithm

Binary Tree Zigzag Level Order Traversal

Trees Pattern

Binary Tree Zigzag Level Order Traversal

Return the tree's values grouped by depth, exactly as in level order, except that the reading direction alternates: the first level (the root) is read left to right, the second right to left, the third left to right again, and so on. The grouping into one list per level is required. An empty tree returns an empty list.

CONSTRAINTS
  • The number of nodes in the tree is in the range [0, 2000]
  • -100 <= Node.val <= 100
  • Level 0 (the root) is read left to right
  • Direction flips at every level boundary
EXAMPLE 1
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Level 0 holds only the root. Level 1 is reversed, so 20 precedes 9. Level 2 flips back to normal, giving 15 before 7.
EXAMPLE 2
Input: root = [1,2,3,4,5,6,7]
Output: [[1],[3,2],[4,5,6,7]]
Only odd-numbered levels are reversed. Level 1 flips to 3 before 2, then level 2 flips back to normal and reads 4,5,6,7 left to right — the direction alternates every level rather than staying reversed.
EXAMPLE 3
Input: root = [1,2,null,3]
Output: [[1],[2],[3]]
With one node per level, direction has nothing to act on, so the zigzag is invisible. A useful case for checking that a flipped direction never drops or duplicates a node.
EXAMPLE 4
Input: root = []
Output: []
No levels exist, so the direction flag is never used.
Which direction does the first level use?
Left to right. Starting with the wrong parity reverses every level and is an easy mistake — confirm it against the root's level, which looks the same either way.
Is reversing each odd level afterwards acceptable?
Yes, and it stays O(N) overall since each node is reversed at most once. It is a perfectly good answer; placing values directly is just tidier and avoids a second pass.
Does the traversal itself change direction?
No — and this is the key point. Nodes are always visited left to right; only the order they are written into the level's list changes.
Should children be enqueued in reversed order on flipped levels?
No. Reversing the enqueue order corrupts the next level's ordering, since it changes which nodes are discovered first. Keep enqueueing left then right, always.

Same grouping as a plain level-by-level read, but the reading direction alternates: level 0 left→right, level 1 right→left, level 2 left→right — a zigzag down the tree.

text
        3        ->   [3]        (L to R)
       / \
      9   20      <-   [20, 9]    (R to L)
         /  \
        15   7    ->   [15, 7]    (L to R)

We still sweep level by level with a queue exactly as in an ordinary level order — freeze the queue's size, pull that many nodes, push their children at the back. Only one thing is new: the order a level's values get written down.

Don't flip the walk — flip the writing

Tempting move: reverse the traversal on flipped levels by enqueueing right-child-before-left. It backfires. The queue's order decides which nodes are discovered first, which sets the left-to-right order of the next level too — so flipping the enqueue order corrupts every level below it. Keep the walk fixed (always enqueue left then right); alternate only where each value lands in the level's list. Visiting order and recording order are two separate things.

Place each value directly

level_size is known before the level starts, so allocate the level's list at full size and write each value straight into its final slot. Left-to-right level: the i-th node pulled → index i. Right-to-left level: → index level_size - 1 - i (the mirror slot), so the first node pulled lands at the far end.

text
level 1, right-to-left, size 2:
  pull 9  (i=0) -> slot  2-1-0 = 1
  pull 20 (i=1) -> slot  2-1-1 = 0      ->  [20, 9]
  (children still enqueued left-then-right: 15, then 7)
python
if root is None: return []
out, queue, ltr = [], deque([root]), True
while queue:
    n = len(queue)                       # frozen level size, exactly as before
    level = [None] * n                   # reserve every slot up front
    for i in range(n):
        node = queue.popleft()
        level[i if ltr else n - 1 - i] = node.val   # placement flips; traversal does not
        if node.left:  queue.append(node.left)      # ALWAYS left then right
        if node.right: queue.append(node.right)
    out.append(level)
    ltr = not ltr                        # flip for the next level
return out
Crucial Notethe direction flag flips exactly once per level, outside the inner loop. Flipping inside it alternates per node and produces a scrambled level rather than a reversed one. And ltr starts as true, because level 0 is read left to right — a parity mistake here is invisible on the root (a single node looks identical in both directions) and only shows up one level down, which makes it annoying to spot.

Building each level as a list and reversing the odd ones afterwards is equally valid and equally O(N), since each node participates in at most one reversal. Direct placement simply avoids the second pass.

Level 1 is the instructive step: 9 is visited first but recorded last. The children were still enqueued left-then-right (15, 7), so level 2 stays correct — only the presentation flipped, not the walk.

Cost, and the lesson

Same as an ordinary level order: every node enqueued, dequeued, and written once — O(N) time, O(W) queue. The alternation is free: one boolean and an index calculation.

The lesson worth keeping: when a problem wants output in an unusual order, first ask whether the traversal must change or only the presentation. Very often the exploration order is exactly what you need and shouldn't be touched — the requirement is satisfied entirely at the point where results are recorded.

Interactive Strategy Visualization

Zigzag Level Order

Alternating Directional BFS

1234567
Process Pipeline

Zigzag flips direction at each level boundary.

"Use a Deque or reverse the level list."

Strategy

Modified BFS: flip collection order using a boolean flag for cada level completion.

"Alternating directional traversal."

O(N) Time Collect Then Reverse Odd Levels
→
O(N) Time · O(W) Space Direct Placement Into Reserved Slots