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 see call stack in your mind. Now let me introduce the companion spell Breadth First Search. The names are self-explanatory. While depth first search reaches for depth (child nodes) first before breadth (nodes in the same level/depth), breath 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:
- narrow but deep trees
- finding nodes far away from the root
BFS is better for:
- shallow but wide trees
- 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 is any
from collections import deque
def bfs_by_queue(root):
queue = deque([root]) # at least one element in the queue to kick start bfs
while len(queue) > 0: # as long as there is element in the queue
node = queue.popleft() # dequeue
for child in node.children: # enqueue children
if OK(child): # early return if problem condition met
return FOUND(child)
queue.append(child)
return NOT_FOUND
Pretty straightforward, right? Let's practice BFS with a few problems!