Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Binary Tree Zigzag Level Order Traversal

MEDIUMProblemSolveExternal Links

Description

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values.

In a zigzag traversal, nodes at the first level are read from left to right, nodes at the second level from right to left, nodes at the third level from left to right again, and so on — the reading direction alternates at every level.

Return the result as a list of lists, where each inner list contains the node values at that level in the zigzag-specified order.

Examples

Example 1

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

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

Explanation: The tree looks like this:

       3
      / \
     9   20
        /  \
       15    7
  • Level 0 (left → right): [3]
  • Level 1 (right → left): [20, 9] — we read 20 before 9
  • Level 2 (left → right): [15, 7]

The direction alternates at each level, producing the zigzag pattern.

Example 2

Input: root = [1]

Output: [[1]]

Explanation: A single-node tree has only level 0, which reads left to right: [1]. No alternation is needed since there is only one level.

Example 3

Input: root = []

Output: []

Explanation: An empty tree has no nodes, so the result is an empty list. This is an important edge case to handle.

Constraints

  • The number of nodes in the tree is in the range [0, 2000]
  • -100 ≤ Node.val ≤ 100

Editorial

Brute Force

Intuition

The most straightforward way to think about zigzag traversal is level by level: for each level of the tree, collect all nodes at that depth, in the appropriate direction.

Imagine you are standing at the top of a building with numbered floors. To inspect each floor, you take the elevator from the ground floor up to that floor, look around, then go back down and repeat for the next floor. It works, but you ride the elevator through every floor each time — even floors you have already seen.

The algorithm works the same way:

  1. First, compute the height of the tree (the number of levels).
  2. For each level, perform a DFS from the root to reach that specific depth.
  3. For even-numbered levels (0, 2, 4, ...), visit left child before right child to collect nodes left-to-right.
  4. For odd-numbered levels (1, 3, 5, ...), visit right child before left child to collect nodes right-to-left.

Each level requires a fresh DFS traversal from the root, which is why this approach is slow for tall trees.

Step-by-Step Explanation

Let's trace through with root = [3, 9, 20, null, null, 15, 7]:

Step 1: Compute tree height. DFS finds the longest path: 3 → 20 → 15 (or 3 → 20 → 7), depth = 3. So we have levels 0, 1, and 2.

Step 2: Level 0, direction = left-to-right. DFS from root, target depth = 0. Root node 3 is at depth 0 — collect it. level_0 = [3]. result = [[3]].

Step 3: Level 1, direction = right-to-left. DFS from root again, target depth = 1, but this time visit right child before left child. At depth 1: visit 20 (right child of 3) first, then 9 (left child of 3). level_1 = [20, 9]. result = [[3], [20, 9]].

Step 4: Level 2, direction = left-to-right. DFS from root once more, target depth = 2, visiting left before right. Node 9 has no children — nothing at depth 2 from the left subtree. In the right subtree of 3: reach 15 (left child of 20) first, then 7 (right child of 20). level_2 = [15, 7]. result = [[3], [20, 9], [15, 7]].

Step 5: All levels processed. Return [[3], [20, 9], [15, 7]].

Brute Force — DFS Per Level with Alternating Direction — Watch how the brute force re-traverses the tree from root for each level, collecting nodes in the appropriate zigzag direction.

Algorithm

  1. Compute the height h of the tree using DFS
  2. For each level from 0 to h-1:
    • If level is even: DFS from root, visiting left child before right, collecting nodes at target depth → left-to-right order
    • If level is odd: DFS from root, visiting right child before left, collecting nodes at target depth → right-to-left order
    • Append the collected level to the result
  3. Return the result list

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int h = getHeight(root);
        
        for (int level = 0; level < h; level++) {
            vector<int> levelNodes;
            if (level % 2 == 0) {
                collectLR(root, level, 0, levelNodes);
            } else {
                collectRL(root, level, 0, levelNodes);
            }
            result.push_back(levelNodes);
        }
        return result;
    }

