Binary Tree Zigzag Level Order Traversal

Description

Binary Tree Zigzag Level Order Traversal

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

Approach 1: BFS Level-Order Traversal ($O(N)$ Time, $O(N)$ Space)

Intuition

Traverse the tree level by level using the standard BFS queue template. Keep track of direction using a boolean flag leftToRight initialized to true:

1. Add root to the queue before entering the loop.
2. For each level, determine levelSize = queue.size() and create a LinkedList<Integer> to hold level values.
3. As nodes are polled from the queue:
   • If leftToRight is true, append to the tail using addLast().
   • If leftToRight is false, insert at the head using addFirst().
4. Push non-null children (left, then right) into the queue for the next level.
5. Invert leftToRight = !leftToRight at the end of each level.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
 
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
 
        Deque<TreeNode> queue = new ArrayDeque<>();
        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 curr = queue.poll();
 
                if (leftToRight) {
                    currentLevel.addLast(curr.val);
                } else {
                    currentLevel.addFirst(curr.val);
                }
 
                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
 
            result.add(currentLevel);
            leftToRight = !leftToRight; // Flip traversal direction
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each node is offered and polled from the queue once, with $O(1)$ operations on LinkedList.
• Space Complexity: $O(N)$ — Space required to store the queue (bounded by the widest level, up to $N/2$ nodes).

---

Approach 2: Recursive DFS ($O(N)$ Time, $O(H)$ Space)

Intuition

Pass the current level down the recursion stack:

1. Base case: If node == null, return.
2. If level == result.size(), instantiate a new LinkedList for this level.
3. Check level % 2:
   • Even Level (0, 2, …): Left-to-right order $\to$ use add() to append to the end.
   • Odd Level (1, 3, …): Right-to-left order $\to$ use addFirst() to insert at the front.
4. Recurse on node.left and node.right with level + 1.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
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;
 
        if (level == result.size()) {
            result.add(new LinkedList<>());
        }
 
        // Even levels append to end, odd levels prepend to front
        if (level % 2 == 0) {
            result.get(level).add(node.val);
        } else {
            ((LinkedList<Integer>) result.get(level)).addFirst(node.val);
        }
 
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Visits every node in the binary tree exactly once.
• Space Complexity: $O(H)$ — Bounded by the call stack height $H$ ($O(\log N)$ for a balanced tree, $O(N)$ for a skewed tree).

---

Easy Memory Rule

“Standard Level-Order BFS $\to$ Use addLast() for even levels and addFirst() for odd levels!”