Lab 1--Build a Binary Search Tree

Purpose
The purpose of this assignment is to have some practice programming a tree from scratch.

What to do

1. Design and implement a class for the node in your tree.
   Use the excerpts of code from the book as a reference.
2. Design a class for the tree itself. One data member (or attribute) in this class should be a reference variable to point to the root.
3. Decide on the functionality you will need. You must implement insertion, deletion, search, and outputting the tree's contents in-order, pre-order and post-order.
4. Write a driver to call your methods.
5. First have the tree hold an object that has an integer that can be compared until everything is working, then modify your tree to handle objects that can be compared. So first just compare the ints in the Node, then modify the code to compare the whole Node as a comparable object.
   • Remember that your key must be Comparable. Any methods in your tree class that say what the data type of the key is should be Comparable, not Object. This lets you use the compareTo method in the tree class.
6. At the end of today's lab I would like to see you inserting elements into the tree, deleting properly and at least one output of the contents. Get as much done as you can.

Grading Criteria

• Programming style
• Insertion
• Deletion
• Search
• In-Order Display
• Pre-Order
• Post-Order