ZigZag Tree Traversal

Time: O(n)

Space: O(n)

Intuition

Level-order BFS with alternating direction. Collect each level normally, then reverse every other level (or use a deque and alternate front/back insertions).

Algorithm

1BFS level order (same as problem 102).
2For odd levels (0-indexed): reverse the level list before adding to result.

Example Walkthrough

Input: root = [3,9,20,null,null,15,7]

1.Level 0 (left-to-right): [3]. Level 1 (right-to-left): [20,9]. Level 2 (left-to-right): [15,7].

Output: [[3],[20,9],[15,7]]

Common Pitfalls

•Track level parity (odd/even) to know when to reverse.

ZigZag Tree Traversal.java

Java

// Approach: BFS level-order with a direction flag. Reverse alternate levels before adding to result.
// Time: O(n) Space: O(n)
import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int d) {
        data = d;
        left = right = null;
    }
}

class Solution {
    ArrayList<Integer> zigZagTraversal(Node root) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();

        int turn = 0;

        queue.offer(root);
        queue.offer(null);

        while (queue.size() > 1) {
            Node node = queue.poll();

            if (node == null) {
                queue.add(null);
                if (turn % 2 == 1)
                    Collections.reverse(list);
                turn++;
                ans.addAll(list);
                list = new ArrayList<>();
                continue;
            }

            list.add(node.data);

            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
        if (turn % 2 == 1)
            Collections.reverse(list);
        ans.addAll(list);
        return ans;
    }
}

Was this solution helpful?