CS 231: Data Structures and Algorithms (Lab Page)

Title image Lab 7
Fall 2016

Binary Search Trees as Maps

The goal of this lab period is to give you an opportunity to implement a map with a binary search tree.


  1. Make a new folder for this week's project.
  2. MyMap - download MyMap.java. Open it and read it. Notice that it is a generic interface that requires two types - a type associated with keys and a type associated with values.
  3. KeyValuePair - create KeyValuePair<Key,Value> class (to be used by the binary search tree). Is supports a generic type for the key (K) and a generic type for the value (V) and should have fields to contain a key and a value and implement the following methods:
    • public KeyValuePair( Key k, Value v ) - constructor.
    • public Key getKey()> - return the key
    • public Value getValue() - return the value
    • public void setValue( Value v ) - set the value
    • public String toString() - return a String containing both the key and value.

    Test your class. Make sure it is in perfect working order.

  4. BSTMap - create a BSTMap (Binary Search Tree Map) class. In BSTMap.java, you will need at least 3 classes - the main tree class (BSTMap), a the tree node class (TreeNode, which can go after it, rather than being nested), and a comparator for Keys (AscendingStringComparator, which works only for Strings and also shouldn't be nested). Below is a template you can use for the BSTMap, TreeNode, and AscendingStringComparator classes:
    public class BSTMap<K,V> implements MyMap<K,V> {
        private TreeNode<K,V> root;
        private Comparator<K> comparator;
        public BSTMap( Comparator<K> comparator ) {
            this.comparator = comparator;
            // WARNING: THIS CODE IS INCOMPLETE. You still need to initialize the root.
            // and code that initializes root
        public void put( K key, V value ) {
            // Call the TreeNode's put method. It will need the comparator passed in to it.
        public static void main( String[] args ) {
            System.out.println( "test code" );
            BSTMap<String,Integer> map = new BSTMap<String,Integer>(new AscendingStringComparator());
            map.put( "B", 2 );
            map.put( "A", 1);
            map.put( "D", 2 );
            map.put( "C", 2 );
            System.out.println( "Has A: " + map.containsKey( "A" ) );
            System.out.println( "Has G: " + map.containsKey( "G" ) );
            map.put( "D", 3 );
            System.out.println( "D now has value " + map.get( "D" ) );
            System.out.println( "The tree has " + map.size() + " elements" );
            System.out.println( "The tree has " + map.depth() + " levels" );
            ArrayList<KeyValuePair<String,Integer>> pairs  = map.getPairs();
            System.out.println( "In useful order: " );
            System.out.println( pairs );
    class TreeNode<Key,Value> {
        private KeyValuePair<Key,Value> pair;
        private TreeNode<Key,Value> left;
        private TreeNode<Key,Value> right;
        public TreeNode( Key this_key, Value this_val, TreeNode<Key,Value> l, TreeNode<Key,Value> r ) {
            ; // code here
      // Methods to support insert, contains, printing, getPairs, etc.
    } // end class TreeNode
    class AscendingStringComparator implements Comparator<String> {
        public int compare( String i1, String i2 ) {
            // returns negative number if i2 comes after i1 lexicographically
            return i1.compareTo(i2);

    Implement the methods required to support the MyMap interface. You will probably also want to add code to print the tree, for debugging purposes. It would also be a good idea to implement as few methods as you can at a time, so you can test as you go (just make stubs for the yet-to-be implemented methods). (Note: A stub is a temporary version of a function that doesn't really do anything but which compiles.)

    One of the more complicated aspects of the generic binary search tree is that it requires a comparator. It will use that comparator to add new pairs to the tree as well as to search the tree. The pair comparator itself needs to store and use a comparator for just the tree types.

    Another plan that you should know about right now is that we are designing the tree so that is it easy to reconstruct it. Once we get to the project, we will be constructing a relatively small tree from a very large data set. We will want to look at the tree for a particular data set multiple times. The most efficient way to do this will be to write a file containing the tree data, then read it in, adding the elements to the tree one at a time (instead of re-reading the original data set). The order in which we add these elements matters. If we add them in sorted order, what will the tree look like? However, if we add them in the order we get from a pre-order traversal, then reconstructing the tree by adding the elements one at a time will work beautifully. This means

    public ArrayList<KeyValuePair<K,V>> getPairs();

    should return a list of pairs from a pre-order traversal.

    Test your code thoroughly and make sure it is in perfect working order. In particular, make sure your getPairs method returns the pairs in pre-order.

Once you have completed the lab, go on to the project.