Binary Tree Zigzag Level Order Traversal

Freeze the level boundary first; then decide how that level should be written.

The clean solution keeps two concerns separate:

1. BFS determines level membership.
2. A direction flag determines output order within that level.

For this tree:

        3
       / \
      9  20
         / \
        15  7

the zigzag result is:

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

The queue does not need to zigzag. It only needs to preserve a predictable order while we place each value into its correct output position.

Recognize the structure

The output is grouped by depth:

• Level 0: left to right
• Level 1: right to left
• Level 2: left to right
• Continue alternating
• An empty tree produces an empty list

The phrase grouped by depth is the main recognition cue. Breadth-first search naturally processes a tree one level at a time.

The word “zigzag” adds a presentation rule, not a new definition of a level. Nodes at the same depth still belong to the same output row regardless of whether that row is read left to right or right to left.

That distinction prevents a common overreaction: changing the traversal itself before understanding what the output requires. Start with ordinary level-order traversal. Then add the alternating placement rule.

Derive the BFS state

A queue gives us the next nodes to process, but its length changes during traversal:

• Removing a node shrinks the queue.
• Adding its children grows the queue.

Therefore, the live queue length cannot by itself describe the current level after processing has begun.

Capture it before the inner loop:

level_size = len(queue)

Then process exactly level_size nodes. Children added during that loop remain in the queue for the next level.

The state has distinct obligations:

State	Obligation
queue	Store nodes waiting to be processed
level_size	Freeze the boundary of the current level
row	Reserve one output position per node at this depth
left_to_right	Record the direction for the entire level
Mirrored index	Place values without changing queue order

At the start of an outer-loop iteration, the queue contains exactly one level in left-to-right discovery order. That order comes from always enqueuing the left child before the right child.

For a level with level_size nodes, the node removed at position i belongs at:

index = i if left_to_right else level_size - 1 - i

When the direction is left to right, the first removed value goes to index 0, the second to index 1, and so on.

When the direction is right to left, the first removed value goes to the final index, the second goes to the previous index, and so on.

For queue values [9, 20] on a right-to-left level:

i = 0: 9  -> index 1
i = 1: 20 -> index 0

The completed row is [20, 9].

This is the central design choice: keep traversal order stable and change only the write position.

Maintain the level invariant

Use this invariant:

At the start of each outer-loop iteration, the queue contains exactly the nodes at the current depth, ordered from left to right. After processing those nodes, the result contains that depth in the required direction.

Each part of the algorithm supports one piece of this statement:

• level_size identifies exactly which queued nodes belong to the current level.
• The fixed-count inner loop prevents newly added children from being processed too early.
• Left-then-right enqueue order preserves left-to-right discovery order for the next level.
• The mirrored index changes output placement without changing the queue.
• The direction flag flips only after a complete row is finished.

A useful interview explanation follows directly from the invariant:

1. The queue contains one level.
2. The saved size tells us where that level ends.
3. We write its values normally or into mirrored positions.
4. Its children form the next level.
5. We flip direction once.

That is the whole mechanism.

Prove correctness

Each row contains one level

At the start of an iteration, level_size equals the number of nodes currently in the queue. The inner loop runs exactly that many times.

Those nodes were already present before the iteration began, so they all belong to the same depth. Their children are appended while the loop runs, but the loop count does not increase. The children wait for the next outer iteration.

Therefore, each outer iteration creates exactly one level row.

Every node is processed once

Every non-null child is appended exactly once by its parent. Every appended node is removed exactly once by popleft().

So each node contributes one value to the result, with no omissions or duplicates.

Each row has the correct direction

The queue presents the current level from left to right.

• On a left-to-right level, value i is written to index i.
• On a right-to-left level, value i is written to index level_size - 1 - i.

The second mapping reverses the sequence while preserving every value exactly once.

Directions alternate correctly

The first level starts with left_to_right = True. The flag flips after the row is appended, so the sequence is:

level 0: left to right
level 1: right to left
level 2: left to right

The flag changes once per level, not once per node.

Dry run

For the sample tree, the state evolves like this:

