141. Binary Tree Zigzag Level Order Traversal

🔗 LeetCode Problem: 103. Binary Tree Zigzag Level Order Traversal
📊 Difficulty: Medium
🏷️ Topics: Binary Trees, BFS, Queue, Level Order, Deque

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints: - The number of nodes in the tree is in the range [0, 2000] - -100 <= Node.val <= 100

---

🌳 Visual Understanding - The Zigzag Pattern!

What is Zigzag Traversal?

Zigzag = Alternate direction at each level

Normal Level Order:
       3           → [3]
      / \
     9   20       → [9, 20]
        /  \
       15   7     → [15, 7]

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


Zigzag Level Order:
       3           → [3] (left to right)
      / \
     9   20       → [20, 9] (right to left!) ⚡
        /  \
       15   7     → [15, 7] (left to right)

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

Pattern: Alternate direction every level!

Visual Direction Pattern:

Tree:
              3                    Level 0: →  [3]
            /   \
           9     20                Level 1: ← [20, 9]
                /  \
               15   7              Level 2: → [15, 7]

Direction by level:
  Level 0 (even): Left → Right
  Level 1 (odd):  Right → Left
  Level 2 (even): Left → Right
  Level 3 (odd):  Right → Left
  ...

Pattern: level % 2 == 0 → LTR, else RTL

Example with More Levels:

Tree:
           1
         /   \
        2     3
       / \   / \
      4   5 6   7
     /
    8

Level 0: →  [1]
Level 1: ← [3, 2]
Level 2: →  [4, 5, 6, 7]
Level 3: ← [8]

Result: [[1], [3, 2], [4, 5, 6, 7], [8]]

Notice: Direction flips each level!

---

🧠 The AHA Moment - Building on Problem 140!

From Level Order to Zigzag:

Problem 140: Level Order
  [[3], [9, 20], [15, 7]]
  All left to right

Problem 141: Zigzag Level Order
  [[3], [20, 9], [15, 7]]
  Alternate directions

Difference: ONLY the order within each level!

Solution: Same BFS + Reverse alternate levels!

Three Approaches to Reversal:

Approach 1: BFS + Reverse
  - Do normal level order
  - Reverse odd levels
  - Simplest to understand

Approach 2: BFS + Direction Flag
  - Track left-to-right vs right-to-left
  - Add nodes in correct order during BFS
  - More efficient (no reversal)

Approach 3: Two Stacks
  - One for current level
  - One for next level
  - Natural zigzag with LIFO
  - Most complex but interesting

---

🎯 Solution 1: BFS + Reverse (Simplest)

Implementation:

class Solution {
    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;  // Direction flag

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

            // Normal level order traversal
            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);
            }

            // Reverse if right to left
            // WHY? Odd levels need reverse order
            if (!leftToRight) {
                Collections.reverse(currentLevel);
            }

            result.add(currentLevel);
            leftToRight = !leftToRight;  // Flip direction
        }

        return result;
    }
}

Why This Works:

Level 0 (leftToRight = true):
  Process: [3]
  No reverse → [3]
  Flip: leftToRight = false

Level 1 (leftToRight = false):
  Process: [9, 20]
  Reverse → [20, 9] ✓
  Flip: leftToRight = true

Level 2 (leftToRight = true):
  Process: [15, 7]
  No reverse → [15, 7]

Pattern works perfectly!

---

🎯 Solution 2: BFS + Insert at Right Position (More Efficient)

Implementation:

class Solution {
    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> currentLevel = new LinkedList<>();

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

                // Add at correct position based on direction
                if (leftToRight) {
                    currentLevel.addLast(node.val);   // Normal: add at end
                } else {
                    currentLevel.addFirst(node.val);  // Reverse: add at front
                }

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

            result.add(currentLevel);
            leftToRight = !leftToRight;
        }

        return result;
    }
}

How addFirst Creates Reverse:

