Objectives

By the end of this chapter you should be able to:

• Compare and contrast three different forms of depth first search
• Compare and contrast depth first and breadth first search
• Implement depth first search
• Implement breadth first search

Now that we have figured out how to insert values into our Binary Search Tree (BST) and find values, what would happen if we wanted to find every single value in the BST? For traversing through all of the nodes in a BST, there are two common algorithms that we use, which enable us to only have to visit each node once. These two algorithms are called Depth First Search (DFS) and Breadth First Search (BFS). They each utilize a secondary data structure (a stack for DFS and a queue for BFS) in order to traverse the tree.

Depth First Search

The algorithm behind depth first search is to search via "depth" and explore each branch of the tree as much as possible. But then the question arises, at which node do we start? Do we start at the root? Do we start at the leftmost node and go upward? Or do we start at the leftmost node and then find the next deepest left node? These distinctions might seem confusing right now, but the difference between them will be clear in a moment. These three approaches to performing depth first search have different names: pre-order, in-order, and post-order.

Pre-order

With pre-order, the algorithm is as follows:

• Start at the root node
• Check the value of the current node; if it has a value, record it
• Recursively call the pre-order function on the subtree to the left of the current node
• Recursively call the pre-order function on the subtree to the right of the current node

In the above example, starting at the root node, we would capture the values in this order: F, B, A, D, C, E, G, I, H.

In-order

With in-order, the algorithm is as follows:

• Start at the root node
• Recursively call the pre-order function on the subtree to the left of the current node
• Check the value of the current node; if it has a value, record it
• Recursively call the pre-order function on the subtree to the right of the current node

In the above example, starting at the root node, we would capture the values in this order: A, B, C, D, E, F, G, H, I. Hence the name: the letters are in order!

Post-order

With post-order, the algorithm is as follows:

• Start at the root node
• Recursively call the pre-order function on the subtree to the left of the current node
• Recursively call the pre-order function on the subtree to the right of the current node
• Check the value of the current node; if it has a value, record it

In the above example, starting at the root node, we would capture the values in this order: A, C, E, D, B, H, I, G, F.

We can see that the implementation of these three kinds of DFS are very similar. The pseudocode is the same, just in a different order! Indeed, once you implement one of these algorithms, you can implement the rest just by changing the order of code!

Breadth First Search

The other alternative to traversing is to search horizontally, or through the "breadth" of the tree. The algorithm is as follows:

• start at the root
• place the root node in a queue
• while there is anything in the queue
  • remove the first element in the queue (dequeue)
    • if what has been dequeued has a left node
      • enqueue the left node
        
    • if what has been dequeued has a right node
      • enqueue the right node
        

In the above example, starting at the root node, we would capture the values in this order: F, B, G, A, D, I, C, E, H.

For more on tree traversal, including references to the traversal images shown here, check out this article.

Exercises

Complete Part II of the exercises here.