## CSci 2101 Lab 12.

#### 30 points

#### Due Monday, April 21.

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.

#### Task 1. Removing a node from a binary search tree

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.

#### Task 2. Tree traversals.

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));
}
}
```

#### How to submit

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.

CSci 2101 course web site.

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.