Binary Tree Level Order Traversal

Difficulty: Medium

Problem

Given the root of a binary tree, return its nodes' values level by level, as a list of lists: the first inner list holds every value at depth 0, the second holds every value at depth 1, and so on — top to bottom, reading each level left to right. This row-by-row exploration is called BFS (Breadth-First Search), and it is a fundamentally different way to explore a tree than the DFS recursion you've learned so far: instead of diving deep down one branch, we sweep across one full level at a time.

Example

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Explanation: The tree has three levels. Level 0 is just the root: [3]. Level 1 is [9, 20], read left to right. Level 2 is [15, 7] — both children of 20, since 9 has none. Each level becomes its own inner list.

Brute-force approach

There is no meaningful 'brute force vs optimal' split here — BFS with a queue IS the natural solution. Trees skip straight to the optimal approach.

Optimal approach

Key insight: A queue is first-in-first-out, so nodes are served in exactly the order they were discovered — and we discover all of level d before anything at level d+1, so the queue hands us the tree level by level. The len(queue) snapshot at the top of each round marks exactly where one level ends and the next begins.

Explore the tree in waves with a queue: snapshot the queue's size, dequeue exactly that many nodes into the current level's list, and enqueue their children — they form the next wave.

Steps

  1. If the root is null, return an empty list — no tree, no levels
  2. Create an empty result list and a queue seeded with the root
  3. While the queue isn't empty, snapshot levelSize = len(queue)
  4. Dequeue exactly levelSize nodes, appending each value to a fresh level list
  5. As each node is dequeued, enqueue its children at the back — they form the next level
  6. Append the level list to result; when the queue runs dry, return result

Time complexity: O(n) · Space complexity: O(w) where w = maximum width of the tree