Level Order Traversal 20 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

Level Order Traversal (BFS) visits nodes level by level, left to right. While DFS uses recursion/stack, BFS uses a queue.

#       3
#      / \
#     9   20
#        /  \
#       15   7
# Level order: [[3], [9, 20], [15, 7]]

Algorithm:

Start with root in a queue
For each level, process all nodes currently in the queue
For each node, add its children to the queue for the next level
Collect values level by level into a list of lists

The key trick: use for _ in range(len(queue)) to process exactly one level at a time. Time: O(n), Space: O(n).

📋 Instructions

Implement `level_order(root)` using BFS with a queue. Return a list of lists where each inner list contains values at that level.

Use collections.deque. While queue: get level_size = len(queue). Loop level_size times, popleft each node, add val to current level, append children. Add level list to result.

🧪 Test Cases

Input

level_order(root)

Expected

[[3], [9, 20], [15, 7]]

Test case 1

Input

level_order(None)

Expected

[]

Edge case — null/empty input

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›