Binary Tree Level Order Traversal
Return the level-order traversal of a binary tree.
Pattern fit
Level-by-level output is exactly what BFS already gives you, so the queue order mirrors the answer shape directly.
Key observation
One queue layer equals one answer layer, so you should snapshot the queue size before processing the current level.
Target complexity
O(n) / O(w)
How to break down the solution cleanly
Level-by-level output is exactly what BFS already gives you, so the queue order mirrors the answer shape directly.
One queue layer equals one answer layer, so you should snapshot the queue size before processing the current level.
Identify the graph model and how neighbors are generated.
Choose BFS for shortest unweighted distance or DFS for structure exploration.
Reference implementation
Python# Generic pattern template
from collections import deque
def bfs(start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
queue.append(nxt)
def dfs(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs(nxt)
Common pitfalls
Appending children without fixing the current level size first.
Mixing nodes from the next level into the current output.
Common follow-ups
How would you return zigzag level order?
Could you solve it with DFS too?
Continue with related problems
Build repeatable depth inside the BFS / DFS cluster before moving on.