Lab 7: TreeMap


In this lab, you’ll create BSTMap, a BST-based implementation of the Map61B interface, which represents a basic tree-based map. You will be creating this completely from scratch, using the interface provided as your guide.

After you’ve completed your implementation, you’ll compare the performance of your implementation to a list-based Map implementation ULLMap as well as the built-in Java TreeMap class (which also uses a BST).


Create a class BSTMap that implements the Map61B interface using a BST (Binary Search Tree) as its core data structure. You must do this in a file named Your implementation is required to implement all of the methods given in Map61B except for remove, iterator and keyset. For these methods you should throw an UnsupportedOperationException.

When declaring your class, you need to specify that your BSTMap will only work with keys that can be compared. The syntax for this in Java is a little weird, so we’ll just give it away:

public class BSTMap<K extends Comparable<K>, V> implements Map61B<K, V>

What this does is ensure that the generic keys K in BSTMap<K,V> extend Comparable.

The following resources might prove useful:

Your BSTMap should also add an additional method printInOrder() (not given in the Map61B interface) that prints out your BSTMap in order of increasing Key. We will not test the result of this method, but you will find this helpful for testing your implementation!

You can test your implementation using

So… How Fast Is It?

There are two interactive speed tests provided in and Do not attempt to run these tests before you’ve completed BSTMap. Once you’re ready, you can run the tests in IntelliJ.

The InsertRandomSpeedTest class performs tests on element-insertion speed of your BSTMap, ULLMap (provided), Java’s built-in TreeMap, and Java’s built-in HashMap (which you’ll explore more in the next lab). It works by asking the user for a desired length of each String to insert, and also for an input size (the number of insertions to perform). It then generates that many Strings of length as specified and inserts them into the maps as <String,Integer> pairs.

Try it out and see how your data structure scales with the number of insertions compared to the naive and industrial-strength implementations. Remember that asympototics aren’t representative on small samples, so make sure your inputs are sufficiently large if you are getting a confusing trend. Record your results in a file named speedTestResults.txt. There is no standard format required for your results, and there is no required number of data points.

Now try running InsertInOrderSpeedTest, which behaves similarly to InsertRandomSpeedTest, except this time the Strings in <String, Integer> key-value pairs are inserted in lexicographically-increasing order. If you observed anything interesting (hopefully you did), you should discuss it with your fellow students and/or TA.

Optional Exercises

This will not be graded, but you can still receive feedback on the autograder.

Implement the methods iterator(), keySet(), remove(K key), and remove(K key, V value), in your BSTMap class. Implementing remove() is fairly challenging. For an extra challenge implement keySet() and iterator without using a second instance variable to store the set of keys.

For remove, you should return null if the argument key does not exist in the BSTMap. Otherwise, delete the key-value pair (key, value) and return value.

Lab Debrief and Submission

At the end of lab, your TA will go over the reference solution. This will be helpful if you haven’t finished the lab, since we don’t want you to be stuck working on lab too much outside of lab. (This is also an incentive for you to go to lab!)

Make sure to submit your completed and speedTestResults.txt, and submit through git and Gradescope as usual.

Optional Asymptotics Problems

Given B, a BSTMap with N key-value pairs, and (K, V), a random key-value pair, answer the following questions.

Unless otherwise stated, “big-Oh” bounds (e.g. O(N)) and “big-Theta” bounds (e.g. Θ(N)) refer to the number of comparisons in the given method call(s).

For questions 1-7, state whether the statement is true or false. For question 8, give a runtime bound.

  1. B.put(K, V) ∈ O(log(N)).
  2. B.put(K, V) ∈ Θ(log(N)).
  3. B.put(K, V) ∈ Θ(N).
  4. B.put(K, V) ∈ O(N).
  5. B.put(K, V) ∈ O(N2).
  6. On average, the total number of comparisons to complete N random calls to B.put(K, V) followed by B.containsKey(K) ∈ ~2(ln(N))

     Note: We write g(N)~f(N) to represent that ~g(N)/f(N) -> 1 as N gets large.
  7. For key C != K, running both B.containsKey(K) and B.containsKey(C) ∈ Ω(log(N)).
  8. Let BSTMap b be comprised of a root Node (Key, Value pair) and two BSTMap subtrees called left and right. Further, assume the method numberOfNodes(BSTMap b) returns the number of nodes of a BSTMap rooted in b.root and has a running time of Θ(n), where n is the number of Nodes in the BSTMap rooted in b. What is the running time (in big O notation) of mystery(b, z) for some positive integer z? Give the tightest bound you can assuming b has N nodes. Your answer should not contain any unnecessary multiplicative constants or additive factors.

     public Key mystery(BSTMap b, int z) {
         if (z > numberOfNodes(b) || z <= 0)
             return null;
         if (numberOfNodes(b.left) == z-1)
             return b.root.key;
         else if (numberOfNodes(b.left) > z)
             return mystery(b.left, z);
             return mystery(b.right, z-numberOfNodes(b.left) - 1);