Binary Tree Zigzag Level Order Traversal

LeetCode 103: Binary Tree Zigzag Level Order Traversal Solution & Explanation

Problem Overview

TL;DR: Use a Breadth-First Search (BFS) to traverse the tree level by level, reversing the collected node values for every alternate level to achieve the zigzag effect.

The Binary Tree Zigzag Level Order Traversal problem asks us to traverse a binary tree and return its values grouped by level. However, unlike a standard level-order traversal, the direction of traversal alternates. The first level is traversed left-to-right, the second right-to-left, the third left-to-right, and so on. This creates a "zigzag" or serpentine pattern across the tree's depth.

This is a popular interview question because it tests your ability to modify a standard algorithm (BFS) to handle specific state changes (direction) without corrupting the underlying traversal logic.

Brute Force Approach for Binary Tree Zigzag Level Order Traversal

A naive or brute force approach to solve LeetCode 103 might involve repeated traversals or an unstructured Depth-First Search (DFS).

One inefficient method is Iterative Deepening. In this approach, we determine the height of the tree first. Then, for every level $L$ from 0 to Height, we perform a fresh traversal from the root to find all nodes specifically at level $L$. Depending on whether $L$ is even or odd, we would collect these nodes in the specific order required.

Pseudo-code

function bruteForceZigzag(root):
    height = getTreeHeight(root)
    result = []
    for level from 0 to height:
        current_level_nodes = []
        dfs_collect(root, level, current_level_nodes)
        if level is odd:
            reverse(current_level_nodes)
        result.add(current_level_nodes)
    return result

Complexity Analysis

• Time Complexity: $O(N^2)$ in the worst case (skewed tree). For a balanced tree, visiting nodes repeatedly for each level results in strictly worse performance than a single-pass scan.
• Space Complexity: $O(N)$ for the recursion stack and output storage.

Why it fails

While this logic produces the correct output, it performs redundant work by traversing the upper nodes repeatedly to reach lower levels. In a large tree (up to 2000 nodes), this is inefficient compared to a single-pass $O(N)$ solution.

Algorithm Strategy: Tree BFS - Level Order Traversal

1. Initialization: Handle the edge case where root is null by returning an empty list. Initialize a Queue with the root node. Initialize a boolean flag leftToRight to true.
2. Level Loop: While the queue is not empty, start a new level.
   • Determine the number of nodes in the current level (size = queue.size()).
   • Create a data structure (list or deque) to hold the values for this level.
3. Node Processing: Iterate size times:
   • Dequeue a node.
   • If leftToRight is true, add the node's value to the end of the current level's list.
   • If leftToRight is false, add the node's value to the beginning of the current level's list (or append and reverse later).
   • Crucial Step: Always enqueue the current node's left child, then its right child. This maintains the BFS invariant.
4. State Update: After processing all nodes in the current level, add the level's list to the main result list. Toggle the leftToRight boolean.
5. Termination: Return the result list when the queue is empty.

Execution Flow

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

1. Start: Queue = [3], leftToRight = true, Result = [].
2. Level 0:
   • Size is 1. Pop 3.
   • leftToRight is true. Level list: [3].
   • Add children 9, 20 to Queue. Queue = [9, 20].
   • Add [3] to Result. Toggle leftToRight -> false.
3. Level 1:
   • Size is 2.
   • Pop 9. leftToRight is false. Level list: [9]. Add children (none).
   • Pop 20. leftToRight is false. Prepend 20. Level list: [20, 9]. Add children 15, 7. Queue = [15, 7].
   • Add [20, 9] to Result. Toggle leftToRight -> true.
4. Level 2:
   • Size is 2.
   • Pop 15. leftToRight is true. Level list: [15]. Add children (none).
   • Pop 7. leftToRight is true. Append 7. Level list: [15, 7]. Add children (none).
   • Add [15, 7] to Result. Toggle leftToRight -> false.
5. End: Queue empty. Return [[3], [20, 9], [15, 7]].

Proof of Correctness

The algorithm is correct because it maintains the structural integrity of the BFS traversal. By always enqueuing children Left-to-Right, we guarantee that the queue contains nodes for level $L+1$ in their correct geometric order (Left-to-Right) after processing level $L$. The zigzag effect is purely a presentation transformation applied to the values of the current level, which does not affect the order in which future nodes are visited. Thus, every node is visited exactly once, and levels are grouped correctly.

