Binary Tree Zigzag Level Order Traversal

MediumTrees · BFS (Level Order)🧩 Tree BFS (Level Order)LeetCode #103 ↗Updated Oct 30, 2026

Problem

Given the root of a binary tree, return its values grouped level by level, but alternate the reading direction: the root level is read left to right, the next right to left, the one after left to right again, and so on.

Input[3,9,20,null,null,15,7]Output[[3],[20,9],[15,7]]

Input[1]Output[[1]]

Input[]Output[]

0 ≤ nodes ≤ 2000 · -100 ≤ Node.val ≤ 100

Try it yourself

Java

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Zigzag changes where a value is written, not the order nodes are visited. Do a normal left-to-right BFS and, on odd levels, place the i-th polled value at slot size - 1 - i.

PatternTree BFS (Level Order)

Instinct The answer talks about levels, rows, depth order, "closest to the root" or what you see from a side? Queue the tree and process it one level at a time.

Memory hack Freeze the size, drain the row - read n = queue.size() before the loop and one level never bleeds into the next.

Open the Tree BFS (Level Order) guide →

Approaches

Brute ForceHeight + DFS per Level, then Reverse

Time O(n · h)Space O(h)

Find the height h. For each depth d run a fresh DFS that collects only the nodes exactly d edges down (left before right), then reverse that list when d is odd. Upper levels get re-walked for every deeper level.

Java

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    int h = height(root);
    for (int d = 0; d < h; d++) {
        List<Integer> level = new ArrayList<>();
        collect(root, d, level);
        if (d % 2 == 1) Collections.reverse(level);
        res.add(level);
    }
    return res;
}
private int height(TreeNode node) {
    return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right));
}
private void collect(TreeNode node, int d, List<Integer> level) {
    if (node == null) return;
    if (d == 0) {
        level.add(node.val);
        return;
    }
    collect(node.left, d - 1, level);
    collect(node.right, d - 1, level);
}

Easy to get right, but a skewed tree (h = n) makes it quadratic.

BetterBFS, then Reverse Odd Levels

Time O(n)Space O(w)

Standard level-order BFS with a queue-size snapshot builds each level left to right in one pass. A level with an odd index is then reversed in place. Every node is enqueued, polled and reversed at most once.

Java

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        if (res.size() % 2 == 1) Collections.reverse(level); // odd level
        res.add(level);
    }
    return res;
}

Linear, but touches every odd-level value twice (write, then reverse).

OptimalBFS with Direct Slot Placement

Time O(n)Space O(w)

Visit nodes in the usual left-to-right BFS order, but write each value straight into its final slot: index i when reading left to right, index size - 1 - i otherwise. A boolean flips after each level, so no reversal pass is ever needed.

Java

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    boolean leftToRight = true;
    while (!queue.isEmpty()) {
        int size = queue.size();
        Integer[] level = new Integer[size];
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level[leftToRight ? i : size - 1 - i] = node.val; // final position
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(Arrays.asList(level));
        leftToRight = !leftToRight;
    }
    return res;
}

One write per value and the child-enqueue order never changes — hard to get wrong.

Pro tip

Never flip the child enqueue order to get zigzag — it scrambles the next level. Keep BFS order fixed and only change the write index.

At a glance

Level	Approach	Time	Space
Brute Force	Height + DFS per Level, then Reverse	`O(n · h)`	`O(h)`
Better	BFS, then Reverse Odd Levels	`O(n)`	`O(w)`
Optimal	BFS with Direct Slot Placement	`O(n)`	`O(w)`

Common pitfalls

Swapping the left/right enqueue order on odd levels — breaks the order of the level after.
Using queue.size() as the loop bound while children are being added.
Forgetting the empty tree → NPE on the first poll().

Interview tips

Say up front: “this is level order with a direction flag”.
Offer the reverse-each-odd-level version first, then remove the extra pass.
Mention the two-stack or deque (addFirst/addLast) variants as alternatives.

Pattern

BFS level-by-level + per-level transform → any traversal where each depth is emitted as a group with its own rule.

My notes saved in this browser