Level 1 (right to left):
  Process nodes: 9, 20 (in queue order)

  Process 9:
    addFirst(9) → [9]

  Process 20:
    addFirst(20) → [20, 9]  ✓

Result: [20, 9] without explicit reverse!

Why it works:
  addFirst = insert at beginning
  Last processed appears first
  Creates reverse order naturally!

---

🎯 Solution 3: DFS with Level Tracking

Implementation:

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) {
            return;
        }

        // Create list for this level if needed
        if (level == result.size()) {
            result.add(new LinkedList<>());
        }

        // Get the list for current level
        LinkedList<Integer> levelList = (LinkedList<Integer>) result.get(level);

        // Add based on level parity
        if (level % 2 == 0) {
            levelList.addLast(node.val);   // Even: left to right
        } else {
            levelList.addFirst(node.val);  // Odd: right to left
        }

        // Recurse on children
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }
}

Why DFS Works:

DFS visits: 3 → 9 → 20 → 15 → 7

Level 0 (even):
  Visit 3 → addLast(3) → [3]

Level 1 (odd):
  Visit 9 → addFirst(9) → [9]
  Visit 20 → addFirst(20) → [20, 9] ✓

Level 2 (even):
  Visit 15 → addLast(15) → [15]
  Visit 7 → addLast(7) → [15, 7]

Works! But visit order doesn't match level order.
Result is still correct! 🎯

---

🔍 Detailed Dry Run - BFS with Reverse

Tree:
       3
      / \
     9   20
        /  \
       15   7

Complete Execution:

INITIAL:
  queue = [3]
  result = []
  leftToRight = true

═══════════════════════════════════════
ITERATION 1 - Level 0:
═══════════════════════════════════════

leftToRight = true
levelSize = 1
currentLevel = []

For i = 0:
  node = poll() = 3
  currentLevel.add(3) → [3]

  Add children: 9, 20
  queue = [9, 20]

Reverse? No (leftToRight = true)
currentLevel = [3]

result.add([3]) → [[3]]
leftToRight = false (flip!)

State:
  queue = [9, 20]
  result = [[3]]
  leftToRight = false

═══════════════════════════════════════
ITERATION 2 - Level 1:
═══════════════════════════════════════

leftToRight = false
levelSize = 2
currentLevel = []

For i = 0:
  node = poll() = 9
  currentLevel.add(9) → [9]

  No children
  queue = [20]

For i = 1:
  node = poll() = 20
  currentLevel.add(20) → [9, 20]

  Add children: 15, 7
  queue = [15, 7]

Reverse? YES (leftToRight = false)
Collections.reverse([9, 20]) → [20, 9] ✓

result.add([20, 9]) → [[3], [20, 9]]
leftToRight = true (flip!)

State:
  queue = [15, 7]
  result = [[3], [20, 9]]
  leftToRight = true

═══════════════════════════════════════
ITERATION 3 - Level 2:
═══════════════════════════════════════

leftToRight = true
levelSize = 2
currentLevel = []

For i = 0:
  node = poll() = 15
  currentLevel.add(15) → [15]

  No children
  queue = [7]

For i = 1:
  node = poll() = 7
  currentLevel.add(7) → [15, 7]

  No children
  queue = []

Reverse? No (leftToRight = true)
currentLevel = [15, 7]

result.add([15, 7]) → [[3], [20, 9], [15, 7]]
leftToRight = false (flip!)

State:
  queue = []
  result = [[3], [20, 9], [15, 7]]

═══════════════════════════════════════
DONE! Queue is empty.
═══════════════════════════════════════

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

---

🔍 Dry Run - addFirst/addLast Approach

Tree:
       3
      / \
     9   20

Level-by-Level with Direction:

LEVEL 0 (leftToRight = true):
═══════════════════════════════════════

currentLevel = []

Process 3:
  leftToRight? YES
  addLast(3) → [3]

Add children: 9, 20
currentLevel = [3]

result = [[3]]
Flip: leftToRight = false

