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
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.
- Recursive implementation for addRecursive(K key, V value)
- Recursive implementation for size()
- Recursive implementation for height()
- Recursive implementation for findRecursive(K key)
- Iterative implementation for find(K key)
- Recursive implementation for printInReverseOrder()
Don't forget...
Start early, ask questions, and have fun!