ICS 211 Homework 10

Tree Traversal

In this assignment, you modify the BinarySearchTree class to add these two methods:

public T findNext(T key) throws java.util.NoSuchElementException
public T findPrevious(T key) throws java.util.NoSuchElementException

which, given a key, search for that key, then return the record in the node that is before or after the node containing the key.

Finding the node before or after may require a search in the tree somewhat similar to what is needed when adding or removing a node. You probably have to use recursion or a stack.

To be clear, given a key k, the node before that is the node with the largest key that is less than k. The node after that is the node with the smallest key that is larger than k. To find that node, your code will have to traverse the tree.

For example, suppose the binary search tree has values with key,value pairs "bar",7, "baz",4, "fee",1, "foo",6, "fum",7. Assume that k is a record with key "foo" (for k, the value is not used). For example, we could have

Record k = new Record("foo");

Then, findNext(k) should return the record "fum",7, and findPrevious(k) should return the record "fee",1. The exact arrangements of records in nodes, that is, the structure of the tree, depends on the sequence in which the nodes were added to the tree. Whatever the structure, your code must find the node immediately preceding or following.

These description assumes that k is in the tree, and that a key less/larger than k is also in the tree. If they are not, the following apply:

if the key is not in the database, return null
if the key is in the database, but there is no previous/next key in the database, throw java.util.NoSuchElementException
since java.util.NoSuchElementException is a RuntimeException, your method doesn't need to declare that it throws the exception
you don't need to worry about the case of multiple elements with the same key -- each key will be in at most one node

You must also modify the TreeMenu.java class so the user can request the information for the node before or after a given node by entering the corresponding key. When you modify this class, you must display the result of the operation to the user, including a clear statement for each of the possible outcomes.

You will need to use the Record.java class, but you should not need to modify it.

You need to understand both BinarySearchTree.java and TreeMenu.java before you can expect to do the assignment.

Turning in the Assignment

Email all the java source code for these three classes:

to the TA following the instructions posted here.