Solving the LeetCode 'Binary Tree Zigzag Level Order Traversal' Problem

Binary Tree Zigzag Level Order Traversal looks more exotic than it really is. The phrase "zigzag" makes it sound as though we need a special tree‑walking trick, but the real structure is much calmer than that. This is still a level‑order traversal problem. The only twist is that the direction of the output alternates on each row.

That distinction matters. We are not changing the shape of the traversal itself. We are still processing the tree layer by layer. What changes is how we write each finished level into the result.

What the Problem is Really Asking

Suppose the tree looks like this:

    3   / \  9  20    /  \   15   7

The expected output is:

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

That means:

• level 0 is written left to right
• level 1 is written right to left
• level 2 goes back to left to right

So this is really "Binary Tree Level Order Traversal, but alternate the ordering of the values inside each level".

That is a much more useful description than "do a zigzag". Once we phrase it that way, the pattern becomes much easier to recognise.

Why Breadth‑First Search is Still the Right Pattern

If the output is grouped by depth, breadth‑first search is usually the most natural fit.

Why? Because BFS already works in layers:

• start with the root
• process all nodes on the current level
• enqueue their children
• move to the next level

That is exactly what this problem wants. The zigzag requirement does not replace BFS. It just adds one small rule on top of it:

• when a level is finished, its values should appear in the opposite direction from the previous level

This is an important design point. The grouping logic comes from BFS. The zigzag logic comes from how we place values inside the current level array.

The Small Extra Idea That Makes It Work

The straightforward level‑order problem lets us append values in the order we visit them. This problem asks us to do one extra piece of bookkeeping: keep track of whether the current level should be written left to right or right to left.

That gives us a clean invariant:

• always traverse the tree in normal breadth‑first order
• for each level, decide where each value should be written

I like this framing because it stops us from mutating the traversal itself unnecessarily. We do not need to enqueue children in a special zigzag order. We do not need two different queue strategies. We only need to control the output positions for the current layer.

A Practical TypeScript Solution

type TreeNode = {  val: number;  left: TreeNode | null;  right: TreeNode | null;};export const zigzagLevelOrder = (root: TreeNode | null): number[][] => {  if (!root) {    return [];  }  const result: number[][] = [];  const queue: TreeNode[] = [root];  let head = 0;  let leftToRight = true;  while (head < queue.length) {    const levelSize = queue.length - head;    const levelValues = new Array<number>(levelSize);    for (let index = 0; index < levelSize; index += 1) {      const node = queue[head];      head += 1;      const outputIndex = leftToRight ? index : levelSize - 1 - index;      levelValues[outputIndex] = node.val;      if (node.left) {        queue.push(node.left);      }      if (node.right) {        queue.push(node.right);      }    }    result.push(levelValues);    leftToRight = !leftToRight;  }  return result;};

Why This Solution Works

There are two moving parts worth understanding properly.

levelSize freezes the current layer

At the start of each outer loop, queue.length ‑ head tells us how many nodes belong to this level. That matters because as we process those nodes, we will enqueue their children. Those children belong to the next level, not this one.

By freezing the size first, we get a clean boundary between levels.

outputIndex controls the zigzag

This line is the real twist:

const outputIndex = leftToRight ? index : levelSize - 1 - index;

If we are writing left to right, the first visited node goes into slot 0, the second into slot 1, and so on.

If we are writing right to left, the first visited node goes into the last slot, the second into the second‑last slot, and so on.

That means we can keep the traversal itself stable whilst changing only the placement of values in the current result row.

A Worked Example

Take this tree:

       1      / \     2   3    / \   \   4   5   6

We begin with:

• queue = [1]
• leftToRight = true

First level:

• levelSize = 1
• create [ ]
• visit 1
• store it at index 0
• enqueue 2 and 3
• result becomes [[1]]

Second level:

• queue now contains 2, 3
• leftToRight = false
• levelSize = 2
• create [ , ]
• visit 2 first, but place it at index 1
• visit 3 next, place it at index 0
• row becomes [3, 2]

Third level:

