Binary Tree ZigZag Level Order Traversal [Easy BFS + LinkedList]

103.Binary Tree Zigzag Level Order Traversal

Tree

Binary Tree

Breadth-First Search

Queue

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

Example:

Input:

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

→

Output:

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

Level 1: left to right, Level 2: right to left, Level 3: left to right

Algorithm:

1. Use BFS with queue for level order traversal
2. Use boolean flag to track direction
3. Use LinkedList for O(1) insertion at either end
4. Toggle direction after each level

Complexity:

Time: O(n) | Space: O(w) where w is max width of tree

Java Solution:

public ListInteger>> zigzagLevelOrder(TreeNode root) {
    ListInteger>> res = new LinkedList<>();
    if (root == null) return res;
    
    // Queue for BFS traversal
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    boolean forward = true;
    
    while (!q.isEmpty()) {
        int n = q.size();
        // Use LinkedList for O(1) insertion at either end
        LinkedList<Integer> level = new LinkedList<>();
        
        // Process current level
        for (int i = 0; i < n; i++) {
            TreeNode curr = q.poll();
            
            // Add children for next level
            if (curr.left != null) q.add(curr.left);
            if (curr.right != null) q.add(curr.right);
            
            // Add current value based on direction
            if (forward)
                level.add(curr.val);
            else
                level.addFirst(curr.val);
        }
        
        res.add(level);
        forward = !forward;  // Toggle direction for next level
    }
    
    return res;
}

Python Solution:

def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
        
    # Queue for BFS traversal
    q = deque([root])
    res = []
    forward = True
    
    while q:
        n = len(q)
        level = deque()
        
        # Process current level
        for _ in range(n):
            curr = q.popleft()
            
            # Add children for next level
            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)
            
            # Add current value based on direction
            if forward:
                level.append(curr.val)
            else:
                level.appendleft(curr.val)
                
        res.append(list(level))
        forward = not forward  # Toggle direction for next level
        
    return res

C++ Solution:

vectorint>> zigzagLevelOrder(TreeNode* root) {
    vectorint>> res;
    if (!root) return res;
    
    // Queue for BFS traversal
    queue<TreeNode*> q;
    q.push(root);
    bool forward = true;
    
    while (!q.empty()) {
        int n = q.size();
        deque<int> level;
        
        // Process current level
        for (int i = 0; i < n; i++) {
            TreeNode* curr = q.front();
            q.pop();
            
            // Add children for next level
            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
            
            // Add current value based on direction
            if (forward)
                level.push_back(curr->val);
            else
                level.push_front(curr->val);
        }
        
        res.push_back(vector<int>(level.begin(), level.end()));
        forward = !forward;  // Toggle direction for next level
    }
    
    return res;
}