Binary Tree Zigzag Level Order Traversal — Practice

Problem

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values (left to right, then right to left for the next level, alternating).

Examples

Example 1

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

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].

Constraints

•The number of nodes is in the range [0, 2000]

Hints

Hint 1

Start from plain BFS level-order traversal — process one level (queue snapshot) at a time.

Hint 2

The only new piece is direction: track whether the current level should be reversed before adding it to the result.

Hint 3

Don't reverse how you traverse the queue — collect the level normally, then reverse the resulting list only on alternate levels. Simpler and less error-prone than trying to alternate the traversal direction itself.

Solutions

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(); // snapshot — exactly this many nodes belong to the current level
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        if (!leftToRight) Collections.reverse(level);
        result.add(level);
        leftToRight = !leftToRight;
    }
    return result;
}

Time: O(n) · Space: O(n)