Zigzag Level Order Traversal Without Queue Gymnastics

"Binary Tree Zigzag Level Order Traversal" shows up again and again in Meta, Amazon, Microsoft phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Tree BFS pattern quickly and code it cleanly. Part 3 of 11 in the Tree BFS arc.

The Problem

Return the zigzag level order traversal: left to right, then right to left, alternating by level. A long-running Meta favorite. The trap is trying to reverse the queue — the fix is realizing direction is a property of the output, not the traversal.

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

Recognizing the Tree BFS Pattern

Breadth-first search explores a tree or graph level by level using a queue, and its defining superpower is the level snapshot: freeze the queue length, process exactly that many nodes, and you have processed one complete level. Anything phrased per-level — level lists, level averages, rightmost visible node, shortest path in unweighted structures — is BFS by construction.

Traversal order is still plain BFS — only each level's rendering flips. Keep the template untouched and post-process alternate levels; entangling direction with queue mechanics is how correct-looking solutions go wrong under pressure.

The Approach

Standard snapshot loop with a boolean flag. Collect each level left to right as usual; before appending, reverse it when the flag says so; flip the flag per level. Reversal cost totals O(n) across all levels — a non-issue.

The deque-of-values alternative (appendleft on alternate levels) avoids the reversal and is worth mentioning; the flag version is easier to get right in seven minutes.

Python Solution

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


from collections import deque


def zigzag_level_order(root: TreeNode | None) -> list[list[int]]:
    """Level lists, alternating left-to-right and right-to-left."""
    if not root:
        return []
    result: list[list[int]] = []
    queue: deque[TreeNode] = deque([root])
    left_to_right = True
    while queue:
        level: list[int] = []
        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)
        result.append(level if left_to_right else level[::-1])
        left_to_right = not left_to_right
    return result

Complexity

• Time: O(n) — BFS plus at most one reversal per level
• Space: O(w) — queue plus one level buffer

Interview Tips and Follow-Ups

• Children are always enqueued left then right, regardless of direction — say this before the interviewer asks, because they will.
• Spiral matrix traversal is the 2D cousin (direction state over a fixed structure) — adjacent prep, same mental model.
• If asked to avoid reversals entirely, the answer is a deque per level with appendleft — know it, don't lead with it.

More Tree BFS problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.