Starter Code:

Do not modify or submit this file! import java.util.Set; // Based on java.util.AbstractMap public interface SimplerMap, V> { public void clear(); public boolean containsKey(K key); public V get(K key); public boolean isEmpty(); public V put(K key, V value); public int size(); }

Do not modify or submit this file!

import java.util.Map; import java.util.Set; public interface SimplerMapExtraCredit, V> { public Set keySet(); public void putAll(Map extends K, ? extends V> builtinMap); }

This is the file that you should modify.

import java.util.Map; import java.util.Set; import java.util.TreeSet; public class UnbalancedMap, V> implements SimplerMap { Node root; public static class Node, V> { public K key; public V value; public Node left, right; public Node(K key, V value) { this.key = key; this.value = value; } boolean containsKey(K key) { int cmp = key.compareTo(this.key); if (cmp == 0) { return true; } else if (cmp  0) { return right != null && right.containsKey(key); } } V get(K key) { return null; // TODO } V put(K key, V value) { return null; // TODO } int size() { return -1; // TODO } // // Extra Credit // // Set keySet() { // Set keys = new TreeSet(); // // TODO // return keys; // } } @Override public void clear() { root = null; } @Override public boolean containsKey(K key) { return root == null ? false : root.containsKey(key); } @Override public V get(K key) { return null; // TODO } @Override public boolean isEmpty() { return root == null; } @Override public V put(K key, V value) { if (root == null) { root = new Node(key, value); return value; } else { return root.put(key, value); } } @Override public int size() { return -12345; // TODO } // // Extra Credit // // @Override // public Set keySet() { // return root.keySet(); // } // @Override // public void putAll(Map extends K, ? extends V> builtinMap) { // // TODO // } @Override public String toString() { return root == null ? "" : root.toString(); } }

Description Maps are useful for any application where you want to look up some data based on some other piece of data and you have enough memory to fit all of the data. For example, you might want to look up an email based on a name or the number of times a word appeared in a book. In this assignment, you'll implement an unbalanced binary search tree that behaves similar to a javautil.TreeMap You may add methods and members to UnbalancedMap but do not remove any. All of the Node methods containsKey, get, put, and size) should be implemented using recursion