Zigzag Traversal (Alternating Level Order)

• BFS core – use the same queue and level-size snapshot as standard level order.
• Direction flag – a boolean leftToRight flips after each level.
• Append vs prepend – on left-to-right levels, add values to the end; on right-to-left levels, add values at the front.
• Queue order unchanged – always enqueue children left then right; the zigzag is purely in placement.
• Complexity – O(n) time, O(w) space; using a LinkedList makes front insertion O(1).

What is Zigzag Level Order Traversal?

Zigzag level order traversal visits a binary tree level by level, but alternates the reading direction at each level. Level 0 is left to right, level 1 is right to left, level 2 is left to right, and so on. The result is a list of lists with the zigzag pattern.

This is a direct variant of the Tree BFS pattern. The traversal itself is unchanged; only the presentation direction changes.

How does the direction flag work?

Keep a boolean leftToRight that starts as true and flips after each level. The queue still enqueues children left then right, maintaining the standard BFS order. The zigzag comes purely from how values are placed into the current level's list.

package com.bank.service;

import java.util.*;

public class ZigzagHierarchyPrinter {

    static class TreeNode {
        int amount;
        TreeNode left, right;
        TreeNode(int val) { this.amount = val; }
    }

    public static 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.amount);
                } else {
                    level.addFirst(node.amount);
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
            leftToRight = !leftToRight;
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1000);
        root.left = new TreeNode(500);
        root.right = new TreeNode(800);
        root.left.left = new TreeNode(200);
        root.left.right = new TreeNode(300);
        root.right.left = new TreeNode(600);
        root.right.right = new TreeNode(400);

        System.out.println("Zigzag: " + zigzagLevelOrder(root));
    }
}

Zigzag: [[1000], [800, 500], [200, 300, 600, 400]]

Why keep traversal constant and change only placement?

Changing the dequeue or enqueue order is an alternative approach but is more error-prone. Keeping traversal constant and changing only where values go in the list cleanly separates concerns.

// CLEAN: traverse normally, change placement
if (leftToRight) level.addLast(val);
else level.addFirst(val);

// ERROR-PRONE: changing dequeue order
// Reversing dequeue order requires a deque and careful child ordering
// Easy to introduce bugs with left/right confusion

How is this different from standard level order?

| Aspect | Standard Level Order | Zigzag Level Order |
|---|---|---|
| Direction | Always left to right | Alternates per level |
| Queue order | Left then right | Left then right (same) |
| Value placement | Always append | Append or prepend based on flag |
| Extra state | None | One boolean flag |

The only difference is one boolean and the conditional placement. The traversal loop is identical.

Why use a LinkedList for the level list?

A LinkedList makes addFirst() an O(1) operation. An ArrayList add(0, val) shifts all elements, making each reversed level O(level_size) per insertion, which is O(level_size^2) total for that level.

// SLOW: ArrayList front insertion
ArrayList<Integer> level = new ArrayList<>();
level.add(0, val); // O(n) shift per insertion

// FAST: LinkedList front insertion
LinkedList<Integer> level = new LinkedList<>();
level.addFirst(val); // O(1)

What are the edge cases?

• Null root – return empty list.
• Single node – return [[root.val]] (left to right, trivially).
• Two levels – first level left-to-right, second level right-to-left.
• Unbalanced tree – levels with one node are the same in either direction.

// Single node
System.out.println(zigzagLevelOrder(new TreeNode(42))); // [[42]]

What are common mistakes?

The most common mistake is fiddling with the enqueue order instead of the placement, leading to children being processed in the wrong order on the next level.

// WRONG: reversing enqueue order
if (!leftToRight) {
    if (node.right != null) queue.offer(node.right); // right first
    if (node.left != null) queue.offer(node.left);
}
// This changes the order for the NEXT level's traversal,
// causing cascading errors across levels

// CORRECT: always enqueue left then right
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
// Zigzag is only in addFirst vs addLast

What is the time and space complexity?

Time is O(n) because every node is processed once. Space is O(w) for the queue where w is the maximum width. Using LinkedList for the level list ensures that front insertion does not add overhead beyond O(1) per node.

What should a senior engineer know?

A senior engineer should articulate the design principle: keep traversal fixed and change only the presentation. This same principle applies to reverse level order (add level at front of result) and other BFS variants. It is the hallmark of a well-structured BFS solution.