Pattern Reuse Notes

The Tree BFS - Level Order Traversal pattern used in this LeetCode 103 Solution is fundamental for many tree problems.

• LeetCode 102: Binary Tree Level Order Traversal: The base case of this pattern without the zigzag reversal.
• LeetCode 199: Binary Tree Right Side View: Uses the same BFS traversal but only captures the last element of each level.
• LeetCode 515: Find Largest Value in Each Tree Row: Instead of collecting all nodes, we track the maximum value seen in the current level loop.
• LeetCode 1161: Maximum Level Sum of a Binary Tree: Computes the sum of values at each level during the BFS pass to find the maximal level.

Reference Implementation

C++ Solution for LeetCode 103

1#include <vector>
2#include <queue>
3#include <algorithm>
4
5using namespace std;
6
7struct TreeNode {
8    int val;
9    TreeNode *left;
10    TreeNode *right;
11    TreeNode() : val(0), left(nullptr), right(nullptr) {}
12    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14};
15
16class Solution {
17public:
18    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
19        vector<vector<int>> result;
20        if (!root) return result;
21        
22        queue<TreeNode*> q;
23        q.push(root);
24        bool leftToRight = true;
25        
26        while (!q.empty()) {
27            int levelSize = q.size();
28            vector<int> currentLevel(levelSize);
29            
30            for (int i = 0; i < levelSize; ++i) {
31                TreeNode* node = q.front();
32                q.pop();
33                
34                // Determine position based on direction
35                int index = leftToRight ? i : (levelSize - 1 - i);
36                currentLevel[index] = node->val;
37                
38                if (node->left) q.push(node->left);
39                if (node->right) q.push(node->right);
40            }
41            
42            result.push_back(currentLevel);
43            leftToRight = !leftToRight;
44        }
45        
46        return result;
47    }
48};

Java Solution for LeetCode 103

1import java.util.*;
2
3/**
4 * Definition for a binary tree node.
5 * public class TreeNode {
6 *     int val;
7 *     TreeNode left;
8 *     TreeNode right;
9 *     TreeNode() {}
10 *     TreeNode(int val) { this.val = val; }
11 *     TreeNode(int val, TreeNode left, TreeNode right) {
12 *         this.val = val;
13 *         this.left = left;
14 *         this.right = right;
15 *     }
16 * }
17 */
18class Solution {
19    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
20        List<List<Integer>> result = new ArrayList<>();
21        if (root == null) return result;
22        
23        Queue<TreeNode> queue = new LinkedList<>();
24        queue.offer(root);
25        boolean leftToRight = true;
26        
27        while (!queue.isEmpty()) {
28            int levelSize = queue.size();
29            // Use LinkedList for efficient addFirst/addLast if desired, 
30            // or ArrayList and reverse.
31            List<Integer> currentLevel = new ArrayList<>(levelSize);
32            
33            for (int i = 0; i < levelSize; i++) {
34                TreeNode node = queue.poll();
35                
36                // Always add children left to right to maintain BFS order
37                if (node.left != null) queue.offer(node.left);
38                if (node.right != null) queue.offer(node.right);
39                
40                if (leftToRight) {
41                    currentLevel.add(node.val);
42                } else {
43                    currentLevel.add(0, node.val); // Or collect and reverse later
44                }
45            }
46            
47            result.add(currentLevel);
48            leftToRight = !leftToRight;
49        }
50        
51        return result;
52    }
53}

Python Solution for LeetCode 103

1from collections import deque
2from typing import List, Optional
3
4# Definition for a binary tree node.
5# class TreeNode:
6#     def __init__(self, val=0, left=None, right=None):
7#         self.val = val
8#         self.left = left
9#         self.right = right
10
11class Solution:
12    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
13        if not root:
14            return []
15        
16        result = []
17        queue = deque([root])
18        left_to_right = True
19        
20        while queue:
21            level_size = len(queue)
22            current_level = deque() # Using deque for efficient append/appendleft
23            
24            for _ in range(level_size):
25                node = queue.popleft()
26                
27                if left_to_right:
28                    current_level.append(node.val)
29                else:
30                    current_level.appendleft(node.val)
31                
32                if node.left:
33                    queue.append(node.left)
34                if node.right:
35                    queue.append(node.right)
36            
37            result.append(list(current_level))
38            left_to_right = not left_to_right
39            
40        return result