Zigzag Level Order Traversal
Level order, but alternate left→right and right→left per level.
Open on LeetCode ↗02
Intuition
Don't complicate the BFS — traverse levels normally and just reverse every other level's list before appending. The zigzag is presentation, not traversal.
03
Approach
1
Plain level-order BFS
Queue with per-level size snapshot, exactly like problem 102.
2
Flip a boolean per level
Keep ltr; after each level, toggle. If not ltr, reverse the collected level (or use a deque and appendleft to avoid the reverse).
3
Cost of the reverse
Total reversal work is O(n) across all levels — free in the big-O.
04
Solution & live demo
python
▶1from collections import deque
▶2
▶3class Solution:
▶4 def zigzagLevelOrder(self, root):
▶5 if not root: return []
▶6 res, q, ltr = [], deque([root]), True
▶7 while q:
▶8 level = []
▶9 for _ in range(len(q)):
▶10 node = q.popleft()
▶11 level.append(node.val)
▶12 if node.left: q.append(node.left)
▶13 if node.right: q.append(node.right)
▶14 res.append(level if ltr else level[::-1])
▶15 ltr = not ltr
▶16 return res
05
Edge cases
Single-node levels
Reversing a singleton is a no-op — direction only matters visually for wide levels.
Empty tree
[].
06
Complexity
Time
O(n)
Space
O(w)
BFS + occasional list reverse.