# Lab 07: BSTMap

[Prerequisites](/cs61b-fall-2022/prerequisites-to-running-the-assignments..md) to running the code.

Instructions: <https://fa22.datastructur.es/materials/lab/lab07/>

Solution: <https://github.com/tomthestrom/cs61b/tree/master/lab07>

The title says it all, I implemented a BSTMap in line with the specs and conventions - for every node X in the tree the following was true:

* every key in the left subtree was less than X's key
* every key in the right subtree was greater than X's key&#x20;

## BSTMap - Instructions

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 `BSTMap.java`. 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`.

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!

In your implementation you should assume that generic keys `K` in `BSTMap<K,V>` extend [Comparable](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Comparable.html).

## Implementation

#### About

The `BSTMap` is made of `BSTNode` instances that store `key`, `value` pairs. `BSTNode` is a nested class of `BSTMap`. Since the `key` of `BSTNode` is a `Comparable`, I used its compareTo method to determine where it belongs within the tree.

#### Code

```java
import java.util.Iterator;
import java.util.Set;

/**
 * Implements a BSTMap as specified by MAP61B interface
 * Core data structure is a binary search tree
 */
public class BSTMap<K extends Comparable, V> implements Map61B<K, V> {
    /**
     * The root of the tree
     */
    private BSTNode<K, V> root;

    /**
     * The nr of nodes in the tree
     */
    private int size;

    /**
     * Represents a node within the BST
     */
    private static class BSTNode<K extends Comparable, V> {
        /**
         * The key of the node
         */
        public K key;
        /**
         * The value of the node
         */
        public V value;

        /**
         * Reference to the left child
         */
        public BSTNode<K, V> left;
        /**
         * Reference to the right child
         */
        public BSTNode<K, V> right;

        public BSTNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * Removes all items from the BST
     */
    @Override
    public void clear() {
        root = null;
        size = 0;
    }

    /**
     * Returns true if the BST contains the requested key
     */
    @Override
    public boolean containsKey(K key) {
        return containsKeyHelper(root, key);
    }

    /**
     * Recursively traverses the tree in search of the requested key, returns
     * true if found, false otherwise
     */
    private boolean containsKeyHelper(BSTNode node, K key) {
        if (node == null) {
            return false;
        }

        if (node.key.compareTo(key) == 0) {
            return true;
        }

        boolean searchLeft = node.key.compareTo(key) > 0;

        if (searchLeft) {
            return containsKeyHelper(node.left, key);
        } else {
            return containsKeyHelper(node.right, key);
        }
    }

    /**
     * Returns the value to which the specified key is mapped, or null if this
     * map contains no mapping for the key.
     */
    @Override
    public V get(K key) {
        return getHelper(root, key);
    }

    /**
     * Recursively traverses the tree in search of the requested key, returns its value
     */
    private V getHelper(BSTNode node, K key) {
        if (node == null) {
            return null;
        }

        if (node.key.compareTo(key) == 0) {
            return (V) node.value;
        }

        boolean searchLeft = node.key.compareTo(key) > 0;

        if (searchLeft) {
            return getHelper(node.left, key);
        } else {
            return getHelper(node.right, key);
        }

    }

    /**
     * Returns the nr. of stored items
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Stores a key value pair
     */
    @Override
    public void put(K key, V value) {
        root = putHelper(root, key, value);
    }

    /**
     * Recursively traverses the nodes comparing the keys to find out where to insert the key, value pair
     */
    private BSTNode<K, V> putHelper(BSTNode<K, V> node, K key, V value) {
        if (node == null) {
            size++;
            return new BSTNode<>(key, value);
        }

        //in case the key already exists, we just assing a new value
        boolean insertHere = node.key.compareTo(key) == 0;

        if (insertHere) {
           node.value = value;
           return node;
        }

        boolean insertLeft = node.key.compareTo(key) > 0;

        if (insertLeft) {
            node.left = putHelper(node.left, key, value);
        } else {
            node.right = putHelper(node.right, key, value);
        }

        return node;
    }

