Loading…

mediumTreesLC #103Frequently asked

Binary Tree Zigzag Level Order Traversal

Trees & BST · 15 of 41 · 9 min

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

In plain English

We still visit the tree level by level, top to bottom — that part is identical to ordinary level-order traversal. The only twist is the within-row ordering: level 0 reads left-to-right, level 1 right-to-left, level 2 left-to-right again, and so on. Critically, the tree's structure and the parent-child links never change; only the direction in which we lay out each row's values alternates.

Examples

Example 1

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

Example 2

Input: root = [1]
Output: [[1]]
Note: Single node, single level, no reversal needed.

Example 3

Input: root = []
Output: []
Note: Empty tree has no levels.

Constraints

The number of nodes is in the range [0, 2000]
-100 ≤ Node.val ≤ 100
Output is a list of lists, one per level, with alternating within-row direction

Clarifying questions4First question: Does the zigzag affect how I traverse, or only how I output?Explore questions

Q1.Does the zigzag affect how I traverse, or only how I output?
Only the output. You traverse identically every level and merely reverse the recording order on alternate levels. Changing the traversal itself is the classic mistake.
Q2.Which direction does the first (root) level go?
Left to right. So even-indexed levels (0, 2, 4, …) are left-to-right and odd-indexed levels are right-to-left.
Q3.Can the tree be empty?
Yes, the range starts at 0. A null root returns an empty list of levels.
Q4.Should I reverse children when enqueuing to flip a level?
No — that corrupts the order of grandchildren. Always enqueue left then right; flip only where each value is placed in the row.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

This is plain level-order BFS plus a direction flag that flips every level. Always traverse the tree the same way (left-to-right, enqueuing children normally); only the ORDER you record each level alternates. The clean implementation collects each level into a deque and either appends to the back (left-to-right rows) or pushes to the front (right-to-left rows), so you never touch the actual traversal — just where each value lands in the row.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you separate the traversal from the output ordering — flipping how each row is recorded with a direction flag rather than altering the BFS or reversing children, which is where candidates introduce bugs.

Where candidates slip

Reversing the order children are enqueued (which scrambles subsequent levels), or reversing the row list with O(width) work each time instead of inserting at the front of a deque.

How to stand out

State 'traversal stays constant, only recording order flips', use a deque for O(1) front insertion, and note the alternative of building normally then reversing odd rows — explaining the small efficiency difference.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Level-Order BFS with a Direction Flag and Deque Insertion (Optimal)Optimal	`O(n)`	`O(n)`	Lead with this. Frame it as 'ordinary level order, but a boolean controls whether each row is filled front or back'.	Read
2	Level-Order BFS Then Reverse Odd Rows	`O(n)`	`O(n)`	Offer as the simplest-to-explain variant — build normal level order, then reverse every other row. Note the small efficiency cost.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewBFS level (always L→R visit)leftToRight ?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Level-Order BFS with a Direction Flag and Deque Insertion (Optimal)

TimeO(n)SpaceO(n)

Lead with this. Frame it as 'ordinary level order, but a boolean controls whether each row is filled front or back'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Strip away the zigzag for a second: this is level-order traversal. What's the minimal change to flip the order of every other level?

2Hint 2Explore hint

Keep a boolean leftToRight that toggles after each level. Don't change how you traverse — change where you place each node's value in the row.

3Hint 3Explore hint

Use a deque for the current row: when going left-to-right, add to the back; when right-to-left, add to the front. Each insertion is O(1), so no row reversal is needed.

A · Core idea

The cleanest way to think about zigzag is to realize that the traversal never changes — only the presentation does. We run exactly the same breadth-first, level-by-level sweep as ordinary level-order traversal, enqueuing each node's children left-then-right every single time. The 'zigzag' lives purely in how we record each level's values into the output.

