Zigzag Level Order Traversal — BFS with Deque in Python

Zigzag Level Order Traversal (LeetCode 103) asks you to traverse a binary tree level by level, but alternating direction each level — left-to-right, then right-to-left, then left-to-right again. It is a classic BFS variation that appears frequently in interviews.

The Problem

Given a binary tree, return its zigzag level order traversal — the values of nodes at each level, alternating between left-to-right and right-to-left.

        3
       / \
      9   20
         / \
        15   7

Output: [[3], [20, 9], [15, 7]]

Level 0 (L→R): [3]
Level 1 (R→L): [20, 9]
Level 2 (L→R): [15, 7]

Why Not Just Reverse?

A naive approach: do a normal level order BFS, then reverse every other level. This works, but it adds O(n) work for reversals. A cleaner approach uses a deque and toggles which end we append to — no reversal needed.

Approach: BFS with Deque

The key insight: instead of reversing after collecting a level, we control where we insert each node’s value.

• Left-to-right level: append values to the right of the level deque
• Right-to-left level: append values to the left of the level deque

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzagLevelOrder(root):
    """
    Zigzag level order traversal using BFS + deque.
    Time: O(n), Space: O(n)
    """
    if not root:
        return []

    result = []
    queue = deque([root])
    left_to_right = True

    while queue:
        level_size = len(queue)
        level = deque()

        for _ in range(level_size):
            node = queue.popleft()

            # Toggle insertion direction
            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)

            # Always enqueue children left then right
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(list(level))
        left_to_right = not left_to_right

    return result

Step-by-Step Trace

Using the tree [3, 9, 20, null, null, 15, 7]:

Step 1: queue = [3], left_to_right = True
  Process 3 → level.append(3) → level = [3]
  Enqueue: 9, 20
  Result: [[3]]

Step 2: queue = [9, 20], left_to_right = False
  Process 9 → level.appendleft(9)  → level = [9]
  Process 20 → level.appendleft(20) → level = [20, 9]
  Enqueue: 15, 7
  Result: [[3], [20, 9]]

Step 3: queue = [15, 7], left_to_right = True
  Process 15 → level.append(15) → level = [15]
  Process 7  → level.append(7)  → level = [15, 7]
  Result: [[3], [20, 9], [15, 7]]

Alternative: Simple Reverse Approach

If you find the deque method hard to remember under pressure, the reverse approach is perfectly valid:

def zigzagLevelOrder_reverse(root):
    """Simpler but slightly less elegant — reverse odd levels."""
    if not root:
        return []

    result = []
    queue = deque([root])
    level_num = 0

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        if level_num % 2 == 1:
            level.reverse()
        result.append(level)
        level_num += 1

    return result

Both are O(n) time and O(n) space. The deque approach avoids the in-place reverse but both are accepted in interviews.

Complexity Analysis

Metric	Value
Time	O(n) — visit each node exactly once
Space	O(n) — queue holds at most one full level (up to n/2 nodes at leaf level)

Edge Cases

# Empty tree
assert zigzagLevelOrder(None) == []

# Single node
root = TreeNode(1)
assert zigzagLevelOrder(root) == [[1]]

# Left-skewed tree: 1 → 2 → 3
# Each level has one node, so zigzag has no visible effect
# Output: [[1], [2], [3]]

# Right-skewed tree: same behavior

When to Use This Pattern

Use zigzag BFS when:

• The problem asks for spiral or zigzag traversal of a tree
• You need level-order output but with alternating direction
• You see “snake order” or “S-shaped traversal” in the problem statement

The deque-based direction toggling generalizes nicely: you can extend it to n-ary trees, or any graph where you want alternating-direction BFS layers.

Common Mistakes

1. Forgetting to toggle left_to_right after each level
2. Reversing children enqueue order — always enqueue left then right; only change where you insert the value
3. Off-by-one on level numbering — level 0 is left-to-right by convention

Related Problems

Problem	Key Difference
Binary Tree Level Order (LC 102)	Standard BFS, no zigzag
Binary Tree Right Side View (LC 199)	Only last node per level
N-ary Tree Level Order (LC 429)	Multiple children per node
Binary Tree Vertical Order (LC 314)	Columns instead of rows
Spiral Matrix (LC 54)	Same zigzag idea on 2D grids

Key Takeaways

• Zigzag level order is a BFS problem with a twist: alternate the insertion direction per level
• Using a deque for each level and toggling append vs appendleft avoids post-processing reversal
• Both approaches (deque toggle and simple reverse) are O(n) and interview-valid
• The pattern generalizes to any “alternating direction by layer” traversal