Implementing Breadth First Search in JavaScript

A step-by-step guide to traversing a tree with breadth first search.

Photo by Sylvia Yang on Unsplash

What is Breadth First Search?

Breadth first search is an algorithm for searching a tree or graph data structure. It begins at the root node then explores all nodes left to right, level by level. Breadth first search follows the FIFO (first in, first out) principle and can be implemented with a queue.

Before We Begin…

For this walkthrough we’ll be writing a function breadthFirstSearch, which will take in a root node, traverse the entire tree and return an array with all the node values in breadth first search order.

The nodes will be defined with the class, Node.

So, given the below tree breadthFirstSearch should return [6, 9, 12, 5, 7, 8, 11, 18, 10, 4, 3].

To Begin, Create a Queue

First, we need to create a queue. The queue will keep track of what nodes need to be searched. We can create a queue with a standard array. We’ll set the first element in the array to root, since we want to begin our search with the root node, node 6.

function depthFirstSearch(root) {
  // Empty array to store node values
  const result = []; 
  // Define queue
  const queue = [root]; 
  // Return final array
  return result; 
}

Create a While Loop

Now, we need to create a while loop. This loop will run as long as the queue is not empty. In other words, it will run as long we still have nodes to traverse.

function depthFirstSearch(root) {
  const result = [];  
  const queue = [root];
  // Create while loop
  while (queue.length > 0) {
     
  }
return result; 
}

While Loop Logic

While inside of the while loop, we need to remove the first node in the queue and set it to the variable current. We can achieve this by setting current to queue.shift().

while (queue.length > 0) {
  const current = queue.shift();
}

Next, we need to make sure the current node is not null (a leaf node).

while (queue.length > 0) {
  const current = queue.shift();
  // If the node is null, we know we've reached the end of a branch
  if (current === null) continue;
}

With our current variable set, we can push current.value to our final result array.

while (queue.length > 0) {
  const current = queue.shift();
  if (current === null) continue;
  // Push node value to final array
  result.push(current.value)
}

Lastly, we can add the current node’s children to the queue.

while (queue.length > 0) {
  const current = queue.shift();
  if (current === null) continue;
  result.push(current.value)
  // Add child nodes to queue
  for (const child of current.children) {
    queue.push(child);
  }
}

The final function looks like this.

Time Complexity

Graphs are made up of vertices and edges. Vertices are the nodes. Edges are what connects the nodes (the lines in between). The time complexity of this algorithm is O(V + E), where V is the number of vertices in the graph and E is the number of edges.

Let’s break this down a bit.

The O(V) time complexity comes from the fact that we are visiting every single node in the tree.

However!

While at each node, we are also iterating through all the child nodes. The amount of edges coming out of a node is equal to the amount of child nodes it has. For example, node 6 has three edges and three child nodes. Node 7 on the other hand has two edges coming out of it and two child nodes accordingly. This results in an additional O(E) time complexity, bringing the grand total time complexity to O(V + E).

Space Complexity

The time complexity for this algorithm is O(V). This is a worst case scenario. Imagine if we had a tree that looked like this.

In this scenario, there would be a point where we had to store V - 1 nodes inside of the queue all at once bringing the space complexity to O(V).

For our depthFirstSearch() function, because we are storing the value of each node inside of an array anyways, it will always be O(V) space complexity.

Conclusion

In summary, the steps necessary to implement breadth first search are as follows:

1. Create a queue. This is where we’ll store nodes that need to be searched. To begin, it will have the root node only.

1. Remove the first node from the queue. It will now be the current node.
2. With the current node value set, we can then apply any necessary logic (e.g. push value to array, check for specific value, etc).
3. Next, add all of the current node’s children into the queue (left to right order).

4. Now we repeat. We remove the first node, node 9, from the queue and set it to current.

5. Apply any necessary logic then push all of node 9’s children into the queue (node 7 and node 8).

6. Continue repeating this process until the queue is empty and all nodes have been visited.