    /**
     * Prints out the BSTMap in order of increasing Key
     */
    public void printInOrder() {
        printInOrderHelper(root);
        System.out.println();
    }

    /**
     * Recursively traverses the tree and prints its items
     * visiting the smallest (left) values first before printing the current value and
     * visitng the largerst (right) values
     */
    private void printInOrderHelper(BSTNode<K, V> node) {
        if (node == null) {
            return;
        }
        printInOrderHelper(node.left);
        System.out.print(node.key);
        printInOrderHelper(node.right);
    }

    /*
     * Unsupported Methods:
     * keySet
     * remove(key)
     * remove(key, value)
     * iterator()
     */

    @Override
    public Set<K> keySet() {
        throw new UnsupportedOperationException();
    }

    @Override
    public V remove(K key) {
        throw new UnsupportedOperationException();
    }

    @Override
    public V remove(K key, V value) {
        throw new UnsupportedOperationException();
    }

    @Override
    public Iterator<K> iterator() {
        throw new UnsupportedOperationException();
    }
}
```

## So ... How Fast Is It? <a href="#so-how-fast-is-it" id="so-how-fast-is-it"></a>

#### About

[Insert random speed test](#insertrandomspeedtest) - my implementation of BSTMap holds up pretty well against Java's built-in data structures.

[Insert in order test](#insertinorderspeedtest) - my implementation is significantly slower than Java's built-in data structures and results in a stackoverflow at 50 000 inserts, I suppose the issue is with the fact that the tree is not self-balancing, so in case every new key is larger than the previous one, the tree is spindly and not a tree, but a linked list instead.

#### InsertRandomSpeedTest:

```

Please enter desired length of each string: 128

Enter # strings to insert into the maps: 1000
class bstmap.ULLMap: 0.01 sec
class bstmap.BSTMap: 0.00 sec
Java's Built-in TreeMap: 0.00 sec
Java's Built-in HashMap: 0.00 sec

Enter # strings to insert into the maps: 100000
--Stack Overflow -- couldn't add 100000 strings of length 128.
class bstmap.BSTMap: 0.20 sec
Java's Built-in TreeMap: 0.16 sec
Java's Built-in HashMap: 0.13 sec

Enter # strings to insert into the maps: 1000000
--Stack Overflow -- couldn't add 1000000 strings of length 128.
class bstmap.BSTMap: 2.00 sec
Java's Built-in TreeMap: 1.97 sec
Java's Built-in HashMap: 1.49 sec

Enter # strings to insert into the maps: 10000000
--Stack Overflow -- couldn't add 10000000 strings of length 128.
class bstmap.BSTMap: 26.70 sec
Java's Built-in TreeMap: 23.35 sec
Java's Built-in HashMap: 15.26 sec
```

#### InsertInOrderSpeedTest

```
Enter # strings to insert into the maps: 1000
class bstmap.ULLMap: 0.02 sec
class bstmap.BSTMap: 0.01 sec
Java's Built-in TreeMap: 0.00 sec
Java's Built-in HashMap: 0.00 sec

Enter # strings to insert into the maps: 10000
class bstmap.ULLMap: 0.76 sec
class bstmap.BSTMap: 0.80 sec
Java's Built-in TreeMap: 0.00 sec
Java's Built-in HashMap: 0.00 sec

Enter # strings to insert into the maps: 20000
class bstmap.ULLMap: 3.21 sec
class bstmap.BSTMap: 2.28 sec
Java's Built-in TreeMap: 0.01 sec
Java's Built-in HashMap: 0.00 sec

Enter # strings to insert into the maps: 50000
--Stack Overflow -- couldn't add 50000 strings.
--Stack Overflow -- couldn't add 50000 strings.
Java's Built-in TreeMap: 0.01 sec
Java's Built-in HashMap: 0.02 sec
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://tomthestrom.gitbook.io/cs61b-fall-2022/lab-07-bstmap.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.