LEVEL 1 (leftToRight = false):
═══════════════════════════════════════

currentLevel = []

Process 9:
  leftToRight? NO
  addFirst(9) → [9]

Process 20:
  leftToRight? NO
  addFirst(20) → [20, 9]  ← Reversed naturally!

currentLevel = [20, 9]

result = [[3], [20, 9]]
Flip: leftToRight = true

═══════════════════════════════════════

FINAL: [[3], [20, 9]]

No explicit reverse needed!
addFirst creates reverse order automatically! 🎯

---

📊 Comparison of Approaches

Approach 1: BFS + Reverse

// Collect normally
currentLevel.add(node.val);

// Reverse if needed
if (!leftToRight) {
    Collections.reverse(currentLevel);
}

Pros:
  ✓ Easiest to understand
  ✓ Clean separation of concerns
  ✓ Uses ArrayList (efficient)

Cons:
  ✗ O(k) extra time per reversed level
  ✗ Modifies list after creation

Time: O(n) + O(k) for reversals
Space: O(n)

Approach 2: BFS + addFirst/addLast

// Add in correct position
if (leftToRight) {
    currentLevel.addLast(node.val);
} else {
    currentLevel.addFirst(node.val);
}

Pros:
  ✓ No explicit reverse needed
  ✓ More efficient (no extra pass)
  ✓ Builds correctly from start

Cons:
  ✗ Uses LinkedList (slightly slower per operation)
  ✗ More thinking required

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

Approach 3: DFS with Level

if (level % 2 == 0) {
    levelList.addLast(node.val);
} else {
    levelList.addFirst(node.val);
}

Pros:
  ✓ No queue needed
  ✓ Recursive elegance
  ✓ Same zigzag effect

Cons:
  ✗ Less intuitive for level order
  ✗ DFS order doesn't match visual order
  ✗ Still needs LinkedList

Time: O(n)
Space: O(h) recursion + O(n) result

Which to Use?

For interviews: Approach 1 (BFS + Reverse)
  → Easiest to explain
  → Clear logic
  → Builds on Problem 140

For efficiency: Approach 2 (addFirst/addLast)
  → No extra reverse pass
  → Still clear
  → Good optimization to mention

For showing off: Approach 3 (DFS)
  → "Also works with DFS!"
  → Shows flexibility
  → But less natural

---

📊 Complexity Analysis

All Approaches:

Time Complexity: O(n)

Visit each node once: O(n)

Approach 1 (with reverse):
  Reverse operations: O(k) per level
  But k ≤ n/2 for any level
  Amortized: O(n) total

Approach 2 & 3:
  No reverse: O(n) directly

All approaches: O(n) overall

Space Complexity: O(n)

Queue: O(w) where w = max width
Result: O(n) for all nodes

Approach 1 & 2:
  Queue-based: O(w) + O(n) = O(n)

Approach 3:
  Recursion: O(h) + O(n) = O(n)

All approaches: O(n) space

---

⚠️ Common Mistakes

Mistake 1: Forgetting to Flip Direction

// ❌ WRONG - Direction never changes!
boolean leftToRight = true;

while (!queue.isEmpty()) {
    // ... process level ...

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

    // Missing: leftToRight = !leftToRight;
}

// All levels reversed or none!

// ✓ CORRECT - Flip each time
leftToRight = !leftToRight;  // Add this!

Mistake 2: Wrong Level Parity Check

// ❌ WRONG - Backwards logic!
if (leftToRight) {
    Collections.reverse(currentLevel);  // Reverse when LTR?
}

// ✓ CORRECT - Reverse when right to left
if (!leftToRight) {
    Collections.reverse(currentLevel);
}

// OR with level number
if (level % 2 == 1) {  // Odd levels
    Collections.reverse(currentLevel);
}

Mistake 3: Using ArrayList with addFirst

// ❌ WRONG - ArrayList doesn't have addFirst!
List<Integer> currentLevel = new ArrayList<>();