Why a direction flag is all you need. We keep a boolean leftToRight, true for the root's level. After finishing each level we flip it. While filling a level, the flag decides where in the row the current node's value goes. On a left-to-right level we append to the back (natural order); on a right-to-left level we push to the front, so the first node visited ends up last in the row — achieving the reversal without ever changing the order in which we visit nodes.

Why a deque makes this O(1) per node. Reversing a list of width w afterward costs O(w). Instead, we collect each level into a double-ended queue: append to the back for left-to-right, appendleft (push front) for right-to-left. Front insertion on a deque is O(1), so the whole row is built in O(w) regardless of direction, with no separate reversal pass. At the end of the level we convert the deque to a plain list and add it to the result.

Why we must NOT reverse the child-enqueue order. A tempting but broken idea is to enqueue children right-then-left on alternate levels to 'naturally' flip the next row. This corrupts everything below: the order of a level's nodes determines the order their children are dequeued, so flipping enqueue order on one level scrambles the grandchildren's order in a way that compounds. By keeping enqueue order fixed (left then right, always) and isolating the flip to the recording step, the BFS frontier stays correct and only the output is serpentine.

Why the size snapshot still matters. As in any level-order BFS, we read size = queue.length before draining the level so children added during the inner loop belong to the next level. That boundary is what lets us flip the flag exactly once per level. Everything special about zigzag is layered on top of this standard, well-understood loop.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Zigzag over [3,9,20,null,null,15,7]

level 0 (L→R)

Active call / nodeSupporting contextReturned stateNot active

Visiting order is constant L→R; the arrows show how the recorded row direction alternates per level.

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

C · Code with teaching comments

solution.javaJava

Level-Order BFS with a Direction Flag and Deque Insertion (Optimal) — optimal

6 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
10
    List<List<Integer>> result = new ArrayList<>();
11
    if (root == null) return result;
12
    Queue<TreeNode> queue = new LinkedList<>();
13
    queue.offer(root);
14
    // Root level reads left-to-right; this flag flips after every level.
15
    boolean leftToRight = true;
16
    while (!queue.isEmpty()) {
17
        int size = queue.size();                 // freeze this level
18
        LinkedList<Integer> row = new LinkedList<>();
19
        for (int i = 0; i < size; i++) {
20
            TreeNode node = queue.poll();
21
            if (leftToRight) {
22
                row.addLast(node.val);            // natural order
23
            } else {
24
                row.addFirst(node.val);           // reversed order, O(1)
25
            }
26
            if (node.left != null) queue.offer(node.left);   // always L then R
27
            if (node.right != null) queue.offer(node.right);
28
        }
29
        result.add(row);
30
        leftToRight = !leftToRight;                // flip once per level
31
    }
32
    return result;
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Decouple traversal order from output order. The tree is always walked the same way; a single boolean redirects each value to the front or back of the current row. This separation — 'don't change how you explore, change how you record' — is a reusable principle for any 'same structure, different presentation' problem.

ComplexityO(n) time, O(n) space — Each node is enqueued and dequeued once, and each value is inserted into a deque in O(1) (front or back) → O(n) time. The queue holds at most one level (width w) and the output stores all n values → O(n) space overall.

E · Edge cases and pitfalls7root = [1] — One level, leftToRight stays true → [[1]].Explore edge cases

Edge cases handled

root = [1]One level, leftToRight stays true → [[1]].
root = []Null root → return empty list immediately.
root = [1,2,3,4,null,null,5]Level 1 reversed → [3,2]; level 2 left-to-right → [4,5]. Confirms enqueue order untouched while output flips.

Pitfalls

Reversing the order children are enqueued — scrambles all deeper levels.
Flipping the flag per node instead of per level.
Reversing the finished row with O(width) work each odd level instead of O(1) front insertion.
Forgetting the empty-tree guard and returning a list with a phantom empty level.

03.2

Approach 2 of 2

Level-Order BFS Then Reverse Odd Rows

TimeO(n)SpaceO(n)

