Work in groups on this lab.
Your goal is to finish implementation of the binary search tree that we strated in class and write three tree traversals.
Starting with the code we have written in class (including the JUnit
tests), write a method that removes a node with a given key from the
tree. Follow the specification in the given file.
Hints:
You need a special case for removing the root.
For a non-root node you need to keep track of the parent of the node
as you are traversing the tree. You also need to know if the node you
are removing is the left or the right child of its parent.
The easiest way to write any method that traverses the tree is
recursion.
Write methods that perform the following tree traversals: pre-order traversal (Root, Left subtree, Right subtree), post-order traversal (Left subtree, Right subtree, Root), and and reverse in-order traversal (i.e. Right subtree, root, Left subtree). The methods should be recursive and should return a list (such as ArrayList) of Key-Value pairs, similar to the in-order traversal that we will write in class.
Write JUnit tests for your methods, make sure the tests pass, and submit the tests with your code. One of the tests must be for an empty tree.
Below is the class KVPair that is used to store the node
data.
/**
* A class for storing key-value pairs generated during
* traversals of a Binary Search Tree
* mypair.key gives the key, mypair.value gives the value
*
* @author Elena Machkasova
*
* @param <K> - key type (must be comparable to itself)
* @param <V> - value type
*/
public class KVPair<K extends Comparable<K>, V> {
final public K key;
final public V value;
public KVPair(K key, V value) {
this.key = key;
this.value = value;
}
public boolean equals(Object other) {
if (! (other instanceof KVPair)) return false;
KVPair<K,V> otherPair = (KVPair<K,V>) other;
return (key.equals(otherPair.key) && value.equals(otherPair.value));
}
}
Submit the java file(s) with your testing code by e-mail to me. The subject of the message must be 2101 Lab 12. Make sure to CC your group partners.