Breadth First Search — An Overview

5 min readFeb 19, 2021

Overview

Graph traversal means visiting every vertex and edge exactly once in a well-defined order. The order in which the vertices are visited depend on the type of algorithm methods you are using for a specific task. For the article, we will create the following Binary Tree where we will explore the Breadth First Search method to traverse through the tree and search a specific thing (anecdotally a specific fruit on a tree 🍎)

Breadth First Search. “What Is It?”

Traversing through the binary tree can come in 2 popular ways. One, you can use the Depth First Search method where the search goes through branch by branch in the binary tree and search something (say a target value).

But the second, which this article will discuss, will be the Breadth First Search method. Breadth First Search is the most commonly used approach and traverses through the tree layer by layer.

Breadth First Search (BFS) algorithm traverses a graph in a breadth ward motion and uses a queue to remember to get the next vertex to start a search. BFS starts from a selected node (source or starting node) and traverse the graph layer wise exploring the neighbor nodes (nodes which are directly connected to source node). Then, the search move towards the next level neighbor nodes.

Queues, Queues, Queues

Queues are an array of to-visit nodes where it is populated while visiting nodes layer by layer and evaluating the children. So the enque occurs if the current node has children and every children is pushed into the Queue array so that it will be evaluated after the algorithm moves onto the next layer. And as the Queue’d nodes are visited, deque occurs as the algorithm removes the front element of the Queue array and stashes it into the Stash/Visited Nodes Array.

Implementing the Breadth First Search

Now let’s dive into the code with the instructions in mind. We will walkthrough how to implement the BFS algorithm which starts from constructing a binary tree and adding children to each nodes to finally return an array that has traversed through all the nodes of the tree while using the Breadth First Search method.

Let’s dissect the construction of the binary tree for the BFS search.

Foundations of the tree object is created like this:

the following creates the structure of the binary tree by adding the name of the node and its children (as an array)constructor(name) {
//this creates the node as name  this.name = name;//this creates the node's children for the binary tree
  this.children = []
}

Children of a node is added with the following method:

addChild(name){
  //pushes the newly created nodes in to the children array.  this.children.push(new Node(name));
  //return the created branch  return this
}

Now toward the breadth first search:

breadthFirstSearch(stashArray) {
  //create a queue array to store queues. This can be done by creating an array with just the root node as a starting point .  const queue = [this]
  //add the tree branches until the queue's length is 0 or less! (which in this case wont be until the very tip of the branch)  while (queue.length > 0) {  //currently iterated queue element will be the first element of the queue
    const current = queue.shift()  //add the name of the node to the Stashed/Visited Array as you're traversing through the tree    stashArray.push(current.name);
  //for each child of the node in the current element of the queue, add the children associated to the node in to the queue    for (const child of current.children) {
      queue.push(child)
    }
  }
  //finally return the array with all the Stashed/Visited elements  return stashArray
}

Time/Space Complexity

For the time complexity of the Breadth First Search, there are two things to keep in mind. First, we will need to traverse through every vertices as we are performing the search. This means that the time to perform the algorithm will increase as size of the vertices increase. In addition, edges connect the vertices and determine how they are connected to the children. So that edges take into the factor of time complexity as well.

Taking in all the factors, the time complexity will look like the following at it’s worst:

O (v + e)

where:

v represents the number of vertices in the binary tree

e represents the number of edges in the binary tree that are connecting the vertices

Now onto the space complexity of the Breadth First Search, there is one thing to keep in mind as we are traversing through the tree with the method. It’s the queue size as we are visiting the nodes layer by layer. So at its worst, space complexity increases by O(v), where again, v represents the number of vertices in the binary tree.

O(v)

Recursive Solution?? — “no”

Now, the above solution uses iteration to store queues to remember the children nodes as the algorithm performs the search layer to layer. However, the question is, does breadth first search have a recursive solution? Although this is definitely a valid question when we are creating search algorithms but the simple answer is — no.

The reason is that breadth first search uses queues (First In First Out) and the recursive method depends on the stacks (Last In Last Out). Since the breadth first search method requires queues to perform the search, recursive solutions cannot be implemented in this case because the call stacks cannot be performed to create queues as iteration can.

So no recursive will be performed for this overview to explore the breadth for search algorithm.

Concept Summary

So in short, here are the gist steps as to what the BFS does so far:

1) Move horizontally and visit all the nodes of the current layer the search is in.

2) Store the queue of all the future Nodes, and stash the current node into a stash/visited nodes array.

3) Move on to the next layer while following the queue.

With the Breadth First Search, you can finally look for that target (ex. 🍎) you are looking for as you traverse through the binary tree!