Homework 3: Binary Search Trees

You will implement the OrderedDictionary interface using binary search trees. You will need to use the compareTo() function to define an order on the keys. The input to your program will be a file which contains a sequence of {Insert, Find, Remove, Pred, Succ, Min, Max} commands. The output should be one line for each command. The format of the output lines for {Insert, Find, Remove} is shown below. The format of output lines for {Pred, Succ, Min, Max} is similar (see input_sample and output_sample for the exact format).

For an insert command, the output should read as:
Insert "key", "value" succeeded.
or
Insert "key", "value" failed. "key" already exists.

For a find command, the output should read as:
Find "key" returned "key", "value"
or
Find "key" returned null

For a remove command, the output should read as:
Remove "key" removed "key", "value"
or
Remove "key" failed. "key" does not exist.

Notice that keys and key-value pairs should always be in quotes as shown.
The name of the file will be specified as a command-line argument:
e.g.: java BST commands-file

We have provided an "input_sample" and the corresponding "output_sample" files. To test your programs, do the following:
java BST input_sample
For a correct implementation, the output should be identical to "output_sample"

To test if your implementation is correct, use:

java BST commands > out
diff out output_sample

Support files:

Test Outputs:

Results

grading