Breadth First Search vs Depth First Search in a Binary SearchTree

In the previous article I talked about Binary Search Trees (BST). In this article I will discuss two popular methods thats that are used in to traverse a tree or graph these methods are called Breadth First Search (BFS) and Depth First Search (DFS) as they pertain to searching a Binary Search Tree. Both of these methods search the whole tree, but the difference is in how they traverse the tree.

Breadth First Search uses the queue data structure in order to sort through all the nodes. A queue data structure has a first-in-first-out situation , basically like standing in a line, so first node that is analyzed will will be the first one removed from the queue the will. The way these data structures operate is once all the nodes connected to the parent node are fully analyzed they get removed from the queue. This method will start with the parents then search all of the children, then the grandchildren and so on. This method is good for finding the shortest distance between two nodes.

Depth first search uses the stack data structure. This data structure operates on a last-in-last-out, very similar to a stack of books, so if you put a node on the stack it will be removed before all the nodes put into the stack before it. While Breadth First Search typically left to right, Depth First Search searches up and down. Once you start down a path DFS will keep going until it finds a a childless node (leaf node).