IntermediateTrees
BFS level by level
Use a queue, and at the start of each round note its size: that many nodes are exactly one level.
The idea
Breadth-first search visits nodes in order of distance from the start, using a queue. To group them by level, read the queue's size at the start of each round and process exactly that many nodes.
The same loop answers “right side view” (last of each level), “zigzag” and minimum depth.
Worked example
Root 3 with children 9 and 20, and 20's children 15 and 7
- queue [3] → size 1 → level [3], queue [9, 20]
- size 2 → level [9, 20], queue [15, 7]
- size 2 → level [15, 7] → done
In code (Python)
from collections import deque
def level_order(root):
if not root:
return []
levels, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)): # exactly one level
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.append(level)
return levelsO(n) time, O(width) space.
How to spot it
- “level”, “layer”, “closest”, “minimum depth”, “right side view”.
Common mistakes
- Using a list and pop(0), which is O(n) per pop: use deque.
- Reading len(queue) inside the loop condition after appending children.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →