#103 Binary Tree Zigzag Level Order Traversal

frequently reported atAmazon Microsoft Bloomberg LinkedIn Google Meta

the problem

In plain words

Return the values level by level, alternating direction: level 0 left to right, level 1 right to left, level 2 left to right again, and so on.

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

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

in root = [1]

out [[1]]

in root = []

out []

0 ≤ number of nodes ≤ 2000
-100 ≤ Node.val ≤ 100

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree BFS (level order)

Keep the BFS exactly as it is — nodes always come out of the queue left to right. Change only where each value goes in its level's list: at the back on even levels, at the front on odd levels.

solutions

From brute force to optimal

Normal size-snapshot BFS; before storing an odd level, Collections.reverse it.

BFS one level at a time.
If the level number is odd, reverse its list.
Add it to the answer.

timeO(n)

Each node is polled once; reversing a level costs its size, so all reversals add up to n.

spaceO(w)

The queue and the current level.

javajava.util.*

1class Solution {2    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {3        List<List<Integer>> levels = new ArrayList<>();4        if (root == null) return levels;5        Deque<TreeNode> queue = new ArrayDeque<>();6        queue.offer(root);7        while (!queue.isEmpty()) {8            int size = queue.size();9            List<Integer> level = new ArrayList<>(size);10            for (int i = 0; i < size; i++) {11                TreeNode node = queue.poll();12                level.add(node.val);13                if (node.left != null) queue.offer(node.left);14                if (node.right != null) queue.offer(node.right);15            }16            if (levels.size() % 2 == 1) Collections.reverse(level);   // odd levels read right to left17            levels.add(level);18        }19        return levels;20    }21}

Collect each level in a Deque: addLast when going left to right, addFirst when going right to left.

leftToRight = true.
Per level: poll size nodes; addLast or addFirst each value.
Store the level as a list; flip leftToRight.

timeO(n)

Each node polled once; addFirst/addLast are O(1).

spaceO(w)

The queue and the current level.

javajava.util.*

1class Solution {2    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {3        List<List<Integer>> levels = new ArrayList<>();4        if (root == null) return levels;5        Deque<TreeNode> queue = new ArrayDeque<>();6        queue.offer(root);7        boolean leftToRight = true;8        while (!queue.isEmpty()) {9            int size = queue.size();10            Deque<Integer> level = new ArrayDeque<>(size);   // O(1) adds at either end11            for (int i = 0; i < size; i++) {12                TreeNode node = queue.poll();               // nodes always come out left to right13                if (leftToRight) level.addLast(node.val);14                else level.addFirst(node.val);              // right-to-left level: prepend instead15                if (node.left != null) queue.offer(node.left);16                if (node.right != null) queue.offer(node.right);17            }18            levels.add(new ArrayList<>(level));19            leftToRight = !leftToRight;                     // flip direction for the next level20        }21        return levels;22    }23}

in the room

How to say it in the interview

talk track

Write plain level order first, then add the one-line twist.
Say why you don't change the order children are offered: it would scramble the next level.

traps

Swapping the order you offer left and right children on odd levels — the next level comes out in a mixed, wrong order.
Prepending with ArrayList.add(0, x): each call shifts the whole list, O(w²) per level. Use a Deque, or reverse once.

what they ask next

Follow-ups

Two-stack version?

Pop from the current stack and push children onto the next one — left then right on even levels, right then left on odd levels. Also O(n).

Bottom-up level order (LC 107)?

Normal BFS, then Collections.reverse(levels) — or addFirst each level into a LinkedList.

before you submit

Edge cases to test

Empty tree → [].
One node → [[1]].
A chain: one value per level, so the direction never shows — but the code must still flip correctly.

practise next