Assignment 2: Binary Search Trees

You must provide a program that builds binary search trees node-by-node. Your program will read input from standard in, and provide output to standard out. Each line of input will contain one commond, from the following list:

insert key

Insert key into the binary search tree, adding it as a leaf node. The structure of the tree should remain the same, except as necessary to add the new node. key will be an all-lower case alphabetic string from 1 to 30 letters long. If 'key' is already in the binary search tree, then your method should take no actions. This command will have no output associated with it.

find key

Print the depth of the node containing key. The root is depth 0. If a node is depth n, then its children are depth n+1. If key is not in the binary search tree, then you should print -(m + 1) where m is the depth at which key would be placed, if key were to be added immediately. So, on an empty tree, 'find bob' would have, as output '-1'.

clear

This command clears the tree, removing all nodes from it. This is the same state in which your program should start.

delete key

Delete key from the binary search tree. If key isn't currently in the binary search tree, then do nothing. If key is, then you must first find its node, p.

If p has no children, you are finished
If p has only 1 child, then that child should take p's place
If p has 2 children, then :
- Find q, the leftmost node in the right subtree (rooted at p.right)
- q has no left child, but might have a right child, r
- r should replace q in the tree, and q should replace p in the tree

quit

Quit

Sample input. Which corresponds to this sample output.

Slightly larger sample input. Which corresponds to this slightly larger sample output.

Slightly largerer sample input. Which corresponds to this slightly largerer sample output.

Due Date and Turn-in

This assignment is due Friday, October 19, 11:59pm. E-mail me your code when ready. If it is just one file, you can attach it as-is. If there is more than one file, you should submit a .zip, .tar, or .tgz.

Questions?

Questions? Ask! Send me e-mail. As questions are posed, I will post most of them either here, or on a separate yet-to-be-created page.