A warehouse-slotting console stores a binary split tree: each node is a question (zone, then aisle, then bin). The picker HUD paints one strip per depth, but the eye snakes — even floors left to right, odd floors right to left — so a reviewer traces the tree like a printer head. The intern version ran full Level Order, then Collections.reverse on every other floor list. A dozen slots painted instantly. A slotting tree with tens of thousands of nodes still returned, but the second pass over the answer was furniture a reverse-after-drain already gives you.

Zigzag asks for the same floor groups as Level Order, with odd depths flipped right to left. The binary tree post owns level-order as a layout walk. The BFS post owns why the frontier is a FIFO ArrayDeque. Level Order is the same size snapshot; they keep each floor left to right, you reverse the odd ones. Do not paste a graph seen set or a shortest-path argument from that post.

The problem

Given the root of a binary tree, return its values grouped by depth: left to right on even floors (depth 0), right to left on odd floors. An empty tree returns an empty list. A single node returns [[val]].

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample trees and the snake return. Missing children do not leave holes — only live nodes appear. Zigzag flips the collected values, not which children you offer.

      8
     / \
    3   10
   / \    \
  1   6    14

→  [[8], [10, 3], [1, 6, 14]]


      8
     /
    3
     \
      5

→  [[8], [3], [5]]


(root = null)  →  []
[1]            →  [[1]]

Note: Depth 0 is even, so it stays left to right. Reversing a singleton is a no-op — a spine looks like Level Order. A single node is [[val]], not [val].

Collect every floor, then reverse the odd ones is the honest brute force

Run the Level Order drain, keep every floor list, then reverse the odd ones. Correct. Extra pass.

List<List<Integer>> zigzagFromFloors(List<List<Integer>> floors) {
    for (int i = 1; i < floors.size(); i += 2) {
        Collections.reverse(floors.get(i));
    }
    return floors;
}

At a dozen nodes this is a rounding error. At tens of thousands you paid a second walk of the answer for a flip the inner loop already owns: is this floor odd?

Snapshot size, reverse every other floor

Same drain as Level Order: offer the root, snapshot int size = q.size(), poll that many, offer left then right when they exist. After the inner loop, if ans.size() is odd, reverse the collected list, then append. Inserting at the front on odd floors (level.add(0, node.val)) is the same idea without a reverse.

Reverse the collected floor, not the queue. Flipping the deque (or offering right-then-left on odd floors while still polling from the front) scrambles which nodes sit on the next floor. Children always enqueue left then right; only the recorded values snake.

q: [8]
size=1  poll 8     offer 3, 10       level [8]         even → keep
q: [3, 10]
size=2  poll 3     offer 1, 6        level [3]
        poll 10    offer 14          level [3, 10]     odd  → reverse [10, 3]
q: [1, 6, 14]
size=3  poll 1, 6, 14                level [1, 6, 14]  even → keep
q: []

→ [[8], [10, 3], [1, 6, 14]]

The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack, not ArrayList.remove(0). Skip null children — ArrayDeque refuses null, and this prompt does not want holes.

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

Time is O(n) — each node is offered once and polled once; reverse per odd floor is still linear in n. Space is O(w) for the queue, w being the widest floor (plus the answer lists, which are the output). A perfect tree’s last floor is about n/2; a spine’s queue stays O(1). Do not quote a graph seen set; there is nothing to mark.

Note: Return [] for a null root before you offer. Offering null throws on ArrayDeque.

What interviewers usually poke next

  • Insert at front. On odd floors level.add(0, node.val) instead of reverse. Same drain, same left-then-right offer. ArrayList.add(0) is O(w) per insert; reverse-once is the cheaper flip.
  • Two ArrayDeques / either end. Alternate which end you poll, or keep one deque for left-to-right and one for right-to-left. Correct. Easy to scramble the next floor if children land on the wrong end. They may ask this after the reverse-after-drain; it is not the default. ArrayDeque, not java.util.Stack.
  • Right Side View. Same drain; keep only the last poll of each floor. Different keep. Right Side View.
  • DFS into buckets. Pass a depth index; grow List<List<Integer>> when depth == ans.size(), recurse left and right, then reverse odd buckets. Correct. A spine is O(n) frames.
  • Why no seen? A tree has no parent pointer back and at most two children. Mark-on-enqueue is the graph post’s cycle filter. Pasting it here is cargo.

You are done with this problem when you can snapshot q.size(), drain that many, reverse the odd floors, walk [[8], [10, 3], [1, 6, 14]] out loud, and say why you reverse the collected list, not the queue.