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:

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:

  • 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
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 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!