Binary Tree Zigzag Level Order Traversal

Zigzag level-order traversal is one of the most frequently asked tree problems in coding interviews. Instead of visiting each level strictly left-to-right, you alternate directions: level 0 goes left-to-right, level 1 goes right-to-left, level 2 goes left-to-right again, and so on. This creates a “zigzag” or “spiral” pattern.

Problem statement

Given the root of a binary tree, return the zigzag level-order traversal of its nodes’ values. The first level is traversed left-to-right, the second right-to-left, and so on alternating.

LeetCode 103: Binary Tree Zigzag Level Order Traversal

Input:
         1
        / \
       2   3
      / \   \
     4   5   7

Output: [[1], [3, 2], [4, 5, 7]]

Level 0 (L→R): [1] Level 1 (R→L): [3, 2] Level 2 (L→R): [4, 5, 7]

TreeNode definition

All solutions use this standard node class:

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

Approach 1: BFS with reverse flag

The simplest approach extends standard level-order traversal. After collecting each level, check if the direction should be reversed, and if so, reverse the list.

from collections import deque

def zigzagLevelOrder(root):
    """
    BFS with a flag to reverse alternate levels.
    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 = []

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

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        # Reverse if this level should go right-to-left
        if not left_to_right:
            level.reverse()

        result.append(level)
        left_to_right = not left_to_right

    return result

Step-by-step walkthrough

Using the tree [1, 2, 3, 4, 5, null, 7]:

Step	Queue	Level collected	Direction	After reverse	Result so far
1	[1]	[1]	L→R	[1]	[[1]]
2	[2, 3]	[2, 3]	R→L	[3, 2]	[[1], [3, 2]]
3	[4, 5, 7]	[4, 5, 7]	L→R	[4, 5, 7]	[[1], [3, 2], [4, 5, 7]]

Why this works but is not optimal

The reverse operation takes O(k) where k is the number of nodes at that level. Across all levels, the total extra work is O(n). So overall time is still O(n), but we do extra work. A deque-based approach avoids this.

Approach 2: BFS with deque insertion (optimal)

Instead of collecting left-to-right and then reversing, we insert into the level list from the correct end:

• Left-to-right levels: append to the right end (normal)
• Right-to-left levels: insert at the left end (appendleft on a deque)

from collections import deque

def zigzagLevelOrder(root):
    """
    BFS with deque-based insertion — no reversal needed.
    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()

            if left_to_right:
                level.append(node.val)      # Add to right
            else:
                level.appendleft(node.val)   # Add to left

            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

The key insight: we always process children left-to-right (maintaining correct BFS order), but we control where values are placed in the output list. This avoids the O(k) reverse at each level.

Approach 3: DFS recursive

You can also solve this with DFS by tracking the level number. Each level maps to a list, and you insert at the front or back depending on parity.

def zigzagLevelOrder(root):
    """
    DFS recursive approach.
    Time: O(n)  Space: O(n) for result + O(h) recursion stack
    """
    result = []

    def dfs(node, level):
        if not node:
            return

        # Create new level list if needed
        if level >= len(result):
            result.append(deque())

        # Insert based on direction
        if level % 2 == 0:  # Left to right
            result[level].append(node.val)
        else:               # Right to left
            result[level].appendleft(node.val)

        dfs(node.left, level + 1)
        dfs(node.right, level + 1)

    dfs(root, 0)
    return [list(d) for d in result]

When to prefer DFS over BFS?

• DFS uses O(h) stack space where h is the tree height, while BFS uses O(w) where w is the maximum width
• For very wide trees (complete trees), DFS uses less memory
• For very deep trees (skewed trees), BFS uses less memory
• In interviews, BFS is more intuitive for level-order problems

Approach 4: Two-stack method

A classic approach uses two stacks to alternate the order of child processing:

