Traversal Methods

Now that we can create a binary search tree by inserting nodes, the next step is to implement methods that can traverse the BST. Feel free to refer back to the Warmup 1 for a reminder of how the different traversals work on a given BST.

Traversal Methods

For our traversals, instead of printing out each item, we will instead save each item to a List when we “visit” a node. Thus, your traversal methods will take as a single parameter a List and you will add a node’s item when we visit the node in the traversal. None of the three methods will need to return anything since the List argument is modified by the methods (and those changes remain outside of the method calls).

You should implement the following traversals:

  1. A pre-order traversal in a public method called preOrder
  2. An in-order traversal in a public method called inOrder
  3. A post-order traversal in a public method called postOrder

If we start with an empty List and pass it into the preOrder method called on the root node, then the list will contain the items in an order such that they can be inserted to recreate an identical BST. If we instead pass an empty list into the inOrder method, we will instead fill a list with the items in sorted order.

Testing Our Traversal Methods

You should create unit tests for each of our traversal methods to verify that they are working correctly.

Hint

As a suggestion, you could first create the example tree we used throughtout our lectures:

then check whether your traversal methods save the items in the following orders:

  • pre-order traversal: 151, 150, 241, 210, 275, 280
  • in-order traversal: 150, 151, 210, 241, 275, 280
  • post-order traversal: 150, 210, 280, 275, 241, 151

To create the example tree, you can insert them in the same order that they are listed in the pre-order traversal.

Committing Your Progress

Don’t forget to frequently save your progress to GitHub using the add/commit/push commands with git.