Binary Search Tree

Description:

• You may not use any iteration statement (e.g., for, while, do-while) during the implementation of BinarySearchTree class methods.
• You may not modify the Node class we provided.
• You may not add any instance nor static variables to the BinarySearchTree class.
• You can use at most one auxiliary method during the implementation of a recursive method.
• The size() method must not traverse the tree nor should it use an auxiliary that updates the treeSize instance variable. The treeSize instance variable will be updated as add and delete operations are performed.
• The implementation of the subTree() method must be efficient. A subtree of the original tree (current object) should not be traversed if it is not necessary. For example, given a tree with a root key of 50, and a range request of lowerLimit (60) and upperLimit (100), your code must not traverse the left subtree. If to create the subtree, you traverse the whole tree selecting to add to the subtree entries in the range. The subtree can be of any shape.

BinarySearchTree Class

public class BinarySearchTree< K, V > {
/*
* You may not modify the Node class and may not add any instance nor static
* variables to the BinarySearchTree class.
*/
private class Node {
private K key;
private V value;
private Node left, right;
private Node(K key, V value) {
this.key = key;
this.value = value; } }
private Node root;
private int treeSize, maxEntries;
private Comparator< K > comparator;
/*Initializes the instance variables using the parameter values. Sets the treeSize to zero. An empty tree is one with the root value set to null.*/
public BinarySearchTree(Comparator< K > comparator, int maxEntries) {
throw new UnsupportedOperationException("Implement this method");
}
/*Adds the specify key value pair to the binary search tree. If the key already exists in the tree, the value associated with the key will be updated. Adding a new entry increases the treeSize by one. Updating an existing key/value, does not increase the size.*/
public BinarySearchTree< K, V > add(K key, V value) throws TreeIsFullException {
throw new UnsupportedOperationException("Implement this method");
}
/*Returns a string with the key/value pairs of the tree in increasing sorted order (according to the comparator). Each key/value pair will be printed using the format {key:value}. For example, a tree with two entries will appear as {Al:10}{Bob:60}. If the tree is empty the "EMPTY TREE" string will be returned.*/
public String toString() {
throw new UnsupportedOperationException("Implement this method");
}
public boolean isEmpty() {
return root == null; }
public int size() {
return treeSize; }
public boolean isFull() {
return treeSize == maxEntries; }
/*Returns a KeyValuePair with a copy (shallow) of the tree entry with the minimum key value.*/
public KeyValuePair< K, V > getMinimumKeyValue() throws TreeIsEmptyException {
throw new UnsupportedOperationException("Implement this method");
}
/*Returns a KeyValuePair with a copy (shallow) of the tree entry with the maximum key value.*/
public KeyValuePair< K, V > getMaximumKeyValue() throws TreeIsEmptyException {
throw new UnsupportedOperationException("Implement this method");
}
/*Returns a KeyValuePair with a copy (shallow) of the tree entry with the specified key parameter or null if no entry with that key exists.*/
public KeyValuePair< K, V > find(K key) {
throw new UnsupportedOperationException("Implement this method");
}
/*Deletes from the key the entry with the specified key value (if present). For replacement of an interior/root node you can use either the maximum from the left subtree or the minimum from the right subtree. Removing an entry from the tree decreases the treeSize by one.*/
public BinarySearchTree< K, V > delete(K key) throws TreeIsEmptyException {
throw new UnsupportedOperationException("Implement this method");
}
/*This method will perform an inorder traversal of the tree, and will call the process method (of the provided callback) on each node. The callback defines the task that will be perform on the node.*/
public void processInorder(Callback< K, V > callback) {
throw new UnsupportedOperationException("Implement this method");
}
/*Returns a new BinarySearchTree with copies (shallow) of key/value pairs of entries that have a key value in the range lowerLimit (inclusive) and upperLimit (inclusive). The implementation of this method must be efficient, otherwise you will not get credit for its implementation. A subtree of the original tree (current object) should not be traversed if it is not necessary. For example, given a tree with a root key of 50, and a range request of lowerLimit (60) and upperLimit (100), your code must not traverse the left subtree. If to create the subtree, you traverse the whole tree selecting to add to the subtree entries in the range, then you will not get credit for this method. The subtree can be of any shape.*/
public BinarySearchTree< K, V > subTree(K lowerLimit, K upperLimit) {
throw new UnsupportedOperationException("Implement this method");
}
/*Returns a TreeSet with the values (not the keys) of leaf nodes. An empty TreeSet will be returned if the tree is empty.*/
public TreeSet< V > getLeavesValues() {
throw new UnsupportedOperationException("Implement this method");
}}

