Breadth First Search on Trees
Hopefully, by this time, you've drunk enough DFS Kool-Aid to understand its immense power and seen enough visualization to create a call stack in your mind. Now, let me introduce the companion spell: Breadth First Search (BFS). The names are self-explanatory. While depth first search reaches for depth (child nodes) first before breadth (nodes in the same level/depth), breadth first search visits all nodes in a level before starting to visit the next level.
DFS vs BFS order of visits:
While DFS uses recursion/stack to keep track of progress, BFS uses a queue (First In First Out). When we dequeue a node, we enqueue its children.
DFS vs BFS
Now, a question naturally arises: which one should I use? Or, more fundamentally, which tasks do they each excel at? Since they are both algorithms that traverse nodes in a tree, the only differences are caused by the different order of traversal:
DFS is better at:
- finding nodes far away from the root
BFS is better for:
- finding nodes close/closest to the root
Template
We can implement BFS using a queue. Important things to remember:
- We need at least one element to kick start the process.
- Right after we dequeue an element, we'd want to enqueue its children if there are any
1from collections import deque
2
3def bfs_by_queue(root):
4 queue = deque([root]) # at least one element in the queue to kick start bfs
5 while len(queue) > 0: # as long as there is an element in the queue
6 node = queue.popleft() # dequeue
7 for child in node.children: # enqueue children
8 if OK(child): # early return if problem condition met
9 return FOUND(child)
10 queue.append(child)
11 return NOT_FOUND
Pretty straightforward, right? Let's practice BFS with a few problems!
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.