CSci 2101 Lab 9.

30 points

Due Wednesday, April 13th.

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), finish the method that removes a node with a given key from the tree.
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.

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 9. 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.