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).

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)

Run BFS level by level, but write values into the level slice from left or from right depending on the current direction.

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

• Invariant: the queue contains exactly the nodes of the current level before you start processing that level.
• The queue holds exactly the current level’s nodes before each level pass.
• Processing size nodes and enqueueing children builds the next level correctly.
• Collected level results therefore match the required traversal.

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.

Complexity

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

Implementation notes (Go)

• Use a slice as a queue with a head index to avoid costly pop(0).
• Filling level by index avoids an extra reverse pass.