← Back to problems Solve on LeetCode → ◆ Tree Patterns See #107 Bottom-Up →

Binary Tree Level Order Traversal

BFS — Top-Down Level Collection

LeetCode 102 • Medium • Trees

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

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 top-down using result.append(level).

Compare: LeetCode #107 uses appendleft for bottom-up order →

✎ 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 (LeetCode 102) ───

# Pattern: BFS + queue for top-down collection

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

# 1. Import: from collections import deque

# 2. Define: levelOrder(self, root)

# Base case: if not root: return []

# 3. Init data structures:

# result = [] ← regular list (top-down)

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

# 4. BFS loop: while queue:

# Snapshot level size: level_size = len(queue)

# Collect level: current_level = []

# 5. Process each node in level:

# for i in range(level_size):

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

# current_level.append(node.val)

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

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

# 6. KEY LINE — top-down insertion:

# result.append(current_level) ← append to end!

# 7. Return: return result

# Vars: result (list), queue (deque), current_level, node

# vs #107: uses [] + append instead of deque + appendleft

▼ 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 — RECURSIVE DFS ═══

PATTERN ▸ DFS + level index 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 & RETURN

dfs(root, 0)

return result

▼ your implementation ▼

Verify your solution: