This is a solution from the group that worked in the lab. Removing an element is not implemented at this point. The testing code is unchanged.

Binary serach tree code:

```
/**
* Binary search tree stores values indexed by keys. Keys must be Comparable and
* are organized based on their natural ordering (i.e. the ordering given by
* their compareTo). Values can be of any object type. This tree implementation
* is not balanced, i.e. it may behave as a linked list in the worst case. Keys
* may be repeated. Somewhat modeled after Map<K,V> classes in the Java
* Collections Framework
*
* Author: Elena Machkasova For UMM CSci 2101 class (version for Summer 2011).
**/
public class BinarySearchTree<K extends Comparable<K>, V> {
private BSTNode root = null;
private int count = 0;
/**
* @return true if the tree is empty, false otherwise
**/
public boolean isEmpty() {
return root == null;
}
/**
* @return the number of elements in the tree
**/
public int size() {
return count;
}
/**
* Adds a given value indexed with a given key to the tree according to the
* binary search structure
*
* @param key
* - the key of the given element
* @param value
* - the value of the given element
*/
public void put(K key, V value) {
BSTNode parentnode = root;
BSTNode toAdd = new BSTNode(key,value);
if(isEmpty()){
root = toAdd;
count++;
}else{
recursive(parentnode, toAdd);
count++;
}
}
private void recursive(BSTNode parentNode, BSTNode addedNode){
if(addedNode.key.compareTo(parentNode.key)<0){
if(parentNode.left == null){
//return parentNode;
parentNode.left = addedNode;
}
else{
recursive(parentNode.left,addedNode);
}
}
else {
if(parentNode.right == null){
//return parentNode;
parentNode.right = addedNode;
}
else{
recursive(parentNode.right,addedNode);
}
}
}
/**
* returns a value associated with the given key in this binary search tree.
* If multiple values are associated with this key, any one may be returned.
* If there is no element associated with this key, null is returned.
*
* @param key
* - the key to search for.
* @return - a value to which the specified key is mapped, or null if this
* tree contains no mapping for the key
* @throws NullPointerException if the key is null
*/
public V get(K key) {
BSTNode current = root;
if(isEmpty()){
return null;
}
BSTNode aNode = recursiveGet(current, key);
if(aNode==null){
return null;
}
return aNode.value;
}
private BSTNode recursiveGet(BSTNode theNode, K key){
if(theNode.key.compareTo(key)==0){
return theNode;
}
if(theNode.key.compareTo(key)>0){
if(theNode.left==null){
return null;
}
return recursiveGet(theNode.left, key);
}else {
if(theNode.right==null){
return null;
}
return recursiveGet(theNode.right, key);
}
}
/**
* Removes an element with the given key. The resulting tree is a binary
* search tree. If there is no such key, the tree is unchanged. If there are
* multiple values associated with this key, only one is removed. Returns
* the value associated with this key or null if there is no such value.
*
* @param key
* - the key
* @return - a value to which the specified key is mapped, or null if this
* tree contains no mapping for the key
* @throws NullPointerException if the key is null
*/
public V remove(K key) {
count--; //change later =]
return null;
}
/**
* Clears all elements from a given tree.
* The resulting tree is empty.
*/
public void clear() {
root = null;
count = 0;
}
private class BSTNode {
public K key;
public V value;
public BSTNode left = null;
public BSTNode right = null;
// null key will generate a null pointer exception when
// a method (such as compareTo) is called on it.
// This is fine, according to the JCF specification.
public BSTNode(K key, V value) {
this.key = key;
this.value = value;
}
}
}
```

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.