if (leftToRight) {
    currentLevel.addLast(node.val);   // No such method!
} else {
    currentLevel.addFirst(node.val);  // No such method!
}

// ✓ CORRECT - Use LinkedList
LinkedList<Integer> currentLevel = new LinkedList<>();

if (leftToRight) {
    currentLevel.addLast(node.val);   // Works!
} else {
    currentLevel.addFirst(node.val);  // Works!
}

Mistake 4: Reversing After Adding to Result

// ❌ WRONG - Reverses in result list!
result.add(currentLevel);

if (!leftToRight) {
    Collections.reverse(currentLevel);  // Too late!
}

// currentLevel is already in result
// Reverse affects the list in result!

// ✓ CORRECT - Reverse before adding
if (!leftToRight) {
    Collections.reverse(currentLevel);
}

result.add(currentLevel);  // Add after reversing

Mistake 5: Starting with Wrong Direction

// ❌ WRONG - Starts with false
boolean leftToRight = false;  // Level 0 should be LTR!

// Result: First level reversed incorrectly

// ✓ CORRECT - Start with true
boolean leftToRight = true;  // Level 0 is LTR

---

🎯 Pattern Recognition - Level Order Variations

Core Pattern: Level Order + Modification

Template for level order variations:

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

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);
    }

    // MODIFY HERE based on problem!
    modifyLevel(currentLevel, level);

    result.add(currentLevel);
}

Related Problems:

1. Binary Tree Level Order (Problem 140)

Base problem - no modification
Just collect levels as-is

Modification: None

2. Binary Tree Zigzag (Problem 141)

Alternate direction per level

Modification: Reverse odd levels
if (level % 2 == 1) reverse(level);

3. Binary Tree Right Side View

Only rightmost node per level

Modification: Take last node
result.add(currentLevel.get(levelSize - 1));

4. Average of Levels

Calculate average per level

Modification: Compute average
double avg = sum / levelSize;

5. Binary Tree Level Order Bottom-Up

Return levels bottom to top

Modification: Reverse result at end
Collections.reverse(result);

6. Maximum Level Sum

Find level with maximum sum

Modification: Track max sum
maxSum = Math.max(maxSum, currentSum);

When to Use This Pattern:

✓ Problem mentions "level"
✓ Need to process by layers
✓ Level-based calculation
✓ Direction alternation
✓ Level-specific operations
✓ Horizontal tree processing

---

📝 Quick Revision Notes

🎯 Core Concept

Zigzag = Level order with alternating direction. Level 0: left→right, Level 1: right→left, Level 2: left→right, etc. Three approaches: (1) BFS + reverse odd levels (simplest), (2) BFS + addFirst for odd levels (efficient), (3) DFS with level % 2 check (alternative). Use boolean flag to track direction, flip after each level. Build on Problem 140!

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

    public static TreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0 || arr[0] == null) {
            return null;
        }

        TreeNode root = new TreeNode(arr[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while (!queue.isEmpty() && i < arr.length) {
            TreeNode current = queue.poll();

            // Process left child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.left = new TreeNode(arr[i]);
                    queue.offer(current.left);
                }
                i++;
            }

            // Process right child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.right = new TreeNode(arr[i]);
                    queue.offer(current.right);
                }
                i++;
            }
        }

        return root;
    }

    public static void print(TreeNode root) {
        if (root == null) {
            System.out.println("[]");
            return;
        }

        List<String> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                result.add(String.valueOf(node.val));
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                result.add("null");
            }
        }

        while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
            result.remove(result.size() - 1);
        }

        System.out.println(result);
    }    
}

class Solution {
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if(root == null) {
      return res;
    }

    // zigzagLevelOrderHelper(root, res); // using arraylist
    zigzagLevelOrderHelperOptimized(root, res); // using linkedlist

