Press Play to watch BFS traverse the tree level-by-level, or Step to advance one operation at a time.
The result is built bottom-up using deque.appendleft().
TimeO(n)visit each node once
SpaceO(n)result + O(h) call stack
Key Insight
This pattern cleverly uses the fact that DFS will visit level 0 first, then level 1, then level 2, etc. The condition level == len(result) is true exactly once per level—the first time that level is visited.
✎ Whiteboard
3
⌨ Type It — Build Muscle Memory
Practice until you don't need to look. Use the guide comments below as scaffolding. Type the full implementation in the editor. The green highlights are the nuances to burn into memory.
═══ LEVEL ORDER TRAVERSAL II — BFS ITERATIVE ═══
PATTERN ▸ BFS + deque (bottom-up) O(n) · O(n)
① BASE CASE
if not root: return []
② INIT
result = deque()
queue = deque([root])
③ BFS LOOP
while queue:
level_size = len(queue)
level = []
④ PROCESS LEVEL
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
⑤ APPENDLEFT & RETURN
result.appendleft(level)
return list(result)
▼ your implementation ▼
Verify your solution:
⌨ Type It — Recursive DFS
Practice until you don't need to look. The green highlights are the nuances to burn into memory.