Level Order Traversal

L8 Hard Trees

Concept

Breadth-first traversal visits nodes level by level using a queue, which makes collecting per-level groups straightforward.

Given the root of a binary tree, return the values of its nodes ordered by level, with each level as its own array (root first). Return an empty array for an empty tree.

Examples

▸ root = [3, 9, 20, nil, nil, 15, 7]

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

▸ root = [1]

→ [[1]]

▸ root = []

→ []

Progressive Hints

Hint 1 · Nudge

Process the tree one whole row at a time using a queue.

Hint 2 · Plan

Breadth-first search with a queue seeded with the root. Each round, look at how many nodes are currently queued and process exactly that many as one level, appending their children for the next round.

Hint 3 · Approach

If root is nil, return an empty list. Queue starts with root. While the queue is non-empty: fix the level size, pop that many nodes into a level row while pushing their non-nil children, and save the row.

Output

// Run your code to see the output here.