Binary Tree Zigzag Level Order Traversal — Solution

Problem

Traverse a binary tree level by level, but alternate the direction each time: left-to-right for the first level, right-to-left for the second, left-to-right for the third, and so on. Return each level's values as a separate list.

[3,9,20,null,null,15,7]

• Input: root = [3, 9, 20, null, null, 15, 7]
• Output: [[3], [20, 9], [15, 7]]
• Explanation: Level 0 is read left-to-right, level 1 is reversed to [20, 9], level 2 is read left-to-right again.

To see why order matters: for the two-level tree [1, 2, 3], a standard BFS gives [[1], [2, 3]], but zigzag gives [[1], [3, 2]] — the second level is flipped.

Intuition

This is standard BFS level order traversal with one twist: for odd-numbered levels, you need the values in reverse. The key insight is that instead of collecting values in a plain list and reversing it afterward, you can use a deque (double-ended queue) as the bucket for each level — appending to the right for even levels and prepending to the left for odd levels. That way you build the correctly-ordered level in a single pass, without a separate reversal step.

Solution — BFS with Per-Level Deque

Process the tree with BFS using a queue. For each level, insert node values into a deque from the appropriate end depending on the level's direction. Children are always enqueued left-to-right so the BFS order stays consistent.

1. Return early if root is null.
2. Initialize a BFS queue with the root and a left_to_right flag set to True.
3. While the queue is non-empty, snapshot the current level size so you process exactly one level per iteration.
4. For each node in the level, add its value to the right of the deque (left-to-right) or the left of the deque (right-to-left), then enqueue its left and right children.
5. Convert the deque to a list and append it to the result.
6. Flip the direction flag before moving to the next level.

1from collections import deque
2from typing import Optional, List
3
4def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
5    if not root:
6        return []
7
8    result = []
9    bfs_queue = deque([root])
10    left_to_right = True
11
12    while bfs_queue:
13        level_size = len(bfs_queue)
14        current_level = deque()  # supports O(1) append to either end
15
16        for _ in range(level_size):
17            node = bfs_queue.popleft()
18
19            if left_to_right:
20                current_level.append(node.val)        # build left-to-right
21            else:
22                current_level.appendleft(node.val)    # prepend to reverse order
23
24            if node.left:
25                bfs_queue.append(node.left)
26            if node.right:
27                bfs_queue.append(node.right)
28
29        result.append(list(current_level))
30        left_to_right = not left_to_right  # flip direction for next level
31
32    return result

Time: O(n) — every node is enqueued and dequeued exactly once.

Space: O(n) — the BFS queue holds at most one full level, which in a complete binary tree is n/2 nodes.

Complexity Summary

Common Mistakes

• Reversing child enqueue order instead of reversing values — BFS must always enqueue left child before right child. The zigzag effect comes from how you insert collected values, not from which children you visit first. Swapping enqueue order corrupts the structure of subsequent levels.
• Reading len(result) after appending to get level parity — if you check len(result) % 2 after calling result.append(...), the parity is wrong for every level. Snapshot the level index before appending, or use a separate boolean flag.
• Using a list instead of a deque for the current level — a list has O(k) insert(0, val) cost for every prepend. On a skewed tree this makes the total work O(n²). A deque's appendleft is O(1).
• Forgetting to snapshot level_size before the inner loop — if you loop on while queue, new children added during the loop bleed into the current level, producing malformed output.
• Off-by-one on the direction flag — starting with left_to_right = False inverts all levels. Level 0 (the root alone) should always be left-to-right.

Related Problems

• binary-tree-level-order-traversal — the same BFS structure without the direction flip; a direct simplification of this problem
• binary-tree-right-side-view — BFS level by level, picking only the last node seen per level
• maximum-level-sum-of-a-binary-tree — BFS with a running sum per level instead of a collected list
• maximum-width-of-binary-tree — BFS with position tracking across levels to compute width
• binary-tree-preorder-traversal — iterative traversal using a stack instead of a queue; contrasts BFS vs DFS traversal order