Pattern visualizer

Binary Tree Zigzag Level Order Traversal

The queue still discovers nodes in the same left-to-right order every time — that discovery order must never change, or parent-child relationships get scrambled. What flips is only where each dequeued value is WRITTEN: a pre-sized row plus a direction-dependent index (i, or k-1-i) places values into zigzag order directly, with no separate reversal step needed. Animated on: root = [3,9,20,null,null,15,7] — return node values grouped by level, alternating left-to-right and right-to-left each level. Expected: [[3],[20,9],[15,7]]..

Same BFS queue, a row index that flips direction each level

time O(n)space O(n)step 1 / 14

Call stack

queue: [3]direction: left-to-right

line 4

Level 0 begins with 1 node in the queue. leftToRight is true, so this level's values land front-to-back in a row of size 1.

Pseudocode

1FUNCTION zigzagLevelOrder(root):
2  queue <- [root],  leftToRight <- true,  result <- []
3  WHILE queue is not empty:
4    k <- LENGTH(queue),  row <- new array of size k
5    FOR i <- 0 TO k - 1:
6      node <- DEQUEUE(queue)
7      idx <- IF leftToRight THEN i ELSE k - 1 - i
8      row[idx] <- node.val
9      IF node.left != null: ENQUEUE(queue, node.left)
10      IF node.right != null: ENQUEUE(queue, node.right)
11    APPEND row TO result
12    leftToRight <- NOT leftToRight
13  RETURN result
14END FUNCTION

← / → step · space play · Home restart

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap