Binary Tree Zigzag Level Order Traversal

Given the root of a binary tree, return the zigzag level order traversal of its node values. Even-depth levels are traversed left to right; odd-depth levels are traversed right to left.

Example 1

Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]] Explanation: Level 0 (L→R): [3]. Level 1 (R→L): [20,9]. Level 2 (L→R): [15,7].

Example 2

Input: root = [1] Output: [[1]]

Constraints:

0 <= Number of nodes <= 2000
-100 <= Node.val <= 100

Solution: BFS with Direction Flag
Complexity Analysis

Solution: BFS with Direction Flag

Standard BFS with a boolean leftToRight flag. For each level, collect the node values in a LinkedList. When the flag is true, append values to the tail (left-to-right order); when false, prepend values to the head (right-to-left order). Toggle the flag after each level. Children are always enqueued left-before-right.

Algorithm:

Enqueue root; initialize leftToRight = true.
For each level, create a LinkedList<Integer>.
If leftToRight, add to the end (addLast); else add to the front (addFirst).
After the level, toggle leftToRight and add the list to results.

Java

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        LinkedList<Integer> level = new LinkedList<>();

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();

            if (leftToRight) {
                level.addLast(node.val);
            } else {
                level.addFirst(node.val); // prepend for R→L
            }

            if (node.left  != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        result.add(level);
        leftToRight = !leftToRight; // toggle direction
    }
    return result;
}

Trace through Example 1: root = [3,9,20,null,null,15,7]

Level	Direction	Nodes	Level output
0	L→R	3	[3]
1	R→L	9, 20	[20, 9]
2	L→R	15, 7	[15, 7]

Complexity Analysis

Time: O(n). Each node is processed exactly once; LinkedList head/tail operations are O(1).
Space: O(n). Queue holds at most n/2 nodes at the widest level.