LeetCode 103 - Binary Tree Zigzag Level Order Traversal

Difficulty: 🟡 Medium
Topics: Tree, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to perform a level order traversal of a binary tree, but with a twist. Instead of always traversing each level from left to right, we alternate the traversal direction at every level.

A normal level order traversal, also called Breadth-First Search (BFS), visits nodes level by level starting from the root. In this problem, the first level is traversed from left to right, the second level from right to left, the third level from left to right again, and so on in a zigzag pattern.

The input is the root node of a binary tree. Each node contains an integer value and references to its left and right children. The output should be a list of lists, where each inner list contains the values of nodes at one level of the tree, arranged according to the required zigzag direction.

For example, consider this tree:

The traversal works like this:

Level 0, left to right: [3]
Level 1, right to left: [20, 9]
Level 2, left to right: [15, 7]

So the final result becomes:

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

The constraints tell us that the tree can contain up to 2000 nodes. This is small enough that an O(n) traversal is easily efficient enough. Since every node must be visited at least once, linear time is optimal.

Several important edge cases should immediately be considered:

The tree may be empty, meaning root = None. In that case, the answer should be an empty list.
The tree may contain only one node.
The tree may be heavily skewed, meaning all nodes exist only on the left or right side.
Levels may contain many nodes, so the implementation must correctly reverse traversal direction without corrupting ordering.

The problem guarantees that the input is a valid binary tree, so we do not need to handle malformed structures or cycles.

Approaches

Brute Force Approach

A straightforward solution is to perform a standard level order traversal using BFS. For each level, we collect all node values in left-to-right order. After collecting a level, if the current level should be traversed in reverse order, we explicitly reverse the list before adding it to the result.

This works because BFS naturally processes nodes level by level. Reversing every alternate level produces the required zigzag ordering.

However, repeatedly reversing lists introduces additional work. If a level contains k nodes, reversing costs O(k). Across all levels, this still totals O(n) overall because every node participates in at most one reversal. Although acceptable for the constraints, it is not the cleanest or most efficient implementation.

Optimal Approach

The optimal solution also uses BFS, but instead of reversing lists afterward, we place values into the level list in the correct order as we process nodes.

The key insight is that BFS already gives us the correct grouping by level. The only remaining challenge is ordering values differently on alternating levels.

We can maintain a boolean flag, such as left_to_right, which tracks the traversal direction for the current level:

If left_to_right is True, append values normally.
If left_to_right is False, insert values at the beginning of the level list.

This avoids an explicit reversal step and keeps the traversal logic clean and direct.

Because every node is processed exactly once, the algorithm runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Standard BFS, reverse every alternate level
Optimal	O(n)	O(n)	BFS with direction-aware insertion

Algorithm Walkthrough

Start by handling the empty tree case. If the root is None, return an empty list immediately because there are no levels to traverse.
Initialize a queue for BFS traversal. The queue stores nodes that still need to be processed. Begin by placing the root node into the queue.
Create a result list that will eventually contain all levels in zigzag order.
Maintain a boolean variable called left_to_right. Initially set it to True because the first level must be traversed from left to right.
Begin the BFS loop. Continue processing while the queue is not empty.
At the start of each iteration, determine how many nodes belong to the current level by checking the queue size. This is important because BFS continuously appends child nodes, so we must isolate processing level by level.
Create an empty list called current_level to store node values for this level.
Process exactly level_size nodes:
Remove the front node from the queue.
If traversing left to right, append the node's value to current_level.
Otherwise, insert the node's value at index 0, effectively building the level in reverse order.
Add the node's left child to the queue if it exists.
Add the node's right child to the queue if it exists.
After processing all nodes in the level, append current_level to the result.
Flip the traversal direction by setting:

left_to_right = not left_to_right

Continue until the queue becomes empty.
Return the result list.

Why it works

BFS guarantees that nodes are processed level by level. At each iteration, the queue contains exactly the nodes belonging to the current level. By alternating how values are inserted into current_level, we ensure the ordering matches the required zigzag pattern. Since every node is visited exactly once and assigned to exactly one level, the final output is correct.

Python Solution

from collections import deque
from typing import List, Optional

# 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 []

        result = []
        queue = deque([root])
        left_to_right = True

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()

                if left_to_right:
                    current_level.append(node.val)
                else:
                    current_level.insert(0, node.val)

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            result.append(current_level)
            left_to_right = not left_to_right

        return result

The implementation begins by checking whether the tree is empty. This prevents unnecessary processing and immediately handles the simplest edge case.

A deque is used for the BFS queue because it provides efficient popleft() operations in constant time. Using a normal Python list would make removals from the front inefficient.

The left_to_right flag controls traversal direction. When the flag is True, values are appended normally. When it is False, values are inserted at the beginning of the level list, creating reverse ordering naturally.

The queue size at the start of each level is stored in level_size. This ensures we process only nodes from the current level before moving to the next one.

