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:

First slide
First slide
PreviousNext

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.

First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
PreviousNext

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!