← Back to problems Solve on LeetCode → ◆ Tree Patterns See #102 Top-Down →

Binary Tree Level Order Traversal II

BFS + Deque — Bottom-Up Level Collection

LeetCode 107 • Medium • Trees

Input: root = [3, 9, 20, null, null, 15, 7] → Output: [[15,7], [9,20], [3]]

Time O(n) visit each node once

Space O(n) queue + result

Visited: 0/5 Queue: 0 Peak Q: 0

Processing

In Queue

Processed

Edge highlight

Queue

empty

Level

[ ]

Result

[ ]

Speed:

Ready

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().

✎ Whiteboard

Size: 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 (LeetCode 107) ───

# Pattern: BFS + deque for bottom-up collection

# Time: O(n) Space: O(n)

# 1. Import: from collections import deque

# 2. Define: levelOrderBottom(self, root)

# Base case: if not root: return []

# 3. Init data structures:

# result = deque() ← deque for O(1) appendleft

# queue = deque([root]) ← BFS queue starts with root

# 4. BFS loop: while queue:

# Snapshot level size: level_size = len(queue)

# Collect level: level = []

# 5. Process each node in level:

# for _ in range(level_size):

# node = queue.popleft() ← O(1) dequeue

# level.append(node.val)

# if node.left: queue.append(node.left)

# if node.right: queue.append(node.right)

# 6. KEY LINE — bottom-up insertion:

# result.appendleft(level) ← prepend!

# 7. Return: return list(result)

# Vars: result (deque), queue (deque), level, node

# vs #102: uses deque() + appendleft instead of list + append

▼ 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.

═══ LEVEL ORDER BOTTOM — RECURSIVE DFS ═══

PATTERN ▸ DFS + level index + reverse O(n) · O(n)+O(h)

① OUTER SETUP

result = []

② INNER DFS + BASE

def dfs(node, level):

base → if not node: return

③ EXTEND IF NEW LEVEL

if level == len(result):

result.append([])

④ COLLECT VALUE

result[level].append(node.val)

⑤ RECURSE LEFT & RIGHT

dfs(node.left, level + 1)

dfs(node.right, level + 1)

⑥ KICK OFF & REVERSE

dfs(root, 0)

return result[::-1] ← only diff vs #102!

▼ your implementation ▼

Verify your solution: