← ~/lc-grind/posts

#103 - Binary Tree Zigzag Level Order Traversal

November 21, 2025

Binary Tree Zigzag Level Order Traversal

Problem Description

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:


Input: root = [1]
Output: [[1]]

Example 3:


Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

Solution

1. Problem Deconstruction

Technical Reformulation: Given a binary tree’s root node, implement a level-order traversal where the direction of node value collection alternates between consecutive levels. Specifically, for level i (0-indexed):

  • If i ≡ 0 (mod 2): collect node values left-to-right
  • If i ≡ 1 (mod 2): collect node values right-to-left Return the aggregated results as a nested list where each sublist represents one level’s values in the specified directional order.

Beginner Explanation: Imagine reading a family tree where you start with the oldest ancestor, then their children, then grandchildren. Normally you’d read each generation left to right. Here, we read the first generation normally, the second generation backwards, the third normally, and so on - alternating directions with each generation.

Mathematical Formulation: Let T be a binary tree with height H. Define:

  • Lₖ = ordered sequence of nodes at depth k (0 ≤ k ≤ H)
  • Vₖ = values of nodes in Lₖ
  • Zₖ = { Vₖ if k ≡ 0 (mod 2) reverse(Vₖ) if k ≡ 1 (mod 2) } Return [Z₀, Z₁, …, Z_H]

Constraint Analysis:

  • 0 ≤ nodes ≤ 2000: Rules out exponential solutions. O(n²) is borderline (4M operations). O(n) or O(n log n) preferred.
  • -100 ≤ Node.val ≤ 100: Values fit in single bytes. No special handling for large numbers needed.
  • Empty tree (root = null): Immediate return of empty list. Critical edge case.
  • Single node tree: Base case where zigzag has no effect (only one direction).
  • Perfect vs. skewed trees: Tests queue management and memory usage.

2. Intuition Scaffolding

Real-World Metaphor: Like a sports tournament bracket where winners progress to next rounds. The first round is seeded normally (left-to-right), but the second round shows upsets (right-to-left), third round returns to expected order, creating an alternating pattern of predictability and surprise.

Gaming Analogy: Think of exploring dungeon levels in a RPG. The first floor you clear rooms left to right. The second floor has a mirror layout so you clear right to left. Each alternate floor flips your clearing pattern, requiring you to mentally reorient.

Math Analogy: Similar to evaluating a piecewise function f(x) = {x if x ∈ [0,1], 1-x if x ∈ [1,2], x-1 if x ∈ [2,3], …} where the function definition alternates between identity and reflection operations.

Common Pitfalls:

  1. Global reversal: Reversing entire result instead of individual levels
  2. Direction miscalculation: Forgetting level 0 is left-to-right (not right-to-left)
  3. Null child enqueueing: Adding null children to queue, wasting memory
  4. Level separation failure: Not distinguishing between levels in BFS
  5. Stack misuse: Using stack instead of queue for BFS, losing level ordering

3. Approach Encyclopedia

Approach 1: Dual-Stack Zigzag

# Use two stacks: current_level and next_level
# Alternate push order based on current direction
def zigzag_level_order(root):
    if not root: return []
    
    result = []
    stack_current = [root]  # Start with left-to-right
    left_to_right = True
    
    while stack_current:
        level_vals = []
        stack_next = []
        
        while stack_current:
            node = stack_current.pop()
            level_vals.append(node.val)
            
            if left_to_right:
                # Push left then right (pop order: right then left)
                if node.left: stack_next.append(node.left)
                if node.right: stack_next.append(node.right)
            else:
                # Push right then left (pop order: left then right)  
                if node.right: stack_next.append(node.right)
                if node.left: stack_next.append(node.left)
        
        result.append(level_vals)
        stack_current = stack_next
        left_to_right = not left_to_right
    
    return result

Complexity Proof:

  • Time: Each node pushed/popped exactly once → O(n)
  • Space: Two stacks hold at most width of tree → O(w) where w = max level width
  • Worst-case: Perfect binary tree → O(n/2) = O(n) space
  • Best-case: Skewed tree → O(1) space

Visualization:

Level 0: [3]           (Stack: [3])
        ↓ pop 3
Level 1: Stack_next = [9, 20] (left-to-right push)
        ↓ process stack_next in reverse: [20, 9]
Level 2: Stack_next = [7, 15] (right-to-left push)  
        ↓ process: [15, 7]

Approach 2: BFS with Level Tracking

# Standard BFS with queue, reverse alternate levels
def zigzag_level_order(root):
    if not root: return []
    
    result = []
    queue = collections.deque([root])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        level_vals = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level_vals.append(node.val)
            
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        
        if not left_to_right:
            level_vals.reverse()
        result.append(level_vals)
        left_to_right = not left_to_right
    
    return result

Complexity Proof:

  • Time: O(n) for BFS traversal + O(∑ wₖ) for reversals = O(n) + O(n) = O(n)
  • Space: Queue holds at most max level width → O(w) = O(n/2) in worst case
  • Mathematical: ∑ₖ₌₀ᴴ wₖ = n, and ∑ₖ₌₀ᴴ wₖ/2 ≤ n for reversals

