Tree BFS: Level by Level

Beginner · 14 min read · Problem-Solving Patterns, Trees

Level-order traversal and every "per level" question.

DFS dives deep along one branch before trying the next. BFS (breadth-first search) does the opposite: it visits the tree level by level — the root, then all its children, then all their children.

The template: freeze the level size

A queue naturally gives level order: children are added to the back while the current level is processed from the front. The one trick is to record the queue's size at the start of each round — that's exactly how many nodes belong to the current level.

Worked problems

The last node processed on each level is the one visible from the right:

BFS or DFS?

Both visit every node once: O(n) time. Memory differs: BFS uses O(width), recursive DFS uses O(height).

Practice ladder

Interview questions

• How do you separate levels in a BFS over a tree?
• Why is BFS better than DFS for minimum depth?

Further reading

Key takeaways

• BFS processes a tree level by level with a queue.
• Freeze size = queue.size() at the start of each round to separate levels.
• BFS finds the shallowest answer first — stop early for minimum depth and nearest-node questions.
• Choose by question type: per-level and nearest → BFS; subtree combinations → DFS.

Previous: Tree DFS: Think in Subtrees · Next: Binary Search Trees