Tree searching

One of the best ways to search hierarchical data is to create a search tree. In Chapter 6, Understanding and Implementing Trees, we saw how to construct a binary search tree and increase the efficiency in searching. We have also discovered different ways to traverse a tree. Now, we will explore the two most popular ways of searching a tree structure commonly known as breadth first search (BFS) and depth first search (DFS).

Breadth first search

In a tree structure, a root is connected to its child node, and each child node can be represented as a tree. We have already seen this in Chapter 6, Understanding and Implementing Trees. In a breadth first search, popularly known as BFS, we start from a node (mostly root node) and first visit all adjacent or neighbor nodes before visiting the other neighbor nodes. In other words, we have to move level by level while we are applying BFS. As we search level by level, this technique is known as breadth first search. In the following tree...