4.14.8 — Binary Tree Level Order Traversal

LeetCode 102 · Medium · ★ Blind 75

The problem

Return the node values level by level, top to bottom, left to right within each level.

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

To put this in plain English: you need to slice the tree horizontally. For each horizontal slice (level), give me a list of the numbers from left to right. Then give me a list containing all those level-lists.

Constraints to Keep in Mind:

• 0 <= Number of nodes in the tree <= 2000
• -1000 <= Node.val <= 1000
• The tree might be empty (root is null).

The Brute Force Approach

The naive way to get nodes level by level without a queue would be to run a DFS search multiple times.

• How it works: You run DFS to find all nodes at depth 0. Then you run DFS again from the root to find all nodes at depth 1. Then you run DFS again to find all nodes at depth 2, and so on, until a DFS finds nothing.
• Why it's too slow: Finding the nodes at depth d requires traversing all nodes above them. You end up visiting the top nodes many times. This takes O(n^2) time on a degenerate tree. To visit each node exactly once, we need to process the tree level by level in a single pass using Breadth-First Search (BFS).

The pattern

Any problem that says level, layer, row, or shortest number of steps is breadth-first search. A queue holds the frontier: take a node off the front, put its children on the back.

The one thing that needs care is knowing where one level ends and the next begins, since the queue mixes them.

The fix is one line: capture the queue's length before processing, and loop exactly that many times.

for _ in range(len(queue)):

At the top of each round, the queue holds exactly one complete level. Freezing that count means the children you add during the round belong to the next level and are not touched until the next round.

This line is the template for five problems in this chapter. Get it into muscle memory.

The solution

Python

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

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

        while queue:
            level = []
            for _ in range(len(queue)):        # exactly this level
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)

        return result

TypeScript

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  let queue: TreeNode[] = [root];

  while (queue.length) {
    const level: number[] = [];
    const next: TreeNode[] = [];
    for (const node of queue) {
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    result.push(level);
    queue = next;                              // swap in the next level
  }

  return result;
}

Code Walkthrough

1. if not root: return []: An empty tree should return an empty list of levels.
2. result = [], queue = deque([root]): Setup our final answer and seed the queue with the first level.
3. while queue:: While there are still nodes to process.
4. for _ in range(len(queue)):: The level freezer. We snapshot how many nodes are CURRENTLY in the queue. This is exactly the number of nodes in the current level.
5. node = queue.popleft(): Take the first node in line.
6. level.append(node.val): Add its value to our current level's bucket.
7. if node.left: queue.append(node.left) (and right): If it has children, queue them up. Because we are inside the frozen for loop, these newly queued children won't be popped until the next iteration of the while loop!
8. result.append(level): Once the for loop finishes, the current level is complete. Save it to result.

Hand Trace

Trace on the example tree:

• Initial: queue = [3], result = []

Round 1:

• len(queue) = 1. level = [].
• Pop 3. level = [3]. Enqueue its children: 9, 20. queue = [9, 20].
• Loop ends. result = [[3]].

Round 2:

• len(queue) = 2. level = [].
• Pop 9. level = [9]. No children. queue = [20].
• Pop 20. level = [9, 20]. Enqueue children: 15, 7. queue = [15, 7].
• Loop ends. result = [[3], [9, 20]].

Round 3:

• len(queue) = 2. level = [].
• Pop 15. level = [15]. No children. queue = [7].
• Pop 7. level = [15, 7]. No children. queue = [].
• Loop ends. result = [[3], [9, 20], [15, 7]].

queue is now empty, while loop terminates. Return result. ✓

Use a real queue. In Python, collections.deque removes from the front in O(1). A list with pop(0) is O(n) and turns this into a quadratic solution. JavaScript's Array.shift() has the same problem, which is why the TypeScript version builds the next level as a separate array and swaps — a common and clean way to sidestep it entirely.

Push children only if they exist, or the queue fills with nulls that must be filtered later.

Complexity

• Time Complexity: O(n). We enqueue each of the n nodes exactly once, and we dequeue each node exactly once. Doing O(1) work per node gives O(n) total time.
• Space Complexity: O(w) extra space, where w is the maximum width of the tree. For a balanced binary tree, the last level holds \lceil n/2 \rceil nodes, so w \approx n/2. Thus, space is O(n). BFS uses more memory than DFS on a balanced tree (O(n) against O(\log n)), and less on a degenerate one. That trade is why both traversals exist.

The five problems this template solves

Change what you do inside the level loop and you have solved:

problem	change
Level Order	collect all values — this page
Right Side View	keep only the last value of each level — 4.14.9
Average of Levels	sum and divide by the level size
Zigzag Level Order	reverse the list on alternate levels
Minimum Depth	return the level number at the first leaf you meet

Minimum Depth is the one worth pausing on: BFS finds it faster than DFS, because it can stop at the first leaf, while DFS has to explore everything. Whenever "shortest" or "fewest" appears, BFS is usually the right tool — and that becomes the whole argument for BFS in graphs in 4.20.

Doing it with DFS instead

You can produce level order with a depth-first walk, by passing the depth down and appending into the right bucket:

def levelOrder(self, root):
    result = []
    def dfs(node, depth):
        if not node: return
        if depth == len(result):
            result.append([])          # first node seen at this depth
        result[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    dfs(root, 0)
    return result

It works, it is O(n), and it uses O(h) space instead of O(w). Worth knowing as an answer to "can you do it without a queue", and worth knowing that it cannot stop early the way BFS can.

What the interviewer will push on

"How do you know where a level ends?" The frozen len(queue) at the top of each round.

"Why deque and not a list?" pop(0) is O(n).

"Which uses more memory, BFS or DFS?" BFS is O(w) and DFS is O(h). On a balanced tree BFS is worse; on a degenerate tree DFS is worse.

"Can you do it depth-first?" Yes, by indexing into the result by depth.

"What if the tree is enormous and you only need the first few levels?" BFS stops naturally; DFS would have to be depth-limited.

One thing to volunteer: name the frozen-length line as the level-boundary trick before writing it. Everything else in this problem is routine.

Next: 4.14.9 Binary Tree Right Side View — the same loop with one line changed.