CallBack Class

public interface Callback< K, V > {
public void process(K key, V value); }

GetDataIntoArrays Class

public class GetDataIntoArrays< K, V > implements Callback< K, V > {
private ArrayList< K > keys;
private ArrayList< V > values;
public GetDataIntoArrays() {
keys = new ArrayList< K >();
values = new ArrayList< V >(); }
public void process(K key, V value) {
keys.add(key);
values.add(value); }
public ArrayList< K > getKeys() {
return new ArrayList< K >(keys); }
public ArrayList< V > getValues() {
return new ArrayList< V >(values); }}

KeyValuePair Class

public class KeyValuePair< K, V > {
private K key;
private V value;
public KeyValuePair(K key, V value) {
this.key = key;
this.value = value; }
public K getKey() {
return key; }
public V getValue() {
return value;
}}

TreeIsEmptyException Class

public class TreeIsEmptyException extends Exception {
private static final long serialVersionUID = 1L;
public TreeIsEmptyException(String message) {
super(message); }}

TreeIsFullException Class

public class TreeIsFullException extends Exception {
private static final long serialVersionUID = 1L;
public TreeIsFullException(String message) {
super(message); } }

SampleDriver Class

public class SampleDriver {
public static void main(String[] args) {
System.out.println("======== Marker #1 ========");
Comparator< String > comparator = String.CASE_INSENSITIVE_ORDER;
int maxEntries = 10;
BinarySearchTree< String, Integer > bst = new BinarySearchTree< String, Integer >(comparator, maxEntries);
System.out.println(bst);
System.out.println("Empty Tree?: " + bst.isEmpty());
System.out.println("\n======== Marker #2 ========");
try {
bst.add("Oliver", 1000).add("Arlene", 50000).add("Terry", 60);
} catch (TreeIsFullException e) {
System.out.println("full tree");
}
System.out.println(bst);
System.out.println("Full Tree?: " + bst.isFull());
System.out.println("Size: " + bst.size());
System.out.println("\n======== Marker #3 ========");
try {
KeyValuePair< String, Integer > maximum = bst.getMaximumKeyValue();
KeyValuePair< String, Integer > minimum = bst.getMinimumKeyValue();
System.out.println("Maximum: " + maximum.getKey() + "/" + maximum.getValue());
System.out.println("Minimum: " + minimum.getKey() + "/" + minimum.getValue());
} catch (TreeIsEmptyException e) {
System.out.println("empty tree");
}
System.out.println("\n======== Marker #4 ========");
KeyValuePair< String, Integer > found = bst.find("Terry");
System.out.println(found == null ? "NOT FOUND" : found.getKey() + "/" + found.getValue()); System.out.println("\n======== Marker #5 ========");
GetDataIntoArrays< String, Integer > callback = new GetDataIntoArrays< String, Integer >();
bst.processInorder(callback);
System.out.println("Keys: " + callback.getKeys());
System.out.println("Values: " + callback.getValues()); System.out.println("\n======== Marker #6 ========");
BinarySearchTree< String, Integer > subTree = bst.subTree("Oliver", "Tracy");
System.out.println("Tree: " + bst);
System.out.println("SubTree: " + subTree);
System.out.println("\n======== Marker #7 ========");
TreeSet< Integer > leavesValuesSet = bst.getLeavesValues();
System.out.println(leavesValuesSet);
System.out.println("\n======== Marker #8 ========");
try {
bst.delete("Terry");
} catch (TreeIsEmptyException e) {
System.out.println("empty tree");
}
System.out.println(bst);
}
}

Output

======== Marker #1 ========
EMPTY TREE
Empty Tree?: true
======== Marker #2 ========
{Arlene:50000}{Oliver:1000}{Terry:60}
Full Tree?: false
Size: 3
======== Marker #3 ========
Maximum: Terry/60
Minimum: Arlene/50000
======== Marker #4 ========
Terry/60
======== Marker #5 ========
Keys: [Arlene, Oliver, Terry]
Values: [50000, 1000, 60]
======== Marker #6 ========
Tree: {Arlene:50000}{Oliver:1000}{Terry:60}
SubTree: {Oliver:1000}{Terry:60}
======== Marker #7 ========
[60, 50000]
======== Marker #8 ========
{Arlene:50000}{Oliver:1000}