LeetCode #103 Medium

Zigzag Level Order Traversal

Level order, but alternate left→right and right→left per level.

treebfs

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.

How to spot this pattern

Standard level-order plus an alternating flag — the traversal never changes, only the presentation of each finished row. That's the lazy read: don't reverse the traversal, reverse the output. Resist the urge to alternate the enqueue order, which complicates the code and gets the children's order wrong.

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

▶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

Common pitfalls

Alternating the order children are enqueued

✗ Wrong

if ltr:
    q.append(node.left); q.append(node.right)
else:
    q.append(node.right); q.append(node.left)

✓ Right

if node.left: q.append(node.left)
if node.right: q.append(node.right)
...
res.append(level if ltr else level[::-1])

Flipping the enqueue order scrambles the next level rather than reversing the current one, because each parent's children reverse locally while the parents themselves stay in order. Reverse the completed row instead — the traversal stays untouched.

Forgetting to flip the flag

✗ Wrong

res.append(level if ltr else level[::-1])

✓ Right

res.append(level if ltr else level[::-1])
ltr = not ltr

Without the toggle every level uses the same direction and the output is a plain level-order traversal. The flip is what makes it zigzag.

Using a deque and appendleft per node

✗ Wrong

if ltr: level.append(node.val)
else: level.appendleft(node.val)

✓ Right

res.append(level if ltr else level[::-1])

It works and is marginally faster, but it mixes the presentation concern into the traversal loop. Reversing once per level is clearer and the cost is the same O(n) overall.

06

Edge cases

Single-node levels

Reversing a singleton is a no-op — direction only matters visually for wide levels.

Empty tree

[].

07

Complexity

Time

O(n)

Space

O(w)

BFS + occasional list reverse.