SA-6

Exercises

Write an implementation of the Set ADT called BSTSet that uses the Binary Search Tree (BST.java) from class to store the data. Your Set implementation should conform to this SimpleSet.java interface. Include test cases to show that your implementation works as intended.

Hint: create an instance variable in your BSTSet class that is the root of a BST. You can use the Key of the BST to store your Set's values. You won't need the Value of the BST, so you can set it to any type you choose. To implement the Set functionality, call BST methods using the root of the BST. Do not try to extend BST and to implement Set functionality.

Hint 2: for the iterator method, see for example how we implemented an Iterator for our linked list: SinglyLinked.java (note also that the parent class must implement Iterable). Your iterator method should simply return a new SetIterator object. Create a private SetIterator class within BSTSet that implements the methods hasNext() and next(). You might find it easiest to give your SetIterator a List instance variable and in its constructor initialize this list by traversing your BST in order. Then you can use the List as a basis for your iterator.

Submission Instructions

Turn in your completed Java code with test cases. If you create multiple files, combine them into a single .zip file. If you include your test cases in your BSTSet class, there is no need to zip this one file.