Input: root = [3, 9, 20, 1, 11, 15, 7] → Output: [[3], [20,9], [1,11,15,7]]
Traverse level-by-level, alternating direction: left→right, then right→left, and so on.
TimeO(n)visit each node once
SpaceO(n)queue + result
Visited: 0/7Queue: 0Peak Q: 0
Processing
In Queue
Processed
Direction
Queue
empty
Dir
→ left-to-right
Level
[ ]
Result
[ ]
Ready
Press Play to watch BFS traverse in zigzag order, or Step to advance one operation at a time. Uses a deque for level collection with append vs appendleft to alternate direction in O(1).
This pattern cleverly uses the fact that DFS will visit level 0 first, then level 1, then level 2, etc. The condition level == len(result) is true exactly once per level—the first time that level is visited.
✎ Whiteboard
3
⌨ Type It — Iterative BFS
Practice until you don't need to look. The green highlights are the nuances to burn into memory.
# ─── ZIGZAG LEVEL ORDER — ITERATIVE (103) ───
# Pattern: BFS + direction flag
# Time: O(n) Space: O(n)
#
# 1. from collections import deque
# 2. Init: result=[], queue=deque([root])
# left_to_right = True ← direction flag!
#
# 3. BFS: while queue:
# level_size = len(queue)
# level = deque() ← deque, not list!
#
# 4. Per node: node = queue.popleft()
# if left_to_right: level.append(val)
# else: level.appendleft(val)
# enqueue children
#
# 5. result.append(list(level))
# left_to_right = not left_to_right
▼ your implementation ▼
Verify your solution:
⌨ Type It — Recursive DFS
Practice until you don't need to look. The green highlights are the nuances to burn into memory.