def zigzagLevelOrder(root):
    """
    Two-stack approach — conceptually clear.
    Time: O(n)  Space: O(n)
    """
    if not root:
        return []

    result = []
    current_stack = [root]
    next_stack = []
    left_to_right = True

    while current_stack:
        level = []

        while current_stack:
            node = current_stack.pop()
            level.append(node.val)

            if left_to_right:
                # Push left then right (they'll come out right then left)
                if node.left:
                    next_stack.append(node.left)
                if node.right:
                    next_stack.append(node.right)
            else:
                # Push right then left
                if node.right:
                    next_stack.append(node.right)
                if node.left:
                    next_stack.append(node.left)

        result.append(level)
        left_to_right = not left_to_right
        current_stack, next_stack = next_stack, []

    return result

This approach is elegant because the stack naturally reverses order. By alternating the order of child insertion, each level comes out in the correct zigzag direction.

Complexity comparison

Approach	Time	Space	Notes
BFS + Reverse	O(n)	O(n)	Simple but extra reverse work
BFS + Deque Insert	O(n)	O(n)	Optimal, no reverse needed
DFS Recursive	O(n)	O(n + h)	Good for deep trees
Two Stacks	O(n)	O(n)	Conceptually elegant

All approaches have O(n) time since every node is visited exactly once. Space is O(n) to store the result in all cases, plus O(h) for recursion stack in DFS or O(w) for queue in BFS.

Edge cases to handle

def test_edge_cases():
    # Empty tree
    assert zigzagLevelOrder(None) == []

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

    # Left-skewed tree
    root = TreeNode(1, TreeNode(2, TreeNode(3)))
    assert zigzagLevelOrder(root) == [[1], [2], [3]]

    # Right-skewed tree
    root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
    assert zigzagLevelOrder(root) == [[1], [2], [3]]

    # Perfect binary tree
    root = TreeNode(1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, TreeNode(6), TreeNode(7))
    )
    assert zigzagLevelOrder(root) == [[1], [3, 2], [4, 5, 6, 7]]

Common mistakes

1. Forgetting to toggle the flag: Always flip left_to_right after processing each level.

2. Modifying the BFS child order: The children should always be added left-to-right to the queue. Only the output order changes. If you add children in zigzag order, the next level’s BFS will be wrong.

3. Using insert(0, val) on a list: This is O(k) per insertion. Use collections.deque with appendleft for O(1) insertion at the front.

4. Off-by-one on level parity: Decide whether level 0 is left-to-right or right-to-left and stick with it. The problem statement usually says level 0 is left-to-right.

Variation: spiral order print

Sometimes the problem asks you to print in spiral order (same as zigzag but starting from the last level). Simply reverse the final result:

def spiralOrder(root):
    """Bottom-up zigzag — useful in some interview variants."""
    zigzag = zigzagLevelOrder(root)
    return zigzag[::-1]

Variation: N-ary tree zigzag

For N-ary trees, the approach is identical — just iterate over all children instead of just left and right:

def zigzagNary(root):
    if not root:
        return []

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

    while queue:
        level = deque()
        for _ in range(len(queue)):
            node = queue.popleft()
            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)
            for child in node.children:
                queue.append(child)
        result.append(list(level))
        left_to_right = not left_to_right

    return result

Big-O analysis deep dive

Time complexity: O(n)

• Each node is visited exactly once in BFS/DFS
• Each node’s value is inserted into the result exactly once
• Deque appendleft is O(1), so no hidden linear costs

Space complexity: O(n)

• The result stores all n node values
• BFS queue holds at most one level at a time: O(w) where w is max width
• For a complete binary tree, the last level has ~n/2 nodes, so w = O(n)
• DFS recursion stack: O(h) where h is the height

Practice problems

Problem	Difficulty	Link
Binary Tree Zigzag Level Order Traversal	Medium	LeetCode 103
Binary Tree Level Order Traversal	Medium	LeetCode 102
Binary Tree Level Order Traversal II	Medium	LeetCode 107
N-ary Tree Level Order Traversal	Medium	LeetCode 429
Binary Tree Right Side View	Medium	LeetCode 199
Average of Levels in Binary Tree	Easy	LeetCode 637

Key takeaways

1. Zigzag traversal is standard BFS with controlled output direction
2. The deque insertion approach is cleanest — avoids reversing
3. Never change the BFS processing order — only change where you place values
4. This pattern extends naturally to N-ary trees and bottom-up variants
5. In interviews, start with the BFS + reverse approach (easy to explain), then optimize to deque insertion if asked