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), 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:
- finding nodes far away from the root
BFS is better for:
- finding nodes close/closest to the root
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!