Mental Model
Imagine you have a tree and you want to visit every node level-by-level. Naively, you might try to do the following,
You visit every node successfully, but since nodes on the same level (adjacent nodes) usually belong to different subtrees, you end up taking very long, inefficient paths moving back and forth between these subtrees, especially as you reach deeper levels.
How could we reduce those long paths?
What if we saved A as a “root” and used it as a starting point whenever we wanted to reach any node?
Setting A as a starting point (root) made,
- the path to its children (B and C) the simplest it could be.
- the paths that require transitioning between its left and right subtrees simpler.
This is great, but can we do better?
why don’t we do the exact same thing with B and C?
Doing this made,
- the path to their children (D, E) and (F, G) the simplest it could be.
- the paths that require transitioning between their left and right subtrees simpler.
If we save every set of parents on each level as local “roots,” we guarantee the simplest access to their children, and thus to the whole tree.
This level-by-level expansion is exactly what Breadth First Search (BFS) is.