Offer as the simplest-to-explain variant — build normal level order, then reverse every other row. Note the small efficiency cost.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What if you ignore zigzag entirely first, producing plain left-to-right level order?

2Hint 2Explore hint

Once you have the list of rows, which ones are out of order? The odd-indexed levels.

3Hint 3Explore hint

Reverse each odd-indexed row in place at the end. Simpler to reason about, though reversing costs O(width) per odd row.

A · Core idea

This variant trades a hair of efficiency for maximum clarity: first produce the ordinary left-to-right level-order traversal, then post-process by reversing every odd-indexed row.

Why it's the easiest to explain. Plain level-order BFS is a pattern most people can write without thinking — snapshot the size, drain the level into a list, enqueue children. There's no direction flag to track during traversal, so there's one fewer moving part to get wrong. The zigzag requirement is handled entirely as a separate, obvious cleanup step.

Why only odd rows are reversed. The root level (index 0) is already left-to-right, which is correct. Level 1 should be right-to-left, so it needs reversing. Level 2 is correct again, level 3 needs reversing, and so on. The rule is simply: reverse the row when its level index is odd. We can do this inside the loop (reverse before adding when the flag says so) or in a final pass over the result.

Why it's slightly less efficient than the deque version. Reversing a row of width w is O(w) work, and we do it for roughly half the levels. The total extra work is still bounded by O(n) across the whole tree, so asymptotically it's identical — but the deque-insertion approach avoids the constant-factor cost of an explicit reversal by placing each value in its final position immediately. In an interview, mentioning that you know this difference (same big-O, slightly worse constant) is a nice touch; in practice either is perfectly acceptable.

Why correctness is obvious here. Because the traversal is the unmodified, well-trusted level-order routine, the only place a bug could hide is the 'reverse odd rows' step — and that's trivially verifiable. This makes the approach a safe fallback when you want to minimize the chance of an off-by-one or an enqueue-order slip under interview pressure.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

BFS

level order = [[3],[9,20],[15,7]]

Staterows collected normally

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

C · Code with teaching comments

Reference implementation previewpublic List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root);Explore the full code

solution.javaJava

Level-Order BFS Then Reverse Odd Rows — reference

4 teaching notes

1
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
2
    List<List<Integer>> result = new ArrayList<>();
3
    if (root == null) return result;
4
    Queue<TreeNode> queue = new LinkedList<>();
5
    queue.offer(root);
6
    // Row 0 is not reversed; the flag toggles so odd rows get reversed.
7
    boolean reverse = false;
8
    while (!queue.isEmpty()) {
9
        int size = queue.size();
10
        List<Integer> row = new ArrayList<>();
11
        for (int i = 0; i < size; i++) {
12
            TreeNode node = queue.poll();
13
            row.add(node.val);                      // always natural order
14
            if (node.left != null) queue.offer(node.left);
15
            if (node.right != null) queue.offer(node.right);
16
        }
17
        if (reverse) Collections.reverse(row);      // fix odd rows
18
        result.add(row);
19
        // Alternate the reversal flag each level.
20
        reverse = !reverse;
21
    }
22
    return result;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Sometimes the clearest solution is 'solve the simple version, then fix it up'. Producing canonical level order and reversing alternate rows decomposes the problem into two independently-correct pieces, which is often easier to defend than a single cleverer loop.

ComplexityO(n) time, O(n) space — Standard level-order BFS is O(n). Reversing the odd rows touches each element at most once more → still O(n) total. Output and queue are O(n) / O(w) space.

E · Edge cases and pitfalls7root = [1] — Single row, reverse stays false → [[1]].Explore edge cases

Edge cases handled

root = [1]Single row, reverse stays false → [[1]].
Full tree of 3 levelsRows 0 and 2 untouched, row 1 reversed — verifies only odd rows flip.
Wide last levelReversing the wide odd row is O(width), still within O(n) overall.

