Extending BST

PRELIMINARIES:

Before starting this assignment you need to be familiar with queues and binary search trees.

THE ASSIGNMENT:

• Write a driver for certain operations of a keyed list. Use the sample.in and the sample. Out files to see what the commands are and what they do. If you wish, you may create your driver by filling out this driver shell.
• Implement the emptyTest, insert, and delete commands seen in sample.in with driver functions that use the SearchTreeIsEmpty, SearchTreeInsert, and SearchTreeDelete operations of the bstClass.
• Implement the count, height, treePrint, and levelPrint commands seen in sample.in by implementing new operations for the LinkedBinarySearchTree and calling them from appropriate functions in the driver. There are new prototypes for the following new public functions: recTreeCount, recTreeHeight,rec RevOrderPrint, and LevOrderPrint. You must write the code for each of these functions by filling in the appropriate "empty function" in the file LinkedBinarySearchTree.java.

IMPLEMENTATIONS:

Keep in mind that it is your responsibility to write the driver and to fill in certain function bodies in the LinkedBinarySearchTree.java file. On the other hand, you must not make any "unauthorized" changes to LinkedBinarySearchTree.java. Also, you must not change any of the other *.java files I am giving you in the assignment directory.

Make recTreeCount, recTreeHeight, and recRevOrderPrint recursive functions. In class we will discuss details of the algorithms to be used by recTreeCount, recTreeHeight, and recRevOrderPrint.

For LevOrderPrint, I recommend a solution that employs a queue as an auxiliary data structure. You will be able declare and use a local variable of type queueClass within your LevOrderPrint function. In class we will discuss more details concerning these data types and also we will discuss the algorithm to be used by the LevOrderPrint function.