TreeMediumO(n) time · O(n) space

ZigZag Level Order Traversal

Mahabharata — The Vyuha Turns — Alternating Direction at Each Level of the Formation

विषम स्तर बायें से — सम स्तर दायें से। ZigZag व्यूह — बारी-बारी से दिशा बदलो॥

*Odd levels left to right — even levels right to left. ZigZag formation — alternate direction each level.*

The Story

Level order traversal but alternating left-to-right and right-to-left at each level.

For tree `[3,9,20,null,null,15,7]`: [[3],[20,9],[15,7]]. - Level 0 (odd depth? or just alternate): [3] (left to right) - Level 1: [20,9] (right to left) - Level 2: [15,7] (left to right)

**Same BFS as tr-4, but reverse odd levels:** ```java boolean leftToRight = true; while (!q.isEmpty()) { int size = q.size(); List<Integer> level = new ArrayList<>(); for (int i=0; i<size; i++) { TreeNode node = q.poll(); level.add(node.val); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } if (!leftToRight) Collections.reverse(level); // Reverse odd levels res.add(level); leftToRight = !leftToRight; // Toggle direction } ```

**Alternative: use LinkedList with addFirst/addLast:** ```java LinkedList<Integer> level = new LinkedList<>(); if (leftToRight) level.addLast(node.val); else level.addFirst(node.val); // Reverse order by inserting at front ``` This avoids the explicit reverse step — O(1) per node instead of O(size) reverse.

Both work correctly. The addFirst/addLast approach is slightly more efficient.

The DFS with Alternating Lists

DFS with depth. At odd depths, add values to front of level list; at even depths, add to back. O(n) time.

java

void dfsZigZag(TreeNode root, int depth, List<List<Integer>> res) {
    if (root == null) return;
    if (depth >= res.size()) res.add(new LinkedList<>());
    if (depth%2==0) ((LinkedList<Integer>)res.get(depth)).addLast(root.val);
    else ((LinkedList<Integer>)res.get(depth)).addFirst(root.val);
    dfsZigZag(root.left, depth+1, res);
    dfsZigZag(root.right, depth+1, res);
}

The Toggle-Direction BFS Wisdom

BFS level order + toggle leftToRight flag. Use LinkedList: addLast if leftToRight, addFirst if not. Or: addAll to list then reverse at odd levels.

java

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    boolean leftToRight = true;
    while (!q.isEmpty()) {
        int size = q.size();
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (leftToRight) level.addLast(node.val);
            else level.addFirst(node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
        leftToRight = !leftToRight;
    }
    return res;
}

Step-by-Step Walkthrough

Tree=[1,2,3]. Level0:[1](LR). Level1:[3,2](RL). Result=[[1],[3,2]] ✅

Deep Insight

**addFirst vs reverse:** `LinkedList.addFirst()` is O(1) per node. `Collections.reverse()` is O(size) per level. For large trees, addFirst/addLast is more efficient, though both are O(n) overall.

**The enqueue order stays the same:** We always enqueue left before right (or right before left is fine too, consistent is key). The zigzag effect comes only from how we ADD to the current level list (addFirst vs addLast), NOT from how we enqueue children.

**Common mistake:** Changing the enqueue order to achieve zigzag. Wrong! Keep BFS consistent, only change the collection order.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(n)	DFS with depth
Optimal	O(n)	O(n)	BFS with addFirst/addLast toggle

Pattern Recognition

✅ ZigZag = BFS level order + toggle direction
✅ Use LinkedList.addFirst()/addLast() for O(1) direction
✅ Toggle leftToRight flag after each level
✅ Enqueue children always left-then-right (don't change)

**LeetCode Trigger Phrases:**
→ "zigzag level order traversal"
→ Alternate left-right by level
→ BFS with per-level direction toggle

Mahabharata Reference

चक्रव्यूहः — अर्जुनस्य पुत्रः अभिमन्युः। एकेन द्वारेण प्रवेशः — निर्गमः अज्ञातः॥

The Chakra-vyuha formation — where Abhimanyu, son of Arjuna, entered through one door but knew not the way out.

Connection: The ZigZag vyuha (formation) is one of the great military strategies of the Mahabharata — alternating direction at each row of warriors, creating a pattern that confuses the enemy. The ZigZag traversal emulates this: each level of the tree is traversed in the opposite direction of the level above. The BFS queue processes each level faithfully, but the direction of recording alternates, creating the zigzag pattern of the legendary battle formations.