Binary Tree Zigzag Level Order Traversal

Given a binary tree, return its level order traversal but alternating direction each level (left-to-right, then right-to-left, and so on).

Why this is worth learning

Traversal order and output placement can be separated. Keep ordinary left-to-right BFS discovery, but write alternate levels into reversed result positions.

Before coding: one-minute experiment

If a BFS level is [4,5,6,7] and this depth is reversed, where is the first removed value 4 written?

Function signature

func ZigzagLevelOrder(root *TreeNode) [][]int

Inputs / outputs

• root: root node of the tree (may be nil).
• Return: slice of levels, where each inner slice lists values in zigzag order.

Example

    3
   / \
  9  20
     / \
    15  7
Output: [[3],[20,9],[15,7]]

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

A straightforward solution collects ordinary level order and reverses alternate result slices. We can eliminate that second per-level pass without changing discovery: allocate the level's final slice and choose each destination index as a node is removed. Forward levels use i, reversed levels use size−1−i. Keeping child enqueue order unchanged lets the original BFS proof continue to apply. Prepending every value is also logically possible, but in Go it can repeatedly copy a wide level and turn linear work into quadratic work.

Invariant: the queue contains exactly the nodes of the current level before you start processing that level.

Algorithm (step-by-step)

1. If root is nil, return an empty slice.
2. Initialize a queue with root and a boolean leftToRight = true.
3. While the queue is not empty:
   • Let size = len(queue) and allocate level := make([]int, size).
   • For i = 0..size-1:
     • Pop the next node.
     • Compute idx = i if leftToRight else size-1-i.
     • Set level[idx] = node.Val.
     • Enqueue node.Left and node.Right if they exist.
   • Append level to the answer.
   • Flip leftToRight.
4. Return the answer.

Correctness sketch

BFS supplies each level's nodes in left-to-right order by the usual queue invariant. On a forward level, store the ith removed value at index i; on a reversed level, store it at size-1-i. Each mapping is a bijection on the level's indices, so every value appears exactly once in the required direction. Child enqueue order remains left then right regardless of the output direction, preserving the next level's discovery invariant. Toggling only the placement direction after each frozen-size level produces the required alternation without changing tree topology.

Trace (hand walkthrough)

Example input:
    3
   / \
  9  20
     / \
    15  7
Output: [[3],[20,9],[15,7]]

Walk:
- level 0 left->right: [3]
- level 1 right->left: nodes [9,20] -> output [20,9]
- level 2 left->right: [15,7]

Pitfalls to avoid

• Reversing by inserting at the front of a slice (O(n^2)).
• Forgetting to toggle the direction each level.
• Not handling a nil root.

Debugging lens

Do not reverse child insertion and output placement simultaneously unless you have proved the resulting order. Use at least three levels so the direction toggles twice.

Complexity

• Time: O(n).
• Extra space: O(n) for the queue.

Implementation notes (Go)

• The reference removes the front with queue = queue[1:], an O(1) reslice in Go; it does not shift all remaining elements. A head index is another option, with retained backing storage included in its memory cost.
• Filling level by index avoids an extra reverse pass.

Reconstruction checkpoint

A reversed level is discovered as [10,20,30]. List the destination indices in dequeue order. If those nodes have children, in what order should their children be enqueued for this implementation?

Return to Binary Tree BFS · Module quiz