Binary TreesProblem 13 of 35

Zig-Zag traversal of a binary tree

Brute Force
Time: O(n)
Space: O(n)
Optimal
Time: O(n)
Space: O(n)

Problem Statement

Given 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 / \ 2 3 / \ \ 4 5 6
  • Input: Root of the above tree
  • Output: [[1], [3, 2], [4, 5, 6]]
  • Level 0: left to right → [1]
  • Level 1: right to left → [3, 2]
  • Level 2: left to right → [4, 5, 6]

Approach 1: BFS with Reversal

Intuition

Perform standard level order traversal, but reverse alternate levels.

Algorithm

  1. Use BFS to traverse level by level
  2. Track whether current level should be reversed
  3. Reverse the level list if needed before adding to result
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public 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();
            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 if right to left
            if (!leftToRight) {
                Collections.reverse(currentLevel);
            }
            
            result.add(currentLevel);
            leftToRight = !leftToRight;
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Each node visited once, reversal is O(k) per level
  • Space Complexity: O(n) - Queue holds up to n/2 nodes

Approach 2: Optimal (Using Deque - No Reversal)

Intuition

Instead of reversing, use a deque to add elements at the front or back based on direction. This avoids the O(k) reversal cost.

Algorithm

  1. Use a deque for the current level
  2. If left to right: add at back
  3. If right to left: add at front
  4. No reversal needed
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<List<Integer>> zigzagLevelOrderOptimal(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 based on direction
                if (leftToRight) {
                    currentLevel.addLast(node.val);
                } else {
                    currentLevel.addFirst(node.val);
                }
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            result.add(currentLevel);
            leftToRight = !leftToRight;
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Each node visited once, O(1) deque operations
  • Space Complexity: O(n) - Queue holds up to n/2 nodes

Approach 3: Using Two Stacks

Intuition

Use two stacks to naturally reverse the order. Alternate between stacks for each level.

Algorithm

  1. Use two stacks: currentStack and nextStack
  2. For odd levels: push right then left to nextStack
  3. For even levels: push left then right to nextStack
  4. Swap stacks after each level
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<List<Integer>> zigzagTwoStacks(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Stack<TreeNode> currentStack = new Stack<>();
        Stack<TreeNode> nextStack = new Stack<>();
        currentStack.push(root);
        boolean leftToRight = true;
        
        List<Integer> currentLevel = new ArrayList<>();
        
        while (!currentStack.isEmpty()) {
            TreeNode node = currentStack.pop();
            currentLevel.add(node.val);
            
            if (leftToRight) {
                if (node.left != null) nextStack.push(node.left);
                if (node.right != null) nextStack.push(node.right);
            } else {
                if (node.right != null) nextStack.push(node.right);
                if (node.left != null) nextStack.push(node.left);
            }
            
            // End of current level
            if (currentStack.isEmpty()) {
                result.add(new ArrayList<>(currentLevel));
                currentLevel.clear();
                Stack<TreeNode> temp = currentStack;
                currentStack = nextStack;
                nextStack = temp;
                leftToRight = !leftToRight;
            }
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Each node visited once
  • Space Complexity: O(n) - Two stacks hold all nodes

Key Takeaways

  1. Zigzag = alternate direction at each level
  2. Three approaches: Reverse after BFS, use deque (no reversal), use two stacks
  3. Deque approach is most efficient - O(1) insertions at both ends
  4. Two stack approach is elegant but uses more space
  5. This is LeetCode #103 - Binary Tree Zigzag Level Order Traversal
  6. Pattern: Any level order variant can be solved with BFS + modifications
Previous
Bottom View of a tree
Next
Check if a tree is balanced or not