6.2.4 Depth vs Breadth Search
When searching or traversing through a data structure, or in this case a list of letters, there are multiple ways to systematically traverse. In this example, you are going to look at comparing these two different searches. You will have a chance to explore these more in future lessons as well.
Depth First Search
As the name suggests, a depth-first search is one where you explore deep before you explore across. In other words, if you were to look at a tree structure, you would essentially search down the left side as far as you could go, then back up one spot and search as far down as you could go.
Here is an example of how a depth first search may look.
Notice in the example that the traversal goes to the bottom, then works its way across.
In the last example, the permutations were generated in a depth-first manner by selecting all of the A combination, then moving on to the B combination, etc.
Breadth First Search
In contrast, a breadth-first search is completed by working all the way across at one level. Only once that level is completed does the search move deeper.
Notice how the order is different. While not as pronounced with only 3 levels, you can still see how the search goes across each level before moving deeper.
Explore the Example
Take time to explore this example. The results from this example are the same as the last example, but since the function is initially set up to execute a breadth-first search, the results will print in a different order.
You can easily compare this back to the previous example by toggling the comments on and off on lines 16 and 25.
Last updated