Pitfalls

Reversing even rows by toggling the flag in the wrong phase (initialize correctly).
Reversing while iterating, mutating the row mid-build.
Assuming the reversal changes complexity — it stays O(n).
Forgetting the empty-tree guard.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;
    while (!queue.isEmpty()) {
        int size = queue.size();                 // freeze this level
        LinkedList<Integer> row = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (leftToRight) {
                row.addLast(node.val);            // natural order
            } else {
                row.addFirst(node.val);           // reversed order, O(1)
            }
            if (node.left != null) queue.offer(node.left);   // always L then R
            if (node.right != null) queue.offer(node.right);
        }
        result.add(row);
        leftToRight = !leftToRight;                // flip once per level
    }
    return result;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Flipping the child-enqueue order

Reversing which child you enqueue first to 'naturally' flip the next level scrambles the order of grandchildren — the corruption compounds down the tree. Keep enqueue order fixed.

Explore the code comparison

Don't write this

if (leftToRight) {
    if (node.left != null) queue.offer(node.left);
    if (node.right != null) queue.offer(node.right);
} else {
    if (node.right != null) queue.offer(node.right);   // wrong: corrupts deeper levels
    if (node.left != null) queue.offer(node.left);
}

Write this instead

if (node.left != null) queue.offer(node.left);   // always left then right
if (node.right != null) queue.offer(node.right);
// flip only where node.val is placed in the row

Toggling the flag per node

The direction is a property of the LEVEL, not the node. Flipping inside the inner loop alternates within a single row, producing garbage ordering.

Explore the code comparison

Don't write this

for _ in range(size):
    node = queue.popleft()
    if left_to_right:
        row.append(node.val)
    else:
        row.appendleft(node.val)
    left_to_right = not left_to_right   # wrong: flips per node

Write this instead

for _ in range(size):
    node = queue.popleft()
    if left_to_right:
        row.append(node.val)
    else:
        row.appendleft(node.val)
left_to_right = not left_to_right       # flip once, after the level

O(width) reversal instead of O(1) front insertion

Building a list then reversing it on every other level repeats work. A deque lets you place each value at its final end in O(1), avoiding the reversal entirely.

Explore the code comparison

Don't write this

List<Integer> row = new ArrayList<>();
for (...) row.add(node.val);
if (!leftToRight) Collections.reverse(row);   // O(width) extra each odd level

Write this instead

