We need to perform a level order traversal of a binary tree, but with a twist. Instead of reading every level left to right, we alternate the direction at each level. Level 0 goes left to right, level 1 goes right to left, level 2 goes left to right again, and so on. The result is a "zigzag" pattern through the tree.

If you've solved Binary Tree Level Order Traversal (LeetCode #102), this is a direct extension. The underlying traversal is the same. The only difference is that we need to reverse the order of every other level. The core challenge is figuring out the cleanest way to handle that alternation.

There are two main strategies: reverse the collected level list on odd levels, or use a deque to build each level's list in the correct direction from the start. Both work in O(n) time, but they differ in elegance.

Key Constraints:

Intuition

The simplest way to think about this: do a normal level order traversal, then reverse every odd-numbered level. If you already know how to solve LeetCode #102 (Binary Tree Level Order Traversal), you're almost done. The zigzag is just a post-processing step.

We use BFS with a queue, grouping nodes by level using the standard levelSize trick. After collecting all values for a level, we check whether that level should be reversed. Even levels (0, 2, 4, ...) go left to right, odd levels (1, 3, 5, ...) go right to left. A simple boolean flag leftToRight toggles after each level.

This approach is easy to understand and easy to implement. The reversal adds a small constant overhead per level, but since each node is only reversed once, the total work is still O(n).

Algorithm

Example Walkthrough

Code

This approach works correctly, but on right-to-left levels we build the list and then reverse it. What if we could build each level's list in the correct order from the start?

Intuition

Instead of reversing after collecting, we build each level's list in the correct zigzag order from the start. The key insight: on left-to-right levels, we append values to the end of the level list. On right-to-left levels, we insert values at the front.

We still do a standard BFS. The queue processes nodes in the same order as before. The only change is how we add values to the current level's list. A deque (double-ended queue) lets us efficiently insert at either end in O(1) time, which is exactly what we need.

Think of it this way: the BFS queue always processes nodes left to right within each level. On even levels, that order is correct, so we append. On odd levels, we want the reverse order, so we prepend. The deque for the current level serves as a flexible container that handles both directions.

Algorithm

Example Walkthrough

Code

Both BFS approaches use a queue explicitly. Can we achieve the same zigzag ordering using DFS, where no explicit queue is needed?

Intuition

Just like regular level order traversal can be solved with DFS, the zigzag variant can too. We perform a preorder DFS, carrying the current level as a parameter. When we visit a node at level d, we add its value to result[d]. The zigzag twist: on even levels, we append to the end of the list; on odd levels, we insert at the front.

This works because DFS with left-before-right recursion visits nodes in the same left-to-right order within each level. On even levels, that's the correct zigzag direction, so appending is fine. On odd levels, we need right-to-left, so inserting at the front reverses the order as values accumulate.

The DFS approach uses no explicit queue. It relies on the recursion stack to manage traversal. This is conceptually different from BFS, but the output is identical.

Algorithm

Example Walkthrough

Code