ZigZag Level Order Traversal

Zigzag Level Order Traversal is a classic tree question that looks tricky but is just level-order BFS with one twist: every other level is read backwards. It tests whether you can run a clean breadth-first traversal and keep one tiny piece of bookkeeping straight.

The slow way first

You could traverse the whole tree, record each node along with its depth, then sort everything into per-level buckets and reverse the odd ones. That works, but it is fiddly: you carry depths around, build a map of depth to values, then post-process. It is easy to get the reversing wrong, and you touch the data more than once.

The question to ask: can I produce each level in order, as I go, without sorting afterwards? Breadth-first search does exactly that — it naturally visits the tree one level at a time.

The idea: BFS, then flip a flag

Run a normal level-order BFS with a queue. The key trick: at the start of each level, the queue holds exactly the nodes of that level. So we record the queue's current size, pop that many nodes, and read their values into a temporary level list while enqueuing their children for the next round.

Then the twist. Keep a boolean leftToRight. When it is True, append level as-is. When it is False, reverse level first. After each level, flip the flag.

The BFS still always reads left-to-right; the zigzag is purely a presentation choice we apply per level with the flag. That keeps the traversal simple and the reversing trivial.

Walk through it

Step through the animation. Each highlighted ring is the current level coming off the queue. Watch the bottom panel: the queue empties and refills with children, the leftToRight flag flips after every level, and result grows one list at a time. On level 1 the flag is False, so [9, 20] is reversed into [20, 9] before it is appended.

Pseudocode

if the tree is empty: return []
result = empty list
queue = a queue containing just the root
leftToRight = True
while the queue is not empty:
    level = empty list
    repeat (current queue size) times:
        node = pop the front of the queue
        add node.value to level
        push node's left child if it exists
        push node's right child if it exists
    if not leftToRight: reverse level
    append level to result
    flip leftToRight
return result

The Python solution

from collections import deque
 
def zigzag_level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    left_to_right = True
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        if not left_to_right:
            level.reverse()
        result.append(level)
        left_to_right = not left_to_right
    return result

• We use a deque so popping the front (popleft) is O(1); a plain list would be O(n) per pop.
• for _ in range(len(queue)) freezes the level size before we start adding children, so we only pop the nodes that were already on this level.
• Inside the loop we always read in queue order (left-to-right) and always enqueue left child before right.
• Lines 18-19 are the whole zigzag: when left_to_right is False, we reverse the collected level before appending it.
• left_to_right = not left_to_right flips the direction for the next level.

Complexity

We touch each of the n nodes a constant number of times, so the traversal is O(n). The queue holds at most one level at a time, so in the worst case (a full bottom level) it uses O(n) space, the same as the output.

When this pattern shows up

Practice