private:
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        return 1 + max(getHeight(node->left), getHeight(node->right));
    }
    
    void collectLR(TreeNode* node, int target, int depth, vector<int>& res) {
        if (!node) return;
        if (depth == target) { res.push_back(node->val); return; }
        collectLR(node->left, target, depth + 1, res);
        collectLR(node->right, target, depth + 1, res);
    }
    
    void collectRL(TreeNode* node, int target, int depth, vector<int>& res) {
        if (!node) return;
        if (depth == target) { res.push_back(node->val); return; }
        collectRL(node->right, target, depth + 1, res);
        collectRL(node->left, target, depth + 1, res);
    }
};
from typing import Optional, List

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        h = self._get_height(root)
        
        for level in range(h):
            level_nodes = []
            if level % 2 == 0:
                self._collect_lr(root, level, 0, level_nodes)
            else:
                self._collect_rl(root, level, 0, level_nodes)
            result.append(level_nodes)
        
        return result
    
    def _get_height(self, node):
        if not node:
            return 0
        return 1 + max(self._get_height(node.left), self._get_height(node.right))
    
    def _collect_lr(self, node, target, depth, res):
        if not node:
            return
        if depth == target:
            res.append(node.val)
            return
        self._collect_lr(node.left, target, depth + 1, res)
        self._collect_lr(node.right, target, depth + 1, res)
    
    def _collect_rl(self, node, target, depth, res):
        if not node:
            return
        if depth == target:
            res.append(node.val)
            return
        self._collect_rl(node.right, target, depth + 1, res)
        self._collect_rl(node.left, target, depth + 1, res)
import java.util.*;

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        int h = getHeight(root);
        
        for (int level = 0; level < h; level++) {
            List<Integer> levelNodes = new ArrayList<>();
            if (level % 2 == 0) {
                collectLR(root, level, 0, levelNodes);
            } else {
                collectRL(root, level, 0, levelNodes);
            }
            result.add(levelNodes);
        }
        return result;
    }
    
    private int getHeight(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }
    
    private void collectLR(TreeNode node, int target, int depth, List<Integer> res) {
        if (node == null) return;
        if (depth == target) { res.add(node.val); return; }
        collectLR(node.left, target, depth + 1, res);
        collectLR(node.right, target, depth + 1, res);
    }
    
    private void collectRL(TreeNode node, int target, int depth, List<Integer> res) {
        if (node == null) return;
        if (depth == target) { res.add(node.val); return; }
        collectRL(node.right, target, depth + 1, res);
        collectRL(node.left, target, depth + 1, res);
    }
}

Complexity Analysis

Time Complexity: O(n × h) where n is the number of nodes and h is the height of the tree

For each of the h levels, we perform a DFS that visits up to n nodes to reach the target depth. In a balanced tree h = O(log n), giving O(n log n). In the worst case (a skewed tree where every node has only one child), h = O(n), giving O(n²).

Space Complexity: O(h)

The recursion stack depth equals the height of the tree. In a balanced tree this is O(log n); in a skewed tree it is O(n). We do not use any auxiliary data structures that grow with input size.

Why This Approach Is Not Efficient

The brute force re-traverses the tree from the root for every single level. Node 3 (the root) is visited once per level — that is h times total. Nodes at depth 1 are visited h-1 times each. Only the deepest nodes are visited once. This means the total work is proportional to n × h.

For a balanced tree with 2000 nodes (h ≈ 11), the total node visits are roughly 2000 × 11 = 22,000 — manageable. But for a skewed tree with 2000 nodes (h = 2000), the total is 2000 × 2000 = 4,000,000 — significantly wasteful.

The fundamental flaw is that BFS naturally visits each node exactly once while discovering its level. We are fighting against this by using DFS, which has no concept of "levels" and must start from scratch each time. The fix is to use BFS (Breadth-First Search) with a queue: process the tree level by level, visiting each node exactly once.

Better Approach - BFS with Level Reversal

Intuition

BFS (Breadth-First Search) processes a tree level by level using a queue. This is exactly what we need — but BFS always processes nodes in the order they were enqueued, which is always left-to-right.

