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.

This is Binary Tree Level Order Traversal with one slot filled differently, so the queue loop and the frozen level_size carry over unchanged. What is new is only the order in which a level's values are written down.

Separate the visiting order from the writing order

The tempting move is to make the traversal itself alternate — enqueue right child before left on flipped levels. It does not work, and understanding why is the useful part. The queue's order determines which nodes are discovered first, and therefore the left-to-right order of the next level as well. Flip the enqueue order and you flip the following level too, then the one after that, and the levels stop corresponding to anything you intended.

So keep the traversal fixed. Nodes always come out of the queue left to right; that is the queue's job and it should be left alone. Only the placement of each value into the current level's list alternates. Two independent things that are easy to conflate: the order of visiting, and the order of recording.

Placing values directly

Since level_size is known before the level starts, the level's list can be allocated at full size up front, and each value written straight into its final slot. On a left-to-right level, the i-th node pulled goes to index i. On a right-to-left level, it goes to index level_size - 1 - i — the mirror position, so the first node pulled (leftmost) lands at the far end.

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.

Worked example:root 3, children 9 and 20; 20 has children 15 and 7
- Level 0, ltr = true, n = 1. Pull 3, write it at index 0. Level [3]. Enqueue 9 then 20. Flip ltr to false.
- Level 1, ltr = false, n = 2. Pull 9 first (i = 0) and write it at index 2 - 1 - 0 = 1. Pull 20 (i = 1) and write it at index 2 - 1 - 1 = 0. Level [20, 9]. Note that 20's children were enqueued in the usual left-then-right order, as 15 then 7. Flip ltr to true.
- Level 2, ltr = true, n = 2. Pull 15 into index 0, 7 into index 1. Level [15, 7].
- Result: [[3], [20, 9], [15, 7]].

Level 1 is the instructive step: 9 was visited first but recorded last. Had we instead enqueued 20's children right-first, level 2 would have come out as [7, 15] before any flipping — the traversal would have been corrupted rather than the presentation.

Cost, and the lesson

Unchanged from level order: every node is enqueued once, dequeued once, and written once, so O(N) time and O(W) space for the queue. The alternation is free — one boolean and an index calculation.

The general point is worth keeping: when a problem asks for output in an unusual order, first check whether the traversal has to change at all, or only the presentation. Very often the exploration order is doing something you need and should not be disturbed, and the requirement can be satisfied entirely at the point where results are recorded. The same separation shows up in reverse level order (collect normally, reverse the outer list at the end) and in Binary Tree Left/Right Side View, where the traversal is untouched and only the selection rule changes.

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