Know this before you start: “BFS: level order with a queue”
Breadth-first traversal with a queue
Use a queue to visit a tree level by level. Read the queue's size at the start of each round: that many nodes are exactly one level.
The idea
Breadth-first search visits all nodes at depth 1, then depth 2, and so on. A queue (first in, first out) gives exactly that order: take a node from the front, add its children to the back.
To group nodes by level, note how many are in the queue when a round starts and process exactly that many. Python's collections.deque pops from the front in O(1).
See it step by step
Tree 3 → (9, 20), 20 → (15, 7)
- queue [3] → level [3], queue [9, 20]
- 2 in the queue → level [9, 20], queue [15, 7]
- 2 in the queue → level [15, 7] → done: [[3], [9, 20], [15, 7]]
In code (Python)
from collections import deque
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def levels(root):
if not root:
return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)): # exactly one level
node = queue.popleft()
level.append(node.val)
for child in (node.left, node.right):
if child:
queue.append(child)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levels(root)) # [[3], [9, 20], [15, 7]]O(n) time, O(width) space.
When you'll use it
- Level order, right side view, minimum depth, zigzag, “closest” or “nearest” in trees.
Common mistakes
- list.pop(0), which is O(n): use deque.popleft().
- Reading len(queue) after children were added.