Think of a line of people at a ticket counter. They always arrive in order: people on the left side of the room arrive first. If you want to read their names from right to left for some reason, you write all names down in arrival order and then flip the list.

That is exactly what this approach does:

  1. Use a standard BFS queue to process the tree level by level.
  2. For each level, collect all node values into a list (always left-to-right since that is how BFS works).
  3. For levels that require right-to-left order, reverse the list after collection.
  4. Append the (possibly reversed) list to the result.

This visits each node exactly once — a huge improvement over the brute force — but the reversal step does extra work on alternate levels.

Step-by-Step Explanation

Let's trace through with root = [3, 9, 20, null, null, 15, 7]:

Step 1: Initialize: push root (3) into queue. queue = [3], leftToRight = true, result = [].

Step 2: Level 0. Queue size = 1. Dequeue 3. level_nodes = [3]. Enqueue children: 9, 20. queue = [9, 20].

Step 3: leftToRight = true → no reversal needed. result = [[3]]. Toggle: leftToRight = false.

Step 4: Level 1. Queue size = 2. Dequeue 9. level_nodes = [9]. Node 9 has no children — nothing to enqueue.

Step 5: Dequeue 20. level_nodes = [9, 20]. Enqueue children of 20: 15, 7. queue = [15, 7].

Step 6: leftToRight = false → REVERSE [9, 20] to [20, 9]. result = [[3], [20, 9]]. Toggle: leftToRight = true.

Step 7: Level 2. Queue size = 2. Dequeue 15. level_nodes = [15]. No children.

Step 8: Dequeue 7. level_nodes = [15, 7]. No children. Queue is now empty.

Step 9: leftToRight = true → no reversal. result = [[3], [20, 9], [15, 7]]. All levels done.

BFS Level-by-Level with Reversal on Alternate Levels — Watch how BFS processes each level left-to-right using a queue, then reverses alternate levels to achieve the zigzag order.

Algorithm

  1. If root is null, return an empty list
  2. Initialize a queue with the root node and set leftToRight = true
  3. While the queue is not empty:
    • Record size = current queue size (number of nodes at this level)
    • Create an empty level list
    • For i from 0 to size-1: dequeue a node, add its value to level, enqueue its children
    • If leftToRight is false, reverse level
    • Append level to result
    • Toggle leftToRight
  4. Return result

Code

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        
        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;
        
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            if (!leftToRight) {
                reverse(level.begin(), level.end());
            }
            result.push_back(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
};
from collections import deque
from typing import Optional, List

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        if not root:
            return result
        
        queue = deque([root])
        left_to_right = True
        
        while queue:
            size = len(queue)
            level = []
            
            for _ in range(size):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            if not left_to_right:
                level.reverse()
            
            result.append(level)
            left_to_right = not left_to_right
        
        return result
