Should I reverse the queue for the odd levels?

No. The queue must keep plain left-to-right order, or the next level’s children come out in the wrong order. Only the list of values collected for the level is reversed.

Why check len(result) % 2?

The number of levels already in the result is the index of the level being added. Levels 1, 3, 5 and so on are odd, and those are the ones read right to left.

Is reversing the list slower than inserting at the front?

Reversing a level of k values costs O(k), the same as building it, so the whole traversal stays O(n). Inserting at the front of an array can cost O(k) per insert instead.

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

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.

Dry Run

Tree: [1, 2, 3, 4, null, null, 5] — 4 is the left child of 2, and 5 is the right child of 3.

Level	Dequeued (left to right)	Collected	Odd?	result
0	1	`[1]`	No — keep	`[[1]]`
1	2, 3	`[2, 3]`	Yes — reverse to `[3, 2]`	`[[1], [3, 2]]`
2	4, 5	`[4, 5]`	No — keep	`[[1], [3, 2], [4, 5]]`

The queue is dequeued left to right on every level; only the collected list is reversed.

Edge Cases & Common Mistakes

Edge Cases:

Null Root: Return [] immediately.
Single Node: [[root.val]].

Common Mistakes:

Reversing the Queue itself (No! Only reverse the values collected for the level).
Checking len(result) % 2 after appending the level instead of before, which flips every direction.

Solution Code

BFS with conditional reverse.

Zigzag Level Order Traversal Code

1var zigzagLevelOrder = function(root) {
2    const result = [];
3    if (!root) {
4        return result;
5    }
6    const queue = [root];
7    let head = 0;
8    while (head < queue.length) {
9        const size = queue.length - head;
10        const level = [];
11        for (let i = 0; i < size; i++) {
12            const node = queue[head++];
13            level.push(node.val);
14            if (node.left) {
15                queue.push(node.left);
16            }
17            if (node.right) {
18                queue.push(node.right);
19            }
20        }
21        if (result.length % 2 === 1) {
22            level.reverse();
23        }
24        result.push(level);
25    }
26    return result;
27};

Binary Tree Rightmost Node (Right Side View)

Maximum Width of Binary Tree

Zigzag Level Order Traversal

Problem Understanding

Algorithm Strategy

Interactive Visualization

Dry Run

Edge Cases & Common Mistakes

Solution Code

Zigzag Level Order Traversal Code

The approach, step by step

Collect a level

Reverse odd levels

Append

Frequently asked questions

Should I reverse the queue for the odd levels?

Why check len(result) % 2?

Is reversing the list slower than inserting at the front?

AI resume checker — match your resume to the job description