1 Overview

This assignment asks you to implement the Map ADT using a binary search tree (BST). Even though we are learning about self-balancing BSTs this week, for this HW you should just create a “vanilla” BST that may be unbalanced or not, depending on the insertion order.

2 Implementing the Map interface

You’ll need these files to get started:

• Map.java
• BSTMap.java

You can get all these files at once by downloading the file hw05.tar.gz and running tar xzvf hw05.tar.gz

You need to complete the BSTJava class so that it correctly implements the methods of the Map interface. Those are the same as the usual Map ADT methods (see the Unit 5 notes), plus an additional traverse() method to do an in-order traversal of the BST.

The Javadoc for the Map interface methods is here.

Now that you’ve implemented stacks and queues yourself, we get to use the built-in ones inside java.util. And in fact Java has just one interface Deque, which encompasses both a stack and a queue. For the traverse() method in your BSTMap, you will need to return the keys in order in a Deque object. The built-in Deque implementations in java.util are ArrayDeque  and LinkedList. Feel free to use either one here - just be sure you add the BST keys in order to the back of the deque.

IMPORTANT: You will need to add an import line for the Deque implementation you choose from java.util. Do not do import java.util.* because that will make java get confused between the standard Map interface and the simplified one we are using for this HW. Just import the specific class that you are using. (And of course, you shouldn’t import anything else from java.util like TreeMap - that is what we are asking you to implement here!

Your notes from class for Unit 4 will be helpful in implementing the BST methods, but keep in mind for this HW your implementation needs to be generic (not restricted to integers or Strings) and your BST nodes need to hold both keys and values (not just keys).

3 Big-O Requirements

Your methods must satisfy the following worst-case running times:

Method	Runtime
get(K)	O(height)
containsKey(K)	O(height)
put(K,V)	O(height)
remove(K)	O(height)
size()	O(1)
traverse()	O(n)

4 Do remove last!

Writing the remove() method will be the hardest, so you should do that last after everything else is completed, tested, and working perfectly.

Here is the grading breakdown for this HW:

• Up to 90%: Implement all Map methods except remove perfectly using an ordinary (not self-balancing) binary search tree data structure.
• Up to 105% (A++): Implement all methods perfectly including remove.

5 Tips

To implement the BST methods which are not \(O(1)\), you will probably want to use some recursion. Here are a few helpful tips to remember:

• Recursion on binary trees follows exactly the same principles as recursion on linked lists, except that each Node has not just a single next node, but instead two subtrees left and right.

• You will usually want to create a helper method which takes an extra Node argument for the “current node”.

• The base case (unless there is some other good reason) is usually when this “current node” is null.

• Methods that always make two recursive calls will usually be O(n) time. Thinking about the order of the recursive calls determines what order the nodes are visited in, corresponding to a pre-order, post-order or in-order traversal.

• Methods that only make at most one recursive call will usually be O(height) time. For BSTs that are generic like the one you will write for this assignment, you have to use the compareTo() method from Java’s Comparable interface. Be sure to check the current node is not null before you try to do the comparison!

• Recursive methods which are trying to find something usually have a return value corresponding to the thing they are finding.

  Recursive methods which are potentially altering the tree are best written to return a Node which is the new root of that subtree.

• Test, test, test — and keep it simple! Remember, part of good data structures programming is thinking about edge cases and getting the details right. It is up to you to test your own code thoroughly before submitting so you are confident it works perfectly.

  There are two sides to this: writing good test cases and keeping your own methods as simple as possible without too many unnecessary if/else cases.