import java.util.*;

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 size = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            if (!leftToRight) {
                Collections.reverse(level);
            }
            result.add(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each node is enqueued and dequeued exactly once, contributing O(1) work per node. The total BFS traversal is O(n). The reversal of alternate levels also totals O(n) across all levels (since the sum of all level widths equals n). Overall: O(n) + O(n) = O(n).

Space Complexity: O(n)

The queue holds at most one level of nodes at a time. In a complete binary tree, the widest level has roughly n/2 nodes, so the queue uses O(n) space. The result list also stores all n node values.

Why This Approach Is Not Efficient

The BFS approach is already O(n) — a massive improvement over the O(n × h) brute force. However, it performs an unnecessary reversal step on every alternate level.

For a level with w nodes, reversing the list costs O(w) time and involves copying or swapping w/2 pairs. Across all levels, the total reversal cost sums to O(n) since all level widths add up to n. For a complete binary tree with 2000 nodes, the widest level has about 1000 nodes — reversing a 1000-element list each time is avoidable work.

The root cause is that BFS always dequeues left-to-right. We then "fix" the order with a post-hoc reversal. A smarter approach asks: can we place each node at its correct final position during BFS itself, so no reversal is ever needed? The answer is yes — by using an index-based placement strategy.

Optimal Approach - BFS with Direct Index Placement

Intuition

Instead of collecting all nodes left-to-right and then reversing, we pre-allocate the level array and place each dequeued node directly at its correct final index.

Imagine you are a teacher assigning seats in alternating rows. In odd rows, students sit left to right (seat 0, 1, 2, ...). In even rows, they sit right to left (seat n-1, n-2, ...). Instead of letting students sit however they arrive and then making everyone switch, you simply tell each student exactly which seat to go to as they enter.

The formula is simple:

  • If leftToRight: the i-th dequeued node goes to index i
  • If rightToLeft: the i-th dequeued node goes to index size - 1 - i

This places every node at its correct position in O(1), eliminating all reversal work. The BFS structure is identical — we just change where each value is written.

Step-by-Step Explanation

Let's trace through with root = [3, 9, 20, null, null, 15, 7]:

Step 1: Initialize: push root (3) into queue. queue = [3], leftToRight = true, result = [].

Step 2: Level 0. size = 1. Pre-allocate level = [_] (one slot). leftToRight = true. Dequeue 3 → index = 0. Place: level[0] = 3. level = [3]. Enqueue 9, 20.

Step 3: Finalize level 0: result = [[3]]. Toggle: leftToRight = false.

Step 4: Level 1. size = 2. Pre-allocate level = [_, _] (two slots). leftToRight = false. Dequeue 9 → i=0, index = 2-1-0 = 1. Place: level[1] = 9.

Step 5: Dequeue 20 → i=1, index = 2-1-1 = 0. Place: level[0] = 20. level = [20, 9]. Enqueue 15, 7. The right-to-left order appeared naturally — no reversal needed!

Step 6: Finalize level 1: result = [[3], [20, 9]]. Toggle: leftToRight = true.

Step 7: Level 2. size = 2. Pre-allocate level = [_, _]. leftToRight = true. Dequeue 15 → i=0, index = 0. Place: level[0] = 15.

Step 8: Dequeue 7 → i=1, index = 1. Place: level[1] = 7. level = [15, 7].

Step 9: Finalize level 2: result = [[3], [20, 9], [15, 7]]. Queue empty. Done.

BFS with Direct Index Placement — Zero Reversals — Watch how each dequeued node is placed directly at its correct index using the formula: leftToRight ? i : size-1-i, eliminating all reversal steps.

Algorithm

  1. If root is null, return an empty list
  2. Initialize a queue with the root node and set leftToRight = true
  3. While the queue is not empty:
    • Record size = current queue size
    • Pre-allocate a level array of length size
    • For i from 0 to size-1:
      • Dequeue a node
      • Compute index = leftToRight ? i : size - 1 - i
      • Set level[index] = node.val
      • Enqueue the node's children (left then right)
    • Append level to result
    • Toggle leftToRight
  4. Return result

Code

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        
        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;
        
        while (!q.empty()) {
            int size = q.size();
            vector<int> level(size);
            
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                int index = leftToRight ? i : size - 1 - i;
                level[index] = node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            result.push_back(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
};
from collections import deque
from typing import Optional, List

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        if not root:
            return result
        
        queue = deque([root])
        left_to_right = True
        
        while queue:
            size = len(queue)
            level = [0] * size
            
            for i in range(size):
                node = queue.popleft()
                index = i if left_to_right else size - 1 - i
                level[index] = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(level)
            left_to_right = not left_to_right
        
        return result
import java.util.*;

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 size = queue.size();
            Integer[] level = new Integer[size];
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                int index = leftToRight ? i : size - 1 - i;
                level[index] = node.val;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            result.add(Arrays.asList(level));
            leftToRight = !leftToRight;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each of the n nodes is enqueued once, dequeued once, and placed at its computed index in O(1). The index computation leftToRight ? i : size - 1 - i is a constant-time arithmetic operation. No reversal step means no extra passes over the data. Total: O(n).

Space Complexity: O(n)

The queue stores at most one level of nodes at a time — up to n/2 in a complete binary tree. The result list stores all n values. The pre-allocated level array is reused per level and is at most n/2 in size. Total auxiliary space: O(n).