LinkedList<Integer> row = new LinkedList<>();
for (...) {
    if (leftToRight) row.addLast(node.val);
    else row.addFirst(node.val);             // O(1), final position immediately
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Level-order BFS + per-level direction flag, insert front/back

Code pattern to memorize

leftToRight = true
while queue:
    size = len(queue)
    row = deque()
    for i in range(size):
        node = queue.popleft()
        if leftToRight: row.append(node.val)   # back
        else:           row.appendleft(node.val)# front
        enqueue node.left, node.right (always normally)
    result.append(list(row))
    leftToRight = not leftToRight

Rules to remember

1Keep the traversal identical every level — only the recording order flips.
2Use a deque per level: append to the back on left-to-right rows, push to the front on right-to-left rows.
3Toggle the direction flag once per level, after finishing the row — not per node.
4Always enqueue children left then right; reversing enqueue order corrupts the next level's nodes.
5Snapshot the queue size before the inner loop, exactly as in any level-order BFS.

Use this pattern when

Level-order output where alternate levels are reversed (serpentine / boustrophedon)
You need rows top-to-bottom but with flipping within-row order
Any 'snake' or 'zigzag' rendering of a tree by level
BFS is natural and you just need to control insertion order per row

Choose another pattern when

Plain left-to-right rows → Level Order Traversal (no flag)
Only a per-level aggregate, not the full row → Average/Max of Levels
Only the last node of each level → Right Side View
Order across levels (not within) matters → that's bottom-up Level Order II

Interview takeaway

Zigzag is Level Order Traversal with one boolean. The insight that you should flip the *recording* order, never the *traversal* order, keeps the children-enqueue logic untouched and the code bug-free. Deque-front-insertion turns the reversal into an O(1)-per-node operation instead of reversing rows afterward.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternLevel-order BFS with controlled per-level output ordering. Recognise it whenever rows must alternate direction or be presented differently than visited. The lesson — decouple traversal from presentation via a flag and deque-end insertion — generalizes to any serpentine/boustrophedon rendering and to Level Order II's bottom-up flip.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Binary Tree Level Order Traversal
The base problem — drop the direction flag and always record left-to-right.
Binary Tree Level Order Traversal II
Coming soon
Bottom-up level order — build normally then reverse the list of levels.
Binary Tree Right Side View
Same BFS, but keep only the last node of each level.
Average of Levels in Binary Tree
Same level-freeze loop, reducing each level to its average.

Same pattern

←

Average of Levels in Binary Tree

Continue · Next problem

Count Complete Tree Nodes

mediumTreesLC #103Frequently asked

Binary Tree Zigzag Level Order Traversal

LCPractice

Trees & BST · 15 of 41 · 9 min

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

In plain English

Examples

Example 1

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

Example 2

Input: root = [1]
Output: [[1]]
Note: Single node, single level, no reversal needed.

Example 3

Input: root = []
Output: []
Note: Empty tree has no levels.

Constraints

The number of nodes is in the range [0, 2000]
-100 ≤ Node.val ≤ 100
Output is a list of lists, one per level, with alternating within-row direction

Clarifying questions4First question: Does the zigzag affect how I traverse, or only how I output?Explore questions

Q1.Does the zigzag affect how I traverse, or only how I output?
Only the output. You traverse identically every level and merely reverse the recording order on alternate levels. Changing the traversal itself is the classic mistake.
Q2.Which direction does the first (root) level go?
Left to right. So even-indexed levels (0, 2, 4, …) are left-to-right and odd-indexed levels are right-to-left.
Q3.Can the tree be empty?
Yes, the range starts at 0. A null root returns an empty list of levels.
Q4.Should I reverse children when enqueuing to flip a level?
No — that corrupts the order of grandchildren. Always enqueue left then right; flip only where each value is placed in the row.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Reversing the order children are enqueued (which scrambles subsequent levels), or reversing the row list with O(width) work each time instead of inserting at the front of a deque.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Level-Order BFS with a Direction Flag and Deque Insertion (Optimal)Optimal	`O(n)`	`O(n)`	Lead with this. Frame it as 'ordinary level order, but a boolean controls whether each row is filled front or back'.	Read
2	Level-Order BFS Then Reverse Odd Rows	`O(n)`	`O(n)`	Offer as the simplest-to-explain variant — build normal level order, then reverse every other row. Note the small efficiency cost.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Level-Order BFS with a Direction Flag and Deque Insertion (Optimal)

TimeO(n)SpaceO(n)

Lead with this. Frame it as 'ordinary level order, but a boolean controls whether each row is filled front or back'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Strip away the zigzag for a second: this is level-order traversal. What's the minimal change to flip the order of every other level?

2Hint 2Explore hint

Keep a boolean leftToRight that toggles after each level. Don't change how you traverse — change where you place each node's value in the row.

3Hint 3Explore hint

Use a deque for the current row: when going left-to-right, add to the back; when right-to-left, add to the front. Each insertion is O(1), so no row reversal is needed.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Zigzag over [3,9,20,null,null,15,7]

level 0 (L→R)

Active call / nodeSupporting contextReturned stateNot active

Visiting order is constant L→R; the arrows show how the recorded row direction alternates per level.

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

C · Code with teaching comments

solution.javaJava

Level-Order BFS with a Direction Flag and Deque Insertion (Optimal) — optimal

6 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
10
    List<List<Integer>> result = new ArrayList<>();
11
    if (root == null) return result;
12
    Queue<TreeNode> queue = new LinkedList<>();
13
    queue.offer(root);
14
    // Root level reads left-to-right; this flag flips after every level.
15
    boolean leftToRight = true;
16
    while (!queue.isEmpty()) {
17
        int size = queue.size();                 // freeze this level
18
        LinkedList<Integer> row = new LinkedList<>();
19
        for (int i = 0; i < size; i++) {
20
            TreeNode node = queue.poll();
21
            if (leftToRight) {
22
                row.addLast(node.val);            // natural order
23
            } else {
24
                row.addFirst(node.val);           // reversed order, O(1)
25
            }
26
            if (node.left != null) queue.offer(node.left);   // always L then R
27
            if (node.right != null) queue.offer(node.right);
28
        }
29
        result.add(row);
30
        leftToRight = !leftToRight;                // flip once per level
31
    }
32
    return result;
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7root = [1] — One level, leftToRight stays true → [[1]].Explore edge cases

Edge cases handled

root = [1]One level, leftToRight stays true → [[1]].
root = []Null root → return empty list immediately.
root = [1,2,3,4,null,null,5]Level 1 reversed → [3,2]; level 2 left-to-right → [4,5]. Confirms enqueue order untouched while output flips.

Pitfalls

Reversing the order children are enqueued — scrambles all deeper levels.
Flipping the flag per node instead of per level.
Reversing the finished row with O(width) work each odd level instead of O(1) front insertion.
Forgetting the empty-tree guard and returning a list with a phantom empty level.

03.2

Approach 2 of 2

Level-Order BFS Then Reverse Odd Rows

TimeO(n)SpaceO(n)

Offer as the simplest-to-explain variant — build normal level order, then reverse every other row. Note the small efficiency cost.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What if you ignore zigzag entirely first, producing plain left-to-right level order?

2Hint 2Explore hint

Once you have the list of rows, which ones are out of order? The odd-indexed levels.

3Hint 3Explore hint

Reverse each odd-indexed row in place at the end. Simpler to reason about, though reversing costs O(width) per odd row.

A · Core idea

This variant trades a hair of efficiency for maximum clarity: first produce the ordinary left-to-right level-order traversal, then post-process by reversing every odd-indexed row.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

BFS

level order = [[3],[9,20],[15,7]]

Staterows collected normally

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

C · Code with teaching comments

solution.javaJava

Level-Order BFS Then Reverse Odd Rows — reference

4 teaching notes

1
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
2
    List<List<Integer>> result = new ArrayList<>();
3
    if (root == null) return result;
4
    Queue<TreeNode> queue = new LinkedList<>();
5
    queue.offer(root);
6
    // Row 0 is not reversed; the flag toggles so odd rows get reversed.
7
    boolean reverse = false;
8
    while (!queue.isEmpty()) {
9
        int size = queue.size();
10
        List<Integer> row = new ArrayList<>();
11
        for (int i = 0; i < size; i++) {
12
            TreeNode node = queue.poll();
13
            row.add(node.val);                      // always natural order
14
            if (node.left != null) queue.offer(node.left);
15
            if (node.right != null) queue.offer(node.right);
16
        }
17
        if (reverse) Collections.reverse(row);      // fix odd rows
18
        result.add(row);
19
        // Alternate the reversal flag each level.
20
        reverse = !reverse;
21
    }
22
    return result;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Standard level-order BFS is O(n). Reversing the odd rows touches each element at most once more → still O(n) total. Output and queue are O(n) / O(w) space.

E · Edge cases and pitfalls7root = [1] — Single row, reverse stays false → [[1]].Explore edge cases

Edge cases handled

root = [1]Single row, reverse stays false → [[1]].
Full tree of 3 levelsRows 0 and 2 untouched, row 1 reversed — verifies only odd rows flip.
Wide last levelReversing the wide odd row is O(width), still within O(n) overall.

Pitfalls

Reversing even rows by toggling the flag in the wrong phase (initialize correctly).
Reversing while iterating, mutating the row mid-build.
Assuming the reversal changes complexity — it stays O(n).
Forgetting the empty-tree guard.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Flipping the child-enqueue order

Reversing which child you enqueue first to 'naturally' flip the next level scrambles the order of grandchildren — the corruption compounds down the tree. Keep enqueue order fixed.

Explore the code comparison

Don't write this

if (leftToRight) {
    if (node.left != null) queue.offer(node.left);
    if (node.right != null) queue.offer(node.right);
} else {
    if (node.right != null) queue.offer(node.right);   // wrong: corrupts deeper levels
    if (node.left != null) queue.offer(node.left);
}

Write this instead

if (node.left != null) queue.offer(node.left);   // always left then right
if (node.right != null) queue.offer(node.right);
// flip only where node.val is placed in the row

Toggling the flag per node

The direction is a property of the LEVEL, not the node. Flipping inside the inner loop alternates within a single row, producing garbage ordering.

Explore the code comparison

Don't write this

for _ in range(size):
    node = queue.popleft()
    if left_to_right:
        row.append(node.val)
    else:
        row.appendleft(node.val)
    left_to_right = not left_to_right   # wrong: flips per node

Write this instead

for _ in range(size):
    node = queue.popleft()
    if left_to_right:
        row.append(node.val)
    else:
        row.appendleft(node.val)
left_to_right = not left_to_right       # flip once, after the level

O(width) reversal instead of O(1) front insertion

Building a list then reversing it on every other level repeats work. A deque lets you place each value at its final end in O(1), avoiding the reversal entirely.

Explore the code comparison

Don't write this

List<Integer> row = new ArrayList<>();
for (...) row.add(node.val);
if (!leftToRight) Collections.reverse(row);   // O(width) extra each odd level

Write this instead

LinkedList<Integer> row = new LinkedList<>();
for (...) {
    if (leftToRight) row.addLast(node.val);
    else row.addFirst(node.val);             // O(1), final position immediately
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Level-order BFS + per-level direction flag, insert front/back

Code pattern to memorize

leftToRight = true
while queue:
    size = len(queue)
    row = deque()
    for i in range(size):
        node = queue.popleft()
        if leftToRight: row.append(node.val)   # back
        else:           row.appendleft(node.val)# front
        enqueue node.left, node.right (always normally)
    result.append(list(row))
    leftToRight = not leftToRight

Rules to remember

1Keep the traversal identical every level — only the recording order flips.
2Use a deque per level: append to the back on left-to-right rows, push to the front on right-to-left rows.
3Toggle the direction flag once per level, after finishing the row — not per node.
4Always enqueue children left then right; reversing enqueue order corrupts the next level's nodes.
5Snapshot the queue size before the inner loop, exactly as in any level-order BFS.

Use this pattern when

Level-order output where alternate levels are reversed (serpentine / boustrophedon)
You need rows top-to-bottom but with flipping within-row order
Any 'snake' or 'zigzag' rendering of a tree by level
BFS is natural and you just need to control insertion order per row

Choose another pattern when

Plain left-to-right rows → Level Order Traversal (no flag)
Only a per-level aggregate, not the full row → Average/Max of Levels
Only the last node of each level → Right Side View
Order across levels (not within) matters → that's bottom-up Level Order II

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Binary Tree Level Order Traversal
The base problem — drop the direction flag and always record left-to-right.
Binary Tree Level Order Traversal II
Coming soon
Bottom-up level order — build normally then reverse the list of levels.
Binary Tree Right Side View
Same BFS, but keep only the last node of each level.
Average of Levels in Binary Tree
Same level-freeze loop, reducing each level to its average.

Same pattern

←

Average of Levels in Binary Tree

Continue · Next problem

Count Complete Tree Nodes