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

---

During the days and weeks before a technical interview, we can apply the 80/20 rule for more efficient preparation. The 80/20 rule, otherwise known as Pareto's Law, stipulates that roughly 80% of your results will come from 20% of your efforts. Once you've seen the lay of the land with software engineering interview concepts, you'll find that learning certain techniques will 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 employed in problems given during an interview. Master the two methods, as they can likely be used to solve roughly two-thirds of tree and graph problems that you may potentially see. Additionally, a surprising number of seemingly unrelated challenges can be mapped as tree or graph problems (see Levenshtein Edit Distance, Split Set to Equal Subsets, and Pick a Sign.

What's a Tree Again?

In programming, a tree is a hierarchical data structure with a root node and corresponding child nodes. Child nodes can further have their own child nodes. Various types of trees will have unique requirements around the number or categorization of child nodes. Alternatively, node with no child is typically called a leaf node.

Nodes are connected via edges, also called links or lines. These terms all simply refer to the connection between two vertices.

Traversal of a tree refers to visiting, or performing an operation, at each node. 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 alongside 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. The horizontal direction chosen will depend on the problem statement-- for instance, a problem that is looking for the sum of all nodes on the right hand side may necessitate right-to-left traversal. This would allow you to just grab the first node, and immediately mvoe on to the next level.

In this lesson, we will see how to perform breadth first search from left to right.

Let's take an example. 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. This is important-- 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]

At this point, we've completed our processing of level 1. We would then repeat steps 2 and 3 for B and C of level 2, and continue 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 scenarios and pointers on when to prefer BFS over DFS:

• 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. As you might infer from its namesake, we will traverse as deeply as possible, before moving on to a neighbor node. 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