What is Breadth-First Search?

What is Breadth-First Search

When working with Binary Search Tree as a programmer you will be asked or required to traverse through the nodes. One concept you want to have in your arsenal is the “Breadth-First Search” technique. The basic method to this is to start from the root node and add all the additional nodes from the right or left to the queue. Once added to the queue it can be pushed to the final array. This technique is used for finding the shortest path in a graph.

How Does it Work

In order to start this method, we need to work off a Binary Tree. Create a variable and set it equal to the root node. Here’s what it looks like below.

In addition, we will create two more variables and set both to empty arrays. The reason for this as explained earlier we will add the nodes to the queue, which will then be added to the result array. Furthermore, we will start off by pushing the root node to the queue. Here is a clear example below.

In this particular step, we initiate the traversing by looping through the queue. Create a while loop that takes an argument of queue.length. If the queue is empty the loop will not start.

Once the loop is initiated will set the variable we had earlier for the current node to queue.shift, which will remove the node in the queue.

We will add that current node value to the result. Here’s a better example below.

The last steps are to add the conditional for both left and right nodes. If the condition passes it will then be added to the queue. In addition, the last step is to return the final/result array.

Thanks a lot for reading stay tuned for Depth First Search.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store