Week 4 · Trees

Binary Tree Level Order Traversal

Return the values of a binary tree grouped by depth from top to bottom and left to right within each level.

Medium Trees Week 4 Practice runner

Frame the problem

An empty tree returns an empty list.
The result needs one list per level.
Left-to-right order within a level matters.

1. Reveal example inputs and outputs

Example 1

Input:

level_order([
  3,
  [
    9,
    null,
    null
  ],
  [
    20,
    [
      15,
      null,
      null
    ],
    [
      7,
      null,
      null
    ]
  ]
])

Output:

Example 2

Input:

level_order(null)

Output:

[]

2. Brute force first

If you used DFS, what extra state would you need to know which output list receives each value?

3. Reveal the insight ladder

BFS naturally visits nodes by level.
A queue holds the frontier for the next nodes to process.
The current queue length tells you exactly how many nodes belong to this level.
Append children for the next level after reading the current node.

4. Dry run before code

Start queue with root 3.
Level 1 consumes 3 and enqueues 9 and 20.
Level 2 consumes 9 and 20 and enqueues 15 and 7.
Level 3 consumes 15 and 7.

5. Reveal final Python solution

from collections import deque

def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            value, left, right = queue.popleft()
            level.append(value)
            if left is not None:
                queue.append(left)
            if right is not None:
                queue.append(right)
        result.append(level)
    return result

Complexity: Time O(n), space O(w), where w is the maximum tree width held in the queue.

Interview narration

I will process the tree one level at a time.
The loop over the current queue length prevents nodes from the next level from leaking into this level.
Children are enqueued left before right to preserve output order.

Common traps

Using while queue and appending one flat list instead of grouping by level.
Recomputing queue length after adding children inside the level loop.
Returning None instead of [] for an empty tree.

Follow-up drills

1. How would you produce zigzag level order?

Keep the same BFS boundaries, but reverse every other level or append into a deque from alternating ends.

2. How would DFS solve this?

Pass depth into recursion. If depth equals len(result), append a new level list, then append the node value into result[depth].

3. What drives space complexity?

The largest frontier width, not necessarily the height. A complete tree can hold O(n) nodes at the last level.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.