☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Zig Zag or Spiral Traversal

Medium TUF ID 126 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return its zigzag level order traversal: the values level by level from top to bottom, where the first level (the root) is read left to right, the second right to left, the third left to right again, and so on. Return a list with one inner list per level. An empty tree gives an empty list.

Constraints: 0 ≤ n ≤ 2000 nodes in the LeetCode version, values fit in an int.

Example 1

tree (level order) = [3, 9, 20, null, null, 15, 7]

     3
    / \
   9   20
      /  \
     15   7

answer = [[3], [20, 9], [15, 7]]      // level 1 is read right to left

Example 2

tree (level order) = [1, 2, 3, 4, 5, 6, 7]

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

answer = [[1], [3, 2], [4, 5, 6, 7]]

This is ordinary level order traversal with one twist: every second level comes out reversed. The interesting part is choosing where to do the reversing. The node visiting order can stay a normal breadth-first order; only the order in which values are written down needs to alternate.

Approach 1: Level order, then reverse every second level

Intuition. Do a standard BFS, collecting one list per level. Keep a boolean leftToRight that flips after every level, and when it is false reverse the list before storing it. This is the simplest correct solution and the natural first answer.

Algorithm.

  1. If the root is null, return an empty list. Otherwise enqueue the root and set leftToRight = true.
  2. While the queue is not empty:
    • Let size be the queue size and poll size nodes into row, enqueuing their existing children left then right.
    • If leftToRight is false, reverse row.
    • Append row and flip leftToRight.
  3. Return the list of rows.
static List<List<Integer>> reverseAlternateLevels(TreeNode root) {
    List<List<Integer>> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    boolean leftToRight = true;
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> row = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            row.add(node.val);
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        if (!leftToRight) Collections.reverse(row);
        out.add(row);
        leftToRight = !leftToRight;
    }
    return out;
}

Complexity. Time O(n): each node is enqueued and polled once, and reversing a level costs its length, so all reversals together cost O(n). Space O(w) beyond the output, where w is the widest level.

Approach 2: Two stacks

Intuition. A stack reverses the order of whatever is pushed onto it, and zigzag is “reverse the direction at every level”. So hold the current level in one stack and push the children into a second stack. Popping a stack always produces the reverse of the push order, so if we are careful about which child we push first, the next level automatically comes out in the opposite direction:

Algorithm.

  1. Push the root onto cur; leftToRight = true.
  2. While cur is not empty: create an empty next stack and row; pop every node from cur, append it to row, and push its children onto next in the order given above. Append row, set cur = next, flip leftToRight.
static List<List<Integer>> twoStacks(TreeNode root) {
    List<List<Integer>> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> cur = new ArrayDeque<>();
    cur.push(root);
    boolean leftToRight = true;
    while (!cur.isEmpty()) {
        Deque<TreeNode> next = new ArrayDeque<>();
        List<Integer> row = new ArrayList<>();
        while (!cur.isEmpty()) {
            TreeNode node = cur.pop();
            row.add(node.val);
            if (leftToRight) {
                if (node.left != null) next.push(node.left);
                if (node.right != null) next.push(node.right);
            } else {
                if (node.right != null) next.push(node.right);
                if (node.left != null) next.push(node.left);
            }
        }
        out.add(row);
        cur = next;
        leftToRight = !leftToRight;
    }
    return out;
}

Dry run on Example 2:

level read direction pop order pushed onto next (bottom to top) row
0 left to right 1 2, 3 [1]
1 right to left 3, 2 7, 6, 5, 4 [3, 2]
2 left to right 4, 5, 6, 7 nothing [4, 5, 6, 7]

Complexity. Time O(n): each node is pushed and popped once. Space O(w): the two stacks together hold at most two adjacent levels. The approach is elegant and is a classic interview alternative, but it is easy to get the push order wrong, so verify it on a three-level tree as in the table.

Approach 3: Optimal, write each value into its final slot

Intuition. In Approach 1 we write the values of a reversed level in the wrong order and then fix them. But at the start of each level we already know its size, so we know where each value belongs: the i-th node polled from the queue (always in left-to-right order) goes to index i on a left-to-right level, and to index size - 1 - i on a right-to-left level. Allocate the row with exactly size slots and write each value straight into place. The BFS stays completely standard, and there is no second pass over any level.

Algorithm.

  1. Standard BFS with leftToRight = true.
  2. For each level of size nodes, create an array row of length size.
  3. For the i-th polled node, store its value at i if leftToRight, else at size - 1 - i; enqueue its children left then right.
  4. Append the row, flip leftToRight.
static List<List<Integer>> optimal(TreeNode root) {
    List<List<Integer>> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    boolean leftToRight = true;
    while (!q.isEmpty()) {
        int size = q.size();
        Integer[] row = new Integer[size];
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            row[leftToRight ? i : size - 1 - i] = node.val;
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        out.add(new ArrayList<>(Arrays.asList(row)));
        leftToRight = !leftToRight;
    }
    return out;
}

The row is built as an Integer[] so that it can be wrapped with Arrays.asList (which would not work on an int[]), then copied into an ArrayList so that the caller receives an ordinary modifiable list.

Complexity. Time O(n): one constant-time write per node. Space O(w) for the queue. All three approaches have the same asymptotic cost; this one does the least work per node and keeps the traversal itself untouched, which makes it the easiest to reason about.

Edge cases and pitfalls