Binary Tree Zigzag Level Order Traversal

Given the root of a binary tree, return the zigzag level-order traversal of its nodes' values — level by level, but alternating direction: left-to-right on the first level, right-to-left on the next, and so on.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Run a normal level-order BFS and keep a direction flag that flips each level.

Collect each level left-to-right, then reverse the rows on odd levels.

The traversal (enqueue left then right) never changes — only the row layout does.

Common doubts

No — keep enqueuing left-then-right; only reverse the collected row for odd levels, or place values positionally.

Level 0 (the root) is left-to-right; the direction alternates from there.

Use a deque per level and front-insert on right-to-left levels, or write each value to index size-1-i.

Interview follow-ups

· What an interviewer asks next.

Alternate pushing children left-first vs right-first onto two stacks — a classic stack-based zigzag.

Only the odd levels are reversed; everything else is identical.

Fun facts

Zigzag order is also called 'spiral' or 'boustrophedon' traversal, after the ox-plowing pattern of ancient writing.
You can implement it with two stacks instead of a flag, alternating the child push order.

Asked at

AmazonMicrosoftFacebook

Frequently Sometimes Occasionally

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [20, 9], [15, 7]]
Level 0 left-to-right, level 1 right-to-left, level 2 left-to-right.

Example 2

Input: root = [1]
Output: [[1]]
A single node forms one level.

Example 3

Input: root = []
Output: []
An empty tree has no levels.

Constraints

- The number of nodes is in the range [0, 2000] - -100 <= Node.val <= 100

Zigzag order is ordinary level-order with one extra rule: reverse every other level. Do a normal breadth-first traversal to collect each level left-to-right, then flip the rows at odd levels. A left-to-right flag toggled each level is all the bookkeeping you need.

Prerequisites

Before you start

· Concepts used directly in the solution.

Level-order traversal. BFS with a queue, processing one level at a time.

A direction flag. A boolean toggled per level to decide whether to reverse.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Direction

“Which level goes which way?”

The first (level 0) is left-to-right; then it alternates.

“Empty tree?”

Return an empty list.

The ideal opening — say it like this

I run a normal level-order BFS and keep a left-to-right flag that flips each level.

When the flag says right-to-left, I reverse that level's row before adding it.

Understand the problem

Worked example — tree [3, 9, 20, null, null, 15, 7]

        3
       / \
      9   20
         /  \
        15   7
level 0 (L->R): [3]
level 1 (R->L): [20, 9]
level 2 (L->R): [15, 7]
result: [[3], [20, 9], [15, 7]]

Key observations

1Aha

It's level-order plus a flip

Collect each level normally; only the direction of odd levels changes.

2Aha

Toggle a flag, don't change the traversal

The BFS still enqueues left-then-right; the zigzag lives entirely in how you lay out each row.

3Aha

Linear time

Each node is visited once and each row reversed once — O(n) overall.

Brute force vs optimal

	Index placement (deque/positional)	Reverse alternate rows
Idea	Insert at front or compute mirrored index per node	Collect L->R, reverse odd levels
Time	O(n)	O(n)
Space	O(n)	O(n)

Both are O(n); reversing alternate rows is the simplest to write. Full code is in the Approaches selector below.

Summary

Key takeaway

Run level-order BFS and reverse every other level. A per-level direction flag decides which rows to flip. O(n) time and space.

zigzag(root):
    bfs level by level, collecting each row L->R
    if the level index is odd: reverse the row
    append the row