103. Binary Tree Zigzag Level Order Traversal - Explanation

Description

You are 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 = [1,2,3,4,5,6,7]

Output: [[1],[3,2],[4,5,6,7]]

Example 2:

Input: root = [1]

Output: [[1]]

Constraints:

0 <= number of nodes in the tree <= 2000
-100 <= Node.val <= 100

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Breadth First Search

Intuition

Level order traversal naturally suggests using BFS with a queue. The zigzag pattern means we alternate the direction we read each level: left-to-right for even levels, right-to-left for odd levels. We can achieve this by collecting each level normally and then reversing it when needed based on the level index.

Algorithm

Initialize an empty result list and a queue with the root node.
While the queue is not empty:
- Create an empty list to store the current level's values.
- Process all nodes at the current level by iterating through the queue's current size.
- For each node, add its value to the level list and enqueue its children (left then right).
- If the current level index is odd, reverse the level list.
- Add the level list to the result.
Return the result list.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        q = deque([root] if root else [])
        while q:
            level = []
            for i in range(len(q)):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if len(res) % 2:
                level.reverse()
            res.append(level)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Breadth First Search (Optimal)

Intuition

Instead of reversing the list after collecting values, we can place each value directly at its correct position. For even levels, values go from index 0 to size-1. For odd levels, values go from index size-1 to 0. This avoids the extra reversal operation.

Algorithm

Initialize an empty result list and a queue with the root node.
While the queue is not empty:
- Get the current level size and create a fixed-size array for this level.
- For each node in the current level:
  - Calculate the insertion index: for even levels use the iteration index, for odd levels use (size - 1 - iteration index).
  - Place the node's value at the calculated index.
  - Enqueue the node's children.
- Add the level array to the result.
Return the result list.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        q = deque([root] if root else [])
        while q:
            size = len(q)
            level = [0] * size
            for i in range(size):
                node = q.popleft()
                idx = size - i - 1 if len(res) % 2 else i
                level[idx] = node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(level)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Depth First Search

Intuition

DFS can also solve this problem by tracking the depth during traversal. We recursively visit nodes in a standard preorder manner (root, left, right), appending values to the appropriate level's list. After the traversal completes, we reverse the odd-indexed levels to achieve the zigzag pattern.

Algorithm

Create an empty result list.
Define a recursive dfs function that takes a node and its depth:
- If the node is null, return.
- If this is the first node at this depth, create a new list for this level.
- Append the node's value to the list at the current depth.
- Recursively process the left child with depth + 1.
- Recursively process the right child with depth + 1.
Call dfs starting from the root at depth 0.
Reverse all lists at odd indices.
Return the result list.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        def dfs(node, depth):
            if not node:
                return
            if depth == len(res):
                res.append([])
            res[depth].append(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        for i, level in enumerate(res):
            if i & 1:
                level.reverse()

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Iterative DFS

Intuition

This approach converts the recursive DFS to an iterative version using an explicit stack. Each stack entry stores both the node and its depth. We process nodes in the same order as recursive DFS by pushing the right child before the left child (so left is processed first). After collecting all values, we reverse the odd levels.

Algorithm

If the root is null, return an empty list.
Initialize a stack with the root node and depth 0.
While the stack is not empty:
- Pop a node and its depth.
- If this depth is new, create a new list for it.
- Append the node's value to the list at this depth.
- Push the right child (if exists) with depth + 1.
- Push the left child (if exists) with depth + 1.
Reverse all lists at odd indices.
Return the result list.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        res = []
        stack = [(root, 0)]

        while stack:
            node, depth = stack.pop()
            if depth == len(res):
                res.append([])

            res[depth].append(node.val)

            if node.right:
                stack.append((node.right, depth + 1))
            if node.left:
                stack.append((node.left, depth + 1))

        for i in range(len(res)):
            if i % 2 == 1:
                res[i].reverse()

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Reversing Children Order Instead of Values

A common mistake is trying to alternate the order of adding children to the queue (right-then-left vs left-then-right). This does not produce the correct zigzag pattern because it affects future levels, not just the current one.

# Wrong: alternating child insertion order
if level_num % 2 == 0:
    queue.append(node.left); queue.append(node.right)
else:
    queue.append(node.right); queue.append(node.left)  # Breaks level structure

Off-by-One Error in Level Index Check

Confusing whether level 0 should be left-to-right or right-to-left. The problem defines level 0 (root level) as left-to-right, so odd-indexed levels should be reversed.

# Wrong: reversing even levels instead of odd
if len(res) % 2 == 0:  # Should be: if len(res) % 2 == 1
    level.reverse()

Using Deque Operations Incorrectly for Zigzag

Some attempt to use appendleft and append alternately to avoid reversing, but this approach requires careful handling to avoid mixing up the traversal order with the output order, often leading to subtle bugs.