Breadth First Search

Breadth first search is a common technique to search a tree data structure. As in the name, this algorithm traverses the tree shallow before going deeper. A tree usually consists of nodes or vertices that hold a value as well as point to other values, which links these items together in a tree like structure.

Let’s look at some pseudocode for how to implement the algorithm, this uses key value pairs to keep track of visited nodes and a queue to keep track of the next nodes to visit:

  1. Pick a node to start with and add it to the queue

There, now we have visited every node in a tree. Notice that in step 4 we recursively call the method with the base case of the queue being empty. We have done this by going breadth first.

How does Breadth First Search(BFS) compare to Depth First Search(DFS)?

  • BFS is faster when the node you are looking for is closer to the node you start on



Software Engineer

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