103 · Binary Tree Zigzag Level Order Traversal

Level order traversal (102) with one twist: alternate levels read right to left. The BFS mechanics don't change at all — only what you do with a level after you've already collected it.

1 — The problem

Produce the same grouped-by-level output as 102, except odd-indexed levels (0-indexed: the 2nd, 4th, ... level) are reversed. The traversal that discovers the nodes never changes direction — BFS always enqueues left child before right child, level after level. The zigzag is purely a post-processing decision applied once a level is already in hand.

This is the detail candidates trip on: they try to make the queue itself alternate direction (dequeue from the right on odd levels), which requires a real deque and careful index bookkeeping. It's unnecessary. Traverse normally, left to right, always; flip the finished list only when the level index is odd.

2 — Visualizing the traversal

Queue<TreeNode> q = new LinkedList<>();q.add(root);boolean leftToRight = true;while (!q.isEmpty()) {    int sz = q.size();    List<Integer> level = new ArrayList<>();    for (int i = 0; i < sz; i++) {        TreeNode nd = q.poll();        level.add(nd.val);        if (nd.left  != null) q.add(nd.left);        if (nd.right != null) q.add(nd.right);    }    if (!leftToRight) Collections.reverse(level);    result.add(level);    leftToRight = !leftToRight;}

Follow the second level closely: BFS still discovers 9 before 20 — left child before right child, exactly as always — so the level list is built in discovery order as [9, 20]. That level's index is 1, which is odd, so the reverse step flips it right before it's committed to the answer, producing [20, 9] as the actual zigzag entry. The traversal order underneath never changes; only the finished list gets flipped, and only on odd levels.

3 — Complexity and edge cases

• Time: O(n) — the traversal itself is unchanged from 102; reversing a level of size k costs O(k), and the levels partition all n nodes, so the total extra work is O(n).
• Space: O(n) for the queue in the worst case (a maximally wide level), plus O(n) for the output.
• Alternative: use an ArrayDeque as the level buffer and call addFirst instead of addLast on odd levels — avoids the explicit reverse pass but reads less obviously correct in review; prefer the reverse-after version unless the extra O(k) pass is a measured problem.
• Empty tree: empty result list.
• Single node: one level, trivially unaffected by direction.

4 — Reference implementation

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    boolean leftToRight = true;
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            TreeNode nd = q.poll();
            level.add(nd.val);
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
        if (!leftToRight) Collections.reverse(level);
        result.add(level);
        leftToRight = !leftToRight;
    }
    return result;
}