Problem 103: Binary Tree Zigzag Level Order Traversal

You are given the root of a binary tree.
Your task is to return its level order traversal, but with a twist:

Levels must alternate between left-to-right and right-to-left.

This pattern is commonly called a zigzag or spiral traversal.

Understanding the Problem

Example tree:

Expected output:

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

Explanation:
Level 0 → left to right → [3]
Level 1 → right to left → [20, 9]
Level 2 → left to right → [15, 7]

Approach (Explained in Simple Language)

We use a Breadth-First Search (BFS) approach to traverse the tree level-by-level.

1. Use a queue to perform normal level-order traversal

Push the root node into the queue and process nodes level by level.

2. For each level, collect all node values in a list

Process nodes in the queue until the level is complete.

3. Reverse the list of values for alternate levels

If the level number is odd, reverse the list.
If even, keep it as-is.

4. Add the processed list to the result

Repeat until the queue becomes empty.

This keeps the solution simple, readable, and efficient.

Java Code

import java.util.*;

public class ZigzagLevelOrderTraversal {

    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 reverse = false;

        while (!queue.isEmpty()) {

            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {

                TreeNode node = queue.poll();
                currentLevel.add(node.val);

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

            if (reverse) {
                Collections.reverse(currentLevel);
            }

            result.add(currentLevel);

            reverse = !reverse;
        }

        return result;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Dry Run

Use this tree:

Queue initially = [3]
reverse = false
result = []

Level 0

Queue = [3]
levelSize = 1
reverse = false

Process node 3 → currentLevel = [3]
Add children 9 and 20 to queue

Queue becomes [9, 20]

reverse is false → keep [3] as-is
result = [[3]]

Toggle reverse → true

Level 1

Queue = [9, 20]
levelSize = 2
reverse = true

Process node 9
currentLevel = [9]
children → none

Process node 20
currentLevel = [9, 20]
children → add 15 and 7

Queue = [15, 7]

reverse = true → reverse currentLevel → [20, 9]
result = [[3], [20, 9]]

Toggle reverse → false

Level 2

Queue = [15, 7]
levelSize = 2
reverse = false

Process node 15
currentLevel = [15]

Process node 7
currentLevel = [15, 7]

reverse = false → keep as-is
result = [[3], [20, 9], [15, 7]]

Toggle reverse → true
Queue becomes empty → done.

Why This Approach Works

Level-order traversal ensures we process nodes in the correct hierarchical order.
By simply reversing alternate levels, we achieve the zigzag pattern without affecting child processing.

Advantages:

Easy to implement
O(n) time, since each node is visited once
Uses simple queue-based BFS