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 — BFS ITERATIVE ═══
PATTERN ▸ BFS + direction flag O(n) · O(n)
① INIT
result = []
queue = deque([root])
left_to_right = True
② BFS LOOP
while queue:
level_size = len(queue)
level = deque()
③ PER NODE (DIRECTION)
node = queue.popleft()
if left_to_right: level.append(val)
else: level.appendleft(val)
enqueue children
④ APPEND & FLIP
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.