The problem
Return the values of a binary tree level by level, from top to bottom and left to right within each level.
Input: [3, 9, 20, null, null, 15, 7] Output: [[3], [9, 20], [15, 7]]
Picture it
Picture a family photo with one generation per row. A queue holds everyone in the current row. We take them out one by one, write down their value, and put their children at the back of the queue. When the current row is used up, the queue holds exactly the next row.
How to recognise it
- The output is grouped by depth: everything at level 0, then level 1, and so on.
- Within a level the order is left to right, the order in which a queue naturally hands nodes out.
- That is breadth-first search (BFS: visit all nodes at one distance before any farther ones). The extra twist is knowing where one level ends and the next begins.
- Up to 2,000 nodes, so visit each node once.
Start with brute force
Collect one level at a time: for depth 0, 1, 2, ... walk the whole tree and keep the nodes at exactly that depth. Stop when a depth comes back empty.
def level_order_brute(root):
def collect(node, d, out):
if not node:
return
if d == 0:
out.append(node.val)
collect(node.left, d - 1, out)
collect(node.right, d - 1, out)
levels, d = [], 0
while True:
row = []
collect(root, d, row)
if not row:
return levels
levels.append(row)
d += 1
The depth-first walk visits left before right, so each row comes out in the right order. But every level re-walks the tree from the root down to that level: O(n · h) time, where h is the height. A 2,000-node chain costs about 2 × 10^6 steps, and the recursion also exceeds Python's default limit of about 1,000 frames.
From brute force to the idea
- Find the waste. To reach level d, the brute force walks again through every level above it.
- Use a queue. A
deque(double-ended queue) givespopleft()in O(1). If each node adds its children to the back, nodes come out in level order, left to right. - Mark the level boundary. At the start of each round the queue holds exactly one full level and nothing else. So read
len(q)once, pop exactly that many nodes intolevel, and push their children; the children wait for the next round. - Save the row. After the inner loop,
levelis complete; append it toout.
This is the key idea: a BFS queue, processed in rounds of len(q) nodes, gives one level per round.
range(len(q)) is evaluated once, before the inner loop starts, so children appended during the loop do not change how many nodes this round pops.
The shown code needs from collections import deque. A plain list with pop(0) gives the same output but costs O(n) per pop.
The key idea
Breadth-first search with a queue, processing one level (queue length) at a time. O(n).
Python solution
def level_order(root):
if not root:
return []
q, out = deque([root]), []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
out.append(level)
return outLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (one walk per level) | O(n · h): each level re-walks the levels above it | O(h): recursion stack, plus the output |
| BFS in rounds (shown code) | O(n): each node enters and leaves the queue once | O(w): the queue holds at most one level plus children, w is the widest level (up to about n/2) |
The output itself always takes O(n).
Edge cases
- Empty tree: returns
[], not[[]], thanks to the first check. - Single node:
[[1]]. - Chain of nodes: one value per level, for example
[[2], [1], [0]]. - Missing children: skipped by the
if node.leftchecks, soNonenever enters the queue. - Deep chain of 2,000 nodes: works, because BFS uses a loop and no recursion.
Common mistakes
- Popping until the queue is empty in the inner loop instead of
len(q)times, which merges every level into one row. - Popping from the end (
pop()) instead of the front: the container acts as a stack, and nodes from different levels get mixed into one row. - Pushing
Nonechildren and then readingnode.valon them. - Returning
[[]]for an empty tree.
Return the levels in zigzag order (LeetCode 103): the first level left to right, the next right to left, and so on. For [3, 9, 20, null, null, 15, 7] the answer is [[3], [20, 9], [15, 7]]. Describe your approach, then write it if you like.
Compare with our answer
Keep the same BFS in rounds. Only the saving step changes: reverse every second row before adding it. The queue order itself stays left to right.
from collections import deque
def zigzag(root):
if not root:
return []
q, out = deque([root]), []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
out.append(level if len(out) % 2 == 0 else level[::-1])
return out
Time O(n), space O(w).
A strong answer mentions: reversing the collected row rather than changing the order children are pushed, using the row number to decide, and that the cost stays O(n).
1. You must print a company org chart one management layer per line, top first. Which approach fits best?
Rounds of BFS give exactly one layer per round in O(n). A single DFS mixes layers, and restarting per layer repeats the upper layers every time.
2. Why does the shown code read len(q) before popping a level?
At the start of a round the queue contains one whole level and nothing else; popping that many nodes empties it of this level while the newly pushed children wait for the next round.
3. A learner replaces for _ in range(len(q)): with an inner while q:. Which tree still gets the right output?
The inner loop now keeps popping the children it just pushed, so every level lands in one row: [1, 2] gives [[1, 2]] instead of [[1], [2]]. A single node has no second level to merge.
Score 60% or more and the lesson is marked complete.