Binary Tree Zigzag Level Order Traversal

Explanation & Solution

Description

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).

Examples

Example 1:

```tree

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

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

null

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

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

Example 2:

```tree

[1]

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

Tree Breadth-First Search pattern

1. Handle Empty Tree

If root is null:
Return []

2. Initialize BFS

Create result = [] to hold all levels
Create queue = [root] with a head pointer for efficient dequeue
Create leftToRight = true to track traversal direction

3. Process Level by Level

While the queue is not empty:
Calculate levelSize = queue.length - head
This captures how many nodes are on the current level

4. Collect Node Values

Loop levelSize times:
Dequeue node via queue[head++]
Push node.val into level array
Enqueue left and right children if they exist
This always collects values left to right

5. Apply Zigzag Direction

If leftToRight is false:
Reverse the level array
This flips alternate levels to read right to left

6. Toggle Direction

After each level, flip leftToRight = !leftToRight
Level 0: left→right, Level 1: right→left, Level 2: left→right, ...

7. Return Result

After all levels, return result

Key Insight

Standard BFS collects nodes left to right at every level
Zigzag is achieved by simply reversing alternate levels after collection
This avoids complex deque logic — just reverse when needed

Time

O(n)visit each node once

Space

O(n)queue and result storage

Visualization

Input:

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

output0

Press play to start DFS traversal

CurrentIn stackComplete

11 steps

Solution Code

Binary Tree Level Order Traversal

Binary Tree Right Side View