CS 201: Data Structures

Binary Search Trees

Hand in BST.java. Put all your prose answers in the comment at the top of BST.java.

Work alone or with a partner of your choice.

Goals

• Understand the core operations of binary search trees
• Understand the time complexity of BST operations (with a specific implementation)
• Compare iterative vs. recursive implementations of BST operations

Relevant code

• BST.java. Starter code for you.

Getting to know BST.java

• Read through the existing methods.
• Try creating a three-node BST using the existing command-line structure. Use the two public printing methods to print the resulting tree.
• Study the print() method and talk with each other about how and why it works.

Your tasks

For each of the numbered methods-to-be-coded shown below, do the following:

• Write a short test for the task and put it in a static method "public static void testXYZ()", where "XYZ" is a suitable name for the thing being tested. These tests should mostly go like this:
  • print a title for the test
  • instantiate a BST
  • add some nodes to the BST
  • print what you expect the task's answer should be
  • call the method you're implementing
  • print the method's answer
• If the implementation is recursive, write a brief prose description of the recursion. (We did an example in class--see the class notes.) Put this description in the comment at the top of the BST.java file. [You WILL NOT be graded on this description, as long as you gave it a try—so really, do this before implementing the method.]
• Implement the method. Use your testing code to help you finish.
• If the implementation is recursive, write an updated prose description that better reflects your implementation experience. (Unless your original was perfect, in which case congratulations!) Again, put this description in the comment at the top of the source file. [You WILL be graded on this one.]

Here are the methods to implement. We did the first one in class Wednesday.

1. Recursive implementation for addRecursive(K key, V value)
2. Recursive implementation for size()
3. Recursive implementation for height()
4. Recursive implementation for findRecursive(K key)
5. Iterative implementation for find(K key)
6. Recursive implementation for printInReverseOrder()

Don't forget...

Start early, ask questions, and have fun!