DSA Tracker

Visualize

Binary Tree Zigzag Level Order Traversal

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

time O(n)space O(n)

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.

Details

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]].

Problem:Binary Tree Zigzag Level Order TraversalMedium

Pattern:Tree BFS and Level Order

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

step 1 / 14

9
3
15
20
7

Call stack

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

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

Every step in words

Show all 14 steps
  1. 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.
  2. Dequeue 3 (1 of 1 popped this level). idx = i = 0, so row[0] <- 3 -> [3].
  3. 3's children (9, 20) join the back of the queue for level 1 — enqueue order never flips, only the row-placement index does.
  4. Level 0 finished: [3]. result = [[3]]. Toggle direction -> right-to-left for level 1.
  5. Level 1 begins with 2 nodes in the queue. leftToRight is false, so this level's values land back-to-front in a row of size 2.
  6. Dequeue 9 (1 of 2 popped this level). idx = k-1-i = 1, so row[1] <- 9 -> [_, 9]. 9 is a leaf, so nothing new is enqueued.
  7. Dequeue 20 (2 of 2 popped this level). idx = k-1-i = 0, so row[0] <- 20 -> [20, 9].
  8. 20's children (15, 7) join the back of the queue for level 2 — enqueue order never flips, only the row-placement index does.
  9. Level 1 finished: [20, 9]. result = [[3], [20, 9]]. Toggle direction -> left-to-right for level 2.
  10. Level 2 begins with 2 nodes in the queue. leftToRight is true, so this level's values land front-to-back in a row of size 2.
  11. Dequeue 15 (1 of 2 popped this level). idx = i = 0, so row[0] <- 15 -> [15, _]. 15 is a leaf, so nothing new is enqueued.
  12. Dequeue 7 (2 of 2 popped this level). idx = i = 1, so row[1] <- 7 -> [15, 7]. 7 is a leaf, so nothing new is enqueued.
  13. Level 2 finished: [15, 7]. result = [[3], [20, 9], [15, 7]]. Queue is empty, so the traversal ends here.
  14. Zigzag level order traversal complete: [[3],[20,9],[15,7]]. Each node is dequeued and placed exactly once, so this costs O(n) time; the queue and result together hold O(n) space.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Binary Tree Zigzag Level Order Traversal in the editorAll Binary Trees problemsBack to roadmap