Zigzag Level Order Traversal

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

Input/Output Specifications

• Input: The root of a binary tree where 0 <= number of nodes <= 2000 and -100 <= Node.val <= 100
• Output: A list of lists containing node values in zigzag level order

Constraints

• 0 <= number of nodes <= 2000
• -100 <= Node.val <= 100

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Explanation:
    3
   / \
  9  20
    /  \
   15   7
Level 0: [3] (left to right)
Level 1: [20,9] (right to left)
Level 2: [15,7] (left to right)

Example 2:

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

Example 3:

Input: root = []
Output: []

Solution Approaches

Approach 1: BFS with Level Tracking - Optimal

Algorithm Explanation:

1. Use BFS to traverse the tree level by level
2. Keep track of the current level
3. Reverse the order of nodes for odd levels (1, 3, 5, …)
4. Use a queue to process nodes level by level

Implementation:

Python:

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzagLevelOrder(root):
    """
    Zigzag level order traversal using BFS
    Time: O(n)
    Space: O(n)
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    level = 0
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Reverse for odd levels (1, 3, 5, ...)
        if level % 2 == 1:
            current_level.reverse()
        
        result.append(current_level)
        level += 1
    
    return result

Java:

import java.util.*;

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

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);
        int level = 0;
        
        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);
                }
            }
            
            // Reverse for odd levels (1, 3, 5, ...)
            if (level % 2 == 1) {
                Collections.reverse(currentLevel);
            }
            
            result.add(currentLevel);
            level++;
        }
        
        return result;
    }
}

Complexity Analysis:

• Time Complexity: O(n) - Visit each node exactly once
• Space Complexity: O(n) - Queue can store at most n nodes

Key Insights

1. Level Order Traversal: Use BFS to process nodes level by level
2. Zigzag Pattern: Reverse the order for odd levels (1, 3, 5, …)
3. Level Tracking: Keep track of current level to determine reversal
4. Queue Management: Process all nodes at current level before moving to next

Edge Cases

1. Empty Tree: Return empty list
2. Single Node: Return single level with one node
3. Two Levels: Handle the first reversal correctly
4. Skewed Tree: Ensure proper level tracking
5. Complete Tree: Verify correct zigzag pattern

Test Cases

def test_zigzagLevelOrder():
    # Test case 1
    root1 = TreeNode(3)
    root1.left = TreeNode(9)
    root1.right = TreeNode(20)
    root1.right.left = TreeNode(15)
    root1.right.right = TreeNode(7)
    assert zigzagLevelOrder(root1) == [[3], [20, 9], [15, 7]]
    
    # Test case 2
    root2 = TreeNode(1)
    assert zigzagLevelOrder(root2) == [[1]]
    
    # Test case 3
    assert zigzagLevelOrder(None) == []
    
    print("All tests passed!")

test_zigzagLevelOrder()

Follow-up Questions

1. Level Order Traversal: How would you do regular level order traversal?
2. Bottom-up Level Order: Traverse from bottom to top?
3. Spiral Order: Traverse in spiral order?
4. Vertical Order: Traverse in vertical order?
5. Diagonal Traversal: Traverse diagonally?

Common Mistakes

1. Wrong Level Tracking: Not properly tracking which level to reverse
2. Incorrect Reversal: Reversing wrong levels or not reversing at all
3. Queue Management: Not processing all nodes at current level
4. Edge Case Handling: Not handling empty tree or single node
5. Index Confusion: Mixing up 0-based and 1-based level indexing

Interview Tips

1. Start with BFS: Explain the level order traversal approach
2. Discuss Zigzag Logic: Explain when and how to reverse levels
3. Handle Edge Cases: Mention empty tree and single node cases
4. Code Carefully: Pay attention to level tracking and reversal logic
5. Discuss Alternatives: Mention DFS approach as alternative

Concept Explanations

Level Order Traversal: A tree traversal method where nodes are processed level by level, from left to right within each level. This is typically implemented using BFS with a queue.

Zigzag Pattern: An alternating pattern where levels are traversed left-to-right and right-to-left alternately. This creates a zigzag effect when visualizing the traversal.

BFS vs DFS: BFS naturally processes nodes level by level, making it ideal for level order problems. DFS can also be used but requires additional level tracking.

When to Use: Use this pattern when you need to process tree nodes level by level with some modification to the standard left-to-right order, such as reversing alternate levels or applying different logic to different levels.