    return res;
  }

  private void zigzagLevelOrderHelperOptimized(TreeNode root, List<List<Integer>> res) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int level = 1;

    while (!queue.isEmpty()) {
      // process the current level.
      int size = queue.size();
      Deque<Integer> temp = new LinkedList<>();
      for(int i = 0; i < size; i++) {
        TreeNode curr = queue.poll();
        if(level % 2 == 0) {          
          temp.addFirst(curr.val);
        } else {
          temp.addLast(curr.val);
        }        

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

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

      res.add(new ArrayList<>(temp));
      level++;
    }
  }

  private void zigzagLevelOrderHelper(TreeNode root, List<List<Integer>> res) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int level = 1;

    while (!queue.isEmpty()) {
      // process the current level.
      int size = queue.size();
      List<Integer> temp = new ArrayList<>();      
      for(int i = 0; i < size; i++) {
        TreeNode curr = queue.poll();
        temp.add(curr.val);

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

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

      if(level % 2 == 0) {
        Collections.reverse(temp);
      }

      res.add(new ArrayList<>(temp));
      level++;
    }
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.zigzagLevelOrder(TreeNode.buildTree(new Integer[] {3,9,20,null,null,15,7})));
    System.out.println(s.zigzagLevelOrder(TreeNode.buildTree(new Integer[] {1})));
    System.out.println(s.zigzagLevelOrder(TreeNode.buildTree(new Integer[] {})));
  }
}

🔑 Key Insights

Building on Problem 140:

Problem 140: Level Order
  [[3], [9, 20], [15, 7]]

Problem 141: Zigzag
  [[3], [20, 9], [15, 7]]
         ↑───↑  Reversed!

Difference: Just reverse alternate levels!

This is COMPOSITION:
  Level Order + Conditional Reverse = Zigzag

Reuse what you know! 🔧

The Direction Flag Pattern:

boolean leftToRight = true;

while (...) {
    // Use flag
    if (!leftToRight) {
        reverse();
    }

    // CRITICAL: Flip flag!
    leftToRight = !leftToRight;
}

Forget to flip → All same direction!

addFirst Magic:

Normal order (addLast):
  add(9) → [9]
  add(20) → [9, 20]

Reverse order (addFirst):
  addFirst(9) → [9]
  addFirst(20) → [20, 9]  ← Automatic reverse!

Last added appears first = reverse! 🎯

🎪 Memory Aid

"Zigzag: flip the flag!"
"Odd levels: reverse or addFirst!"
"Even left, odd right!"
"Level 140 + reverse = 141!" ✨

⚠️ Don't Forget

• Flip direction flag (after each level!)
• Reverse BEFORE adding (not after!)
• Use LinkedList (for addFirst/addLast)
• Level 0 starts LTR (leftToRight = true)
• Odd levels reverse (level % 2 == 1)
• Build on level order (don't reinvent!)

---

🎉 Congratulations!

You've mastered level order variations!

What You Learned:

✅ Zigzag pattern - Alternating directions
✅ Three approaches - Reverse, addFirst, DFS
✅ Direction tracking - Boolean flag technique
✅ Problem composition - Building on Problem 140
✅ LinkedList usage - addFirst/addLast operations
✅ Level order template - Reusable with modifications

Pattern Evolution:

Problem 140: Level Order (Base)
  - BFS with queue
  - Level-by-level processing
  - Foundation pattern

Problem 141: Zigzag (Variation)
  - Same BFS structure
  - Add direction logic
  - Composition pattern!

Formula: Base Pattern + Modification = New Problem

The Composition Power:

You didn't start from scratch!

You took Problem 140 and added:
  1. Direction flag
  2. Conditional reverse
  3. Direction flip

3 small changes → new problem solved! 💪

This is how experts solve problems!
Not by memorizing, but by COMPOSING! 🎯

Next Level-Order Problems:

All use the same template: - Right Side View (last node per level) - Bottom-Up Level Order (reverse result) - Average of Levels (sum/count per level) - Max Level Sum (track max)

You have the toolkit! 🧰🌳✨