• queue now contains 4, 5, 6
• leftToRight = true again
• values are written normally as [4, 5, 6]

Final output:

[[1], [3, 2], [4, 5, 6]]

The useful thing to notice is that the queue order never became strange. The zigzag effect came entirely from where we wrote each value inside the level array.

Why I Prefer This Over Reversing Each Odd Level

A very common solution is:

• collect the level values in normal left‑to‑right order
• reverse the finished array on every other level

That is valid, and in interview terms it is often acceptable. The reason I would not lead with it is that it does extra work we do not really need. We already know the final size of the level, so we can place each value directly where it belongs.

Direct placement is slightly more deliberate:

• no extra reversal step
• no second pass over the finished level
• the direction rule is visible where the values are written

So, although reversing odd rows is not wrong, it is a little less crisp than filling the correct positions from the start.

Other Potential Solutions, and Why I Would Not Choose Them First

Using unshift() on odd levels

Another tempting approach is to build each level like this:

• push() when going left to right
• unshift() when going right to left

This reads nicely at first, but in JavaScript and TypeScript unshift() is not especially attractive for repeated use because it has to reindex the existing array contents. On a wide level, that means unnecessary extra work.

The pre‑sized array version avoids that completely.

Two Stacks

There is a classic two‑stack solution to zigzag traversal:

• one stack for the current level
• one for the next level
• alternate the child‑push order between rounds

That works, but I think it is more complicated than the problem needs. The main pattern is still level‑order traversal, so keeping one queue and a direction flag is easier to explain and easier to maintain.

Depth‑First Search with Level Tracking

DFS can solve this if we pass the current depth down recursively and write into result[level]. But the output is explicitly level‑based, so BFS is a more direct fit.

DFS also becomes awkward if we try to prepend values on odd‑numbered levels, because we drift back toward the same unshift() cost problem. You can still make it work, but the code is no longer as honest as the queue‑based version.

A Mistake People Make When They Overthink the Zigzag

One subtle bug is trying to change the order in which children are enqueued depending on the current row.

That usually feels plausible:

• maybe on odd rows we should enqueue right child before left child?

But that changes the traversal frontier itself, which then affects the next level in a way we do not want. The problem does not ask for a different tree exploration order. It asks for a different ordering of values in the output row.

That is why I prefer this rule:

• always enqueue children in normal left‑then‑right order
• only vary the output position inside the current level array

Common Mistakes

Forgetting to Flip Direction After Each Level

If leftToRight never changes, the solution quietly collapses back into ordinary level‑order traversal.

Mixing Current‑Level Nodes with Next‑Level Nodes

If we do not freeze levelSize before processing the level, we can accidentally let children from the next row leak into the current row.

Using unshift() without thinking about the cost

It works functionally, but it is not the most efficient or cleanest option in JavaScript.

Changing Child Enqueue Order Instead of Output Order

That changes the traversal itself rather than just the presentation of each finished row.

Forgetting the Empty‑Tree Case

If root is null, the correct result is [].

Complexity and Why This is a Strong Pattern

Each node is visited exactly once, so the time complexity is O(n).

The queue stores at most one full level at a time, so the auxiliary space complexity is O(w), where w is the maximum width of the tree.

That is the same broad complexity story as ordinary level‑order traversal. The zigzag rule does not require a fundamentally more expensive algorithm. It just asks us to be a little more careful about where each level value is written.

Wrapping up

Binary Tree Zigzag Level Order Traversal is a good reminder that not every twist changes the core pattern. The underlying job is still breadth‑first search. The new part is just an output invariant: alternate the direction of each level.

Once we keep the traversal steady and focus on value placement, the problem becomes much less dramatic. It is really just level‑order traversal with one extra line of indexing logic.

Key Takeaways

• This is still a breadth‑first search problem because the output is grouped by depth.
• The zigzag behaviour should affect output placement, not the traversal order itself.
• A pre‑sized level array avoids both reverse() and repeated unshift() calls.

That makes this a nice follow‑on from ordinary level‑order traversal: same core pattern, slightly sharper bookkeeping.