Binary Tree Level Order Traversal

Explanation & Solution

Description

Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).

Examples

Example 1:

```tree

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

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

null

Output: [[3], [9, 20], [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]
-1000 <= Node.val <= 1000

Approach

Tree Breadth-First Search pattern

1. Handle Empty Tree

If root is null:
Return []
Reason:
No nodes means no levels to traverse

2. Initialize BFS

Create result = [] to hold all levels
Create queue = [root] to process nodes level by level
Create head = 0 as a pointer for efficient dequeue

3. Process Level by Level

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

4. Process Each Node in the Level

Loop levelSize times:
Dequeue node via queue[head++]
Push node.val into the current level array
If node.left exists, enqueue it
If node.right exists, enqueue it

5. Collect the Level

After processing all nodes in a level:
Push the level array into result

6. Return Result

After all levels are processed, return result
Each sub-array contains values from left to right for that level

Key Insight

BFS naturally processes nodes level by level
The trick is snapshotting levelSize before adding children
Using a head pointer avoids costly shift() operations — O(1) dequeue

Time

O(n)visit each node once

Space

O(n)queue holds at most one level of nodes

Visualization

Input:

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

output0

Press play to start DFS traversal

CurrentIn stackComplete

11 steps

Solution Code

Binary Tree Zigzag Level Order Traversal