Level	Queue at start	Direction	Values removed	Row	Queue after children
0	[3]	Left to right	3	[3]	[9, 20]
1	[9, 20]	Right to left	9, 20	[20, 9]	[15, 7]
2	[15, 7]	Left to right	15, 7	[15, 7]	[]

At level 1, the queue still removes 9 before 20. The direction is implemented by writing 9 to index 1 and 20 to index 0.

The queue never needs to be reversed. Its stable order remains useful for discovering the next level.

An uneven tree follows the same rules:

    1
     \
      2
     /
    3

The result is:

[[1], [2], [3]]

A one-node level has only one possible position, so reversing its direction has no visible effect. Missing children simply are not enqueued; they do not create placeholders.

Python implementation

Use collections.deque because popleft() removes the front node without shifting every remaining element, as a list would.

from collections import deque


class Solution:
    def zigzagLevelOrder(self, root: "TreeNode | None") -> list[list[int]]:
        if root is None:
            return []

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

        while queue:
            level_size = len(queue)
            row = [0] * level_size

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

                index = i if left_to_right else level_size - 1 - i
                row[index] = node.val

                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)

            result.append(row)
            left_to_right = not left_to_right

        return result

The code follows the derivation without adding hidden behavior:

• queue stores the frontier.
• level_size freezes the current boundary.
• row allocates exactly one position for each current-level node.
• index applies the direction.
• Children are appended left first, then right.
• The flag flips after the complete row is stored.

An alternative is to collect every row left to right and call row.reverse() on alternating levels. That is also correct and remains linear overall. I prefer indexed placement in an interview because the direction rule is visible in one formula, and every write has a known destination.

Complexity and edge cases

Let n be the number of nodes and w be the maximum width of the tree.

Time complexity

The traversal takes O(n) time.

Each node is:

1. Added to the queue once.
2. Removed once.
3. Written into one result position once.

The index calculation and child checks are constant-time operations.

Space complexity

The queue uses O(w) auxiliary space, where w is the maximum number of nodes at one level.

The returned result stores all node values, so it uses O(n) space. Including the output, total space is O(n). Excluding the output, the working traversal space is O(w).

Check these cases mentally before submitting:

• Empty tree: []
• Single node: [[value]]
• Skewed tree: one value per row
• Uneven children: enqueue only children that exist
• Negative or duplicate values: values do not affect traversal logic
• One-child level: do not insert a missing-sibling placeholder

Common mistakes

Confusing a fixed loop with a changing boundary

This form is safe in Python:

level_size = len(queue)

for _ in range(level_size):
    ...

The value of level_size is captured before processing begins.

This form expresses the wrong boundary for a single-level pass:

while queue:
    ...

If used inside the logic intended to build one row, it can consume children that were just added and mix two depths together.

The rule is simple: capture the boundary once, then process exactly that many nodes.

Toggling direction per node

The direction belongs to a level. Flipping it inside the inner loop produces a node-by-node alternation rather than a level-by-level zigzag.

Reversing the queue

The queue controls discovery of future levels. Reversing it to fix the current row changes the state that the next level depends on.

Change the output position, not the frontier invariant.

Enqueuing right before left

If you enqueue right children before left children but keep the same mirrored-index formula, you have changed the queue's ordering invariant without changing the proof. The code may pass a narrow example and fail when a level contains several nodes.

Repeated front insertion

This works conceptually:

row.insert(0, node.val)

But inserting at the front of a Python list shifts existing elements. Indexed placement assigns each value directly to its final position and keeps the intended cost visible.

The transferable recognition rule

When an output is grouped by depth, distance, time layer, or another frontier, freeze the boundary before processing the frontier.

Then ask:

• What belongs to this layer?
• Exactly when does the layer end?
• Does the rule change per item or per layer?
• Am I changing traversal order, or only presentation order?

For this problem, the answers are precise:

• The queue contains one tree level.
• The saved queue size ends that level.
• Direction changes once per completed level.
• The queue stays left-to-right while output positions alternate.

Name those obligations before writing code. Once the boundary is fixed, the zigzag is just an index calculation.