# 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:

- Pick a node to start with and add it to the queue
- Mark the node at the front of the queue as visited
- Take all of this node’s adjacent nodes that aren’t marked visited and add them to the back of the queue
- Repeat steps 2 and 3 until the queue is empty

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
- DFS generally uses less memory than BFS
- DFS us generally faster than BFS
- BFS uses a first-in first-out approach with a queue
- DFS uses a last-in first-out approach with a stack