0
Challenge · 42Trees

BFS: level order

Treesused in ~95% of apps

The other way to walk a tree, and the first appearance of the queue you built in tier 5. Depth first dives. Breadth first spreads. Which one you pick decides whether you can answer questions about distance at all.

Core idea. Breadth first search finishes every node on one level before touching the next. A queue does the work: take the node at the front, push its children onto the back, repeat. Because you always reach a node by the shortest route, this is the traversal that answers anything about levels or distance.
Playground, this isn't a screenshot
one level finished before the next one starts
nothing visited yet
level 08
level 13, 10
level 21, 6, 14

Nothing on level two is touched until level one is completely done.

↑ play a little first, then dig in