Approach 3: DFS with Level Indexing

# Pre-order DFS storing nodes by level, reverse alternate levels
def zigzag_level_order(root):
    levels = []
    
    def dfs(node, depth):
        if not node: return
        
        if depth == len(levels):
            levels.append([])
        
        levels[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    
    dfs(root, 0)
    
    # Reverse odd-indexed levels
    for i in range(1, len(levels), 2):
        levels[i] = levels[i][::-1]
    
    return levels

Complexity Proof:

  • Time: O(n) DFS + O(∑ wₖ) reversals = O(n)
  • Space: O(h) recursion stack + O(n) levels storage = O(n)
  • Worst-case: Skewed tree → O(n) recursion depth

4. Code Deep Dive

Optimal Solution (BFS with Deque):

import collections

def zigzagLevelOrder(root):
    # Edge case: empty tree
    if not root:
        return []
    
    result = []
    queue = collections.deque([root])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        # Process entire level
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            # Enqueue children for next level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Reverse if right-to-left level
        if not left_to_right:
            current_level.reverse()
            
        result.append(current_level)
        left_to_right = not left_to_right
    
    return result

Line-by-Line Analysis:

  1. Line 4-5: Immediate empty tree check - handles Example 3
  2. Line 8: Deque initialization with root - starts traversal
  3. Line 9: Direction flag - level 0 starts left-to-right
  4. Line 11: level_size capture - critical for level separation
  5. Line 15: Standard BFS popleft - maintains FIFO order
  6. Line 16: Value collection - order depends on direction flag
  7. Line 19-22: Child enqueueing - always left-to-right for consistency
  8. Line 25-26: Conditional reversal - implements zigzag pattern
  9. Line 28: Direction toggle - alternates for next level

Edge Case Handling:

  • Example 1: root = [3,9,20,null,null,15,7]
    • Level 0: [3] (no reversal)
    • Level 1: [9,20] → reversed to [20,9]
    • Level 2: [15,7] (no reversal)
  • Example 2: Single node [1] → single level [[1]]
  • Empty tree: Immediate return []
  • Skewed tree: Linear levels handled naturally

5. Complexity War Room

Hardware-Aware Analysis:

  • 2000 nodes → ~16KB memory for node storage (8 bytes per node reference)
  • BFS queue peaks at tree width: worst-case ~1000 nodes → 8KB queue
  • Fits comfortably in L2/L3 cache (256KB-8MB typical)
  • Reversal operations: O(w) per level, totaling O(n) → cache-friendly sequential access

Industry Comparison Table:

Approach Time Space Readability Interview Viability
Dual-Stack O(n) O(w) 7/10 ✅ Demonstrates stack mastery
BFS + Reverse O(n) O(w) 9/10 ✅ Most intuitive, preferred
DFS + Index O(n) O(h) 8/10 ✅ Good for recursion practice
Brute Force O(n²) O(n) 6/10 ❌ Inefficient

Performance Characteristics:

  • Dual-Stack: Excellent for memory-constrained environments
  • BFS+Reverse: Best real-world performance, cache-friendly
  • DFS+Index: Good for trees with large width but small height

6. Pro Mode Extras

Variants & Extensions:

  1. Spiral Matrix Conversion
# Convert zigzag level order to spiral matrix
def tree_to_spiral_matrix(root):
    levels = zigzagLevelOrder(root)
    if not levels: return []
    
    # Flatten alternating directions
    result = []
    for i, level in enumerate(levels):
        if i % 2 == 0:
            result.extend(level)
        else:
            result.extend(reversed(level))
    return result
  1. Zigzag with Level Metadata
# Return tuples (level_values, level_depth, direction)
def zigzag_with_metadata(root):
    result = zigzagLevelOrder(root)
    return [(level, i, "left_to_right" if i % 2 == 0 else "right_to_left") 
            for i, level in enumerate(result)]
  1. Bidirectional Zigzag (Alternate starting direction)
def bidirectional_zigzag(root, start_left=True):
    # Modified version supporting configurable start direction
    if not root: return []
    
    result = []
    queue = collections.deque([root])
    left_to_right = start_left
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        
        if not left_to_right:
            current_level.reverse()
        result.append(current_level)
        left_to_right = not left_to_right
    
    return result

Interview Cheat Sheet:

  • First Mention: Always state time/space complexity upfront
  • Edge Cases: Explicitly list: empty tree, single node, skewed trees
  • Direction Logic: Clarify level 0 is left-to-right (even-indexed)
  • Optimization Path: Start with BFS+reverse, mention dual-stack as alternative
  • Testing Strategy: Test with provided examples + edge cases
  • Trade-offs: BFS+reverse vs dual-stack (readability vs memory)

Common Follow-ups:

  • “How would you handle very large trees that don’t fit in memory?”
  • “Can you implement this without using the reverse operation?”
  • “How would you modify this for an N-ary tree?”