Return the values of a binary tree in breadth-first (level) order: top to bottom, left to right.
breadthFirstValues(root)
Input format: level-order with x for missing children. Output the values
space-separated.
3 9 20 x x 15 7 // → 3 9 20 15 7
1 2 3 // → 1 2 3
(empty) // → (empty)
This wants values ordered by distance from the root — everything on level 0, then level 1, then level 2, and so on. That's fundamentally different from depth-first order, where you plunge down one branch before looking at a sibling. Recursion naturally gives depth-first order, since the call stack finishes one branch before returning to try another — it has no notion of "level." The tools you'd reach for on other tree problems don't fit here, and that mismatch is the insight: the shape of traversal you need should drive the data structure, not the other way around.
You need to process nodes in the exact order you discover them, discovering a node's children only after the node itself is processed, left before right. That's first-in-first-out — a queue. A stack (last-in-first-out), which is what recursion gives you, would dive deep into one child before even looking at its sibling — the depth-first behavior you're avoiding.
When you dequeue the root and enqueue its two children, they're guaranteed to come out next, before anything from a deeper level — nothing deeper has been enqueued yet. A node's children only get added after their parent has been dequeued, so no node can jump ahead of an entire earlier level. First-in-first-out is exactly what enforces "finish level N before touching level N+1," with no explicit level-tracking needed.
Every node is enqueued once and dequeued once, so work is proportional to the number of nodes. The queue holds at most as many nodes as the tree's widest level, which bounds the extra memory.
def breadth_first_values(root):
if root is None:
return []
values = []
queue = [root]
i = 0
while i < len(queue):
node = queue[i]
i += 1
values.append(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return values
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.