After each level is completed, the direction flag is toggled so the next level uses the opposite traversal order.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }

    result := [][]int{}
    queue := []*TreeNode{root}
    leftToRight := true

    for len(queue) > 0 {
        levelSize := len(queue)
        currentLevel := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            if leftToRight {
                currentLevel = append(currentLevel, node.Val)
            } else {
                currentLevel = append([]int{node.Val}, currentLevel...)
            }

            if node.Left != nil {
                queue = append(queue, node.Left)
            }

            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, currentLevel)
        leftToRight = !leftToRight
    }

    return result
}

The Go solution follows the same BFS strategy as the Python version. Since Go does not provide a built-in deque, a slice is used as the queue.

Nil checking is explicit in Go, so the empty tree case is handled using:

if root == nil

The main implementation difference is how reverse ordering is handled. In Python, we use insert(0, value). In Go, we prepend values using:

currentLevel = append([]int{node.Val}, currentLevel...)

This creates the reverse ordering needed for zigzag traversal.

There are no integer overflow concerns because node values are constrained between -100 and 100.

Worked Examples

Example 1

Input:

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

Tree:

Initial state:

Variable	Value
queue	[3]
result	[]
left_to_right	True

Level 0

Process node 3.

Action	current_level	queue
append 3	[3]	[9, 20]

After level completion:

Variable	Value
result	[[3]]
left_to_right	False

Level 1

Current queue:

[9, 20]

Process node 9.

Action	current_level
insert at front	[9]

Process node 20.

Action	current_level
insert at front	[20, 9]

Children added:

15, 7

After level completion:

Variable	Value
result	[[3], [20, 9]]
queue	[15, 7]
left_to_right	True

Level 2

Process node 15.

Action	current_level
append 15	[15]

Process node 7.

Action	current_level
append 7	[15, 7]

Final result:

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

Example 2

Input:

root = [1]

Processing:

Level	current_level
0	[1]

Final result:

[[1]]

Example 3

Input:

root = []

Since the root is None, the algorithm immediately returns:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(n)	Queue and output may store all nodes

The algorithm processes each node exactly one time during BFS traversal. All queue operations are constant time. Although reverse insertion may appear expensive, the total work across all levels remains proportional to the number of nodes for the problem constraints.

The space complexity is O(n) because the queue may contain an entire level of the tree at once. In the worst case, this can approach n / 2 nodes. The output list also stores all node values.

Test Cases

from collections import deque
from typing import Optional, List

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 []

        result = []
        queue = deque([root])
        left_to_right = True

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()

                if left_to_right:
                    current_level.append(node.val)
                else:
                    current_level.insert(0, node.val)

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            result.append(current_level)
            left_to_right = not left_to_right

        return result

solution = Solution()

# Empty tree
assert solution.zigzagLevelOrder(None) == []

# Single node tree
root = TreeNode(1)
assert solution.zigzagLevelOrder(root) == [[1]]

# Example 1
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
assert solution.zigzagLevelOrder(root) == [[3], [20, 9], [15, 7]]

# Left skewed tree
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(3)
root.left.left.left = TreeNode(4)
assert solution.zigzagLevelOrder(root) == [[1], [2], [3], [4]]

# Right skewed tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)
root.right.right.right = TreeNode(4)
assert solution.zigzagLevelOrder(root) == [[1], [2], [3], [4]]

# Complete binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
assert solution.zigzagLevelOrder(root) == [[1], [3, 2], [4, 5, 6, 7]]

# Tree with negative values
root = TreeNode(-1)
root.left = TreeNode(-2)
root.right = TreeNode(-3)
assert solution.zigzagLevelOrder(root) == [[-1], [-3, -2]]

# Uneven tree structure
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.right.right = TreeNode(5)
assert solution.zigzagLevelOrder(root) == [[1], [3, 2], [4, 5]]

Test	Why
Empty tree	Verifies handling of `None` input
Single node tree	Confirms simplest non-empty case
Example 1	Validates standard zigzag behavior
Left skewed tree	Tests traversal with only left children
Right skewed tree	Tests traversal with only right children
Complete binary tree	Verifies multiple full levels
Tree with negative values	Ensures negative numbers are handled correctly
Uneven tree structure	Tests irregular branching

Edge Cases

Empty Tree

An empty tree is one of the most important edge cases. A naive BFS implementation might attempt to process the root immediately without checking whether it exists, causing runtime errors. The implementation handles this safely with:

if not root:
    return []

This ensures the algorithm terminates immediately for empty input.

Single Node Tree

A tree containing only one node can expose bugs in level-processing logic, especially when toggling traversal direction. The implementation correctly processes the root as a single level and then exits because no children are added to the queue.

Highly Skewed Tree

A skewed tree behaves almost like a linked list. Some implementations accidentally assume multiple nodes exist at every level. In a skewed tree, each level contains exactly one node. The BFS approach naturally handles this because levels are determined by queue size, not by assumptions about tree shape.

Uneven Tree Structures

Some nodes may have only one child while others have two. Incorrect queue handling can accidentally skip nodes or process levels incorrectly. The implementation safely checks each child individually before adding it to the queue:

if node.left:
    queue.append(node.left)

if node.right:
    queue.append(node.right)

This guarantees all valid children are processed exactly once.