FAANGPrep Sprint

Zigzag Level Order Traversal

Traverse levels in alternating order (left-to-right, then right-to-left).

Medium

15 min

Solve on LeetCode

Examples

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

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

Explain:

Level 1 is read right to left.

Input:root = [1]

Output:[[1]]

Explain:

A single level.

Input:root = []

Output:[]

Explain:

An empty tree has no levels.

Problem Understanding

Read the binary tree under root level by level, switching direction on every level, and return the values in that order.

Level 0: Left -> Right
Level 1: Right -> Left
Level 2: Left -> Right
...

Algorithm Strategy

We use standard BFS with a Queue to process levels one by one.

Handling Zigzag:

Collect all values for the current level into a list.
Check Depth: If the current level depth is Odd, reverse the list before adding it to results.
Alternative: Use a Deque for the current level list, using push_front or push_back depending on depth.

Interactive Visualization

#n = DEQUEUE ORDER, ALWAYS LEFT TO RIGHT · ROWS BESIDE = OUTPUT

ENQUEUE ROOT

Level

Direction

→ left to right

queue (front first)

level list

Not collecting

result

[]

Put the root, 3, in the queue

Level 0: size = 1. Dequeue it left to right, as always

Tree

The number under each node is the order it left the queue — left to right on every level, exactly as in plain level order. The zigzag only appears in the result beside the tree, where every odd level's list has been reversed before it is appended.