BFS vs. DFS: Understanding Breadth First Search & Depth First Search

---

During interview preparation, we can apply the 80/20 rule and realize that learning certain techniques significantly improve our ability to solve problems relative to others. Breadth First Search (BFS) and Depth First Search (BFS) are two of the most common strategies to in solving tree problems during an interview, and can likely be used to solve roughly two-thirds of tree and graph problems you may get.

What's a Tree Again?

A tree is a hierarchical data structure with a root node and corresponding child nodes. Child nodes can further have their own child nodes. A node with no child is called a leaf node.

Nodes are connected via edges, also called links or lines.

Searching a tree refers to traversing all the nodes of a tree where each node is visited only once.

How Do We Traverse a Tree?

There are two main ways to search a tree: Breadth First Search (BFS) and Depth First Search (DFS). This lesson explains these two search techniques along with their Python implementations, and allows for a helpful comparison of the two methods.

To explain the concepts in this article, the following tree will be used as an example:

Breadth First Search (BFS)

The Theory

In Breadth First Search (BFS), the key is that it is level-based, or row-based. At each level or row, the nodes of a tree are traversed horizontally from left to right or right to left. In this section, we will see how to perform breadth first search from left to right.

For instance, if you look at the example tree above, the tree has 4 levels.

1. At level 1, the tree has the root node A.
2. At level 2 it has two nodes B and C.
3. Similarly, level 3 contains nodes D, E, F, G.
4. Finally at level 4, nodes H, I, J are present. If the tree is searched via the breadth first search technique, the nodes would be traversed in the following order:

A-B-C-D-E-F-G-H

The steps to implement the breadth first search technique to traverse the above tree are as follows:

1. Add the node at the root to a queue. For instance, in the above example, the node A will be added to the queue.
2. Pop an item from the queue and print/process it.
3. Add all the children of node popped in step two to the queue. At this point of time, the queue will contain the children of node A:

queue = [B, C]

Repeat steps 2 and 3 until the queue is empty.

Python Implementation for BFS

The python implementation for the BFS is as follows:

import collections

class Tree_Node:
    def __init__(self,root_value,children_nodes):
        self.value = root_value
        self.children_nodes  = children_nodes

def breadth_first_search(Root_Node): 
    queue = collections.deque()
    queue.append(Root_Node.value)

    while queue:
        node_value = queue.popleft()
        print(node_value)
        children_nodes = nodes_dic[node_value]

        for i in children_nodes:
            if i == None:
                continue
            queue.append(i)

In the script above we create a class Tree_Node and a method breadth_first_search(). The tree_node class contains the value of the root node and the list of child nodes.

The breadth_first_search() method implements steps 1 through 3, as explained in the theory section. You simply have to pass the root node to this method and it will traverse the tree with using BFS.

Let's now create a tree with the tree that we saw in the diagram.

nodes_dic =  {"A":["B","C"],
              "B":["D","E"],
              "C":["F","G"],
              "D":[None],
              "E":["H","I"],
              "F":[None],
              "G":["J",None],
              "H":[None],
              "I":[None],
              "J":[None]}

In the script above we create a dictionary nodes_dic where each element corresponds to node of a tree.

The key is the value of the root node, whereas the value of each item in the dictionary is the corresponding list of child nodes. _For instance, the first dictionary element contains A as the key and a list of child nodes B and C as the value. _

We will create an object of the root node class, and then initialize it with first item in the dictionary:

root_node_value = next(iter(nodes_dic.keys()))
root_node_children = next(iter(nodes_dic.values()))
root_node = Tree_Node(root_node_value,root_node_children)

Finally, we can simply pass the root node to the breadth_first_search method to traverse the tree.

depth_first_search(root_node) 

In the output, you will then see the following expected sequence of nodes:

A
B
C
D
E
F
G
H
I
J

When To Use BFS

A few pointers on preferring BFS:

• When you need to find the shortest path between any two nodes in an unweighted graph.
• If you're solving a problem, and know a solution is not far from the root of the tree, BFS will likely get you there faster.
• If the tree is very deep, BFS might be faster.

What About Depth First Search (DFS)?

The Theory

In Depth First Search (DFS), a tree is traversed vertically from top to bottom or bottom to top. There are three main ways to apply Depth First Search to a tree.

They are as follows:

• Preorder Traversal - We start from the root node and search the tree vertically (top to bottom), traversing from left to right. The order of visits is ROOT-LEFT-RIGHT.

• In-order Traversal - Start from the left most node and move to the right nodes traversing from top to bottom. The order of visits is LEFT-ROOT-RIGHT.

• Post-order Traversal - Start from the left most node and move to the right nodes, traversing from bottom to top. The order of visits is LEFT-RIGHT-ROOT.

Let's focus on Preorder Traversal for now, which is the most common type of depth first search.

If you traverse the example tree in this article using Preorder Traversal, the tree nodes will be traversed in the following order:

A-B-D-E-H-I-C-F-G-J

The following are the steps required to perform a Preorder Traversal DFS:

1. Add the root node to a stack. For the example tree in this article, the node A will be added to the stack.
2. Pop the item from the stack and print/process it. The node A will be printed.
3. Add the right child of the node popped in step 2 to the stack and then add the left child to the stack. Because the nodes are traversed from left to right in Preorder Traversal, the node added last in the stack (the left node) will be processed first. In this case, the nodes C and B will be added to the stack, respectively.
4. Repeat the steps 2 and 3 until stack is empty.

Python Implementation for DFS

The python script for Preorder Traversal DFS is as follows:

class Tree_Node: 
    def __init__(self,root_value,children_nodes):
        self.value = root_value
        self.left_child = children_nodes[0]
        self.right_child = children_nodes[1]


def depth_first_search(Root_Node): 
    if Root_Node.value is None: 
        return 

    stack = [] 
    stack.append(Root_Node.value) 

    while(len(stack) > 0): 

        node_value = stack.pop() 
        print (node_value) 
        children_nodes = nodes_dic[node_value]  

        if not(len(children_nodes) == 1 and children_nodes[0] == None):
            if children_nodes[1] is not None: 
                stack.append(children_nodes[1]) 
            if children_nodes[0] is not None: 
                stack.append(children_nodes[0]) 

The depth_first_search() method in the script above performs Preorder Traversal BFS. Let's create nodes for the example tree and test the working of depth_first_search() method.

nodes_dic =  {"A":["B","C"],
              "B":["D","E"],
              "C":["F","G"],
              "D":[None],
              "E":["H","I"],
              "F":[None],
              "G":["J", None],
              "H":[None],
              "I":[None],
              "J":[None]}

root_node_value = next(iter(nodes_dic.keys()))
root_node_children = next(iter(nodes_dic.values()))
root_node = Tree_Node(root_node_value ,root_node_children )

depth_first_search(root_node) 

And here is the final expected output:

A
B
D
E
H
I
C
F
G
J

When To Use DFS

A few pointers on preferring DFS:

• If there's a large branching factor (wide) but limited depth.
• DFS is more space efficient than BFS.
• If the tree is very wide, BFS will likely be incredibly memory inefficient, so DFS could be better.

---

---

Back