Let’s Learn Searching: A basic overview of BFS and DFS
To me, searching algorithms have seemed like the holy grail of my technical interview practice: mysterious, coveted, yet ultimately out of reach. Until today.
For my first foray into searching, I’ve going to give a very basic overview of two prominent searching algorithms: Breadth First Search (BFS) and Depth First Search (DFS). Questions about these two algorithms come up frequently during technical interviews and so understanding the basics of how they work might very well help you to land your first programming job!
Breadth First Search
Breadth first search works by starting at the root node and then moving left to right across the second level, then left to right across the third, etc. until it finds the correct node.
Depth First Search
In contrast to its cousin algorithm, depth first search works by following one branch of a tree/graph down as many levels as possible until it either finds the correct node or reaches the last node in that branch. DFS will start with the left branch and then move to the right after reaching the deepest depth on the original branch. I find it easier to understand how DFS works by seeing it in action:
As you can see, we start the branch furthest to the left and move down that entire branch before returning to the shared ancestor (1, or our root node in this case) and move right to 5. Then, we move down from 5 on the left until we reach 7 before going back up to another shared ancestor and moving right to 8 and so on.
BFS vs DFS
Now that we have a bit of an understanding on how both of these search algorithms work, you might be wondering when you are supposed to use them. I mean, they seem pretty similar so you should just be able to use them interchangeably right?
While there definitely are times where you would want to use BFS over DFS (and vice versa), the two algorithms to do have some similarities that make deciding when to use them difficult. Most notably, both algorithms have the same runtime complexity of O(n), meaning that you might not save any time running one algorithm over the other. However, they both have some pros and cons to take into account when deciding which to implement.
BFS, for example, uses up significantly more memory than DFS. On the other hand, if a tree/graph is really deep, then DFS can be much slower than BFS. Basically, despite the two algorithms having the same runtime complexity, we should definitely be choosy about when/where to implement each algorithm.
If we know that the node we are looking for is close to the root of tree, then we should use breadth first search. Alternatively, if we know that the node we are looking for is near the bottom of the tree, we should use depth first search.
Ultimately, I hope you that this tutorial has given you a basic understanding of these two common search algorithms. As always, good luck and happy coding!
