Assignment on Java programing 1. Write programs for the following exercises in Java. Each file should have short description of the implemented class and for files with main method the problem it is solving. Make sure your files have appropriate names. Programs should write output to the Console.

b) BST: Implement Binary Search Tree ADT with insert(int key), delete(int key), Node find(int key), and in-order traverse() where it prints the value of the key. Your operations should use recursion. The tree should store key as integer. You should have a single file with class BST for the program. Your test program (main method) should demonstrate that all operations work correctly. Note that your textbook has the pseudo code and code in C for these operations that you can use but you need to modify a little to meet the assignment instructions and grading criteria.

c) BST2List: Copy your BST implementation from above and call it BST2. Change the Node to have additional data: status of type boolean and change BST2 operations appropriately: insert(int key, boolean status), delete(int key), find(int key), traverse(). Then implement an algorithm as method, findList(int low, int max) in BST2 class which prints out all key values within the range low and max if the status is true. Write test program which creates a BST2 instance and loads with below data, displays the values of the nodes in the tree in-order, displays low and max values, and calls findList to display values in range. Evaluate and report the time and space complexity of your findList algorithm. For example,

Original list with status values:

45 false, 38 true, 21 false, 40 true, 50 true, 86 true, 90 false In-order traversal of the BST: 21 38 40 45 50 86 90 low=39 max=51 Find list: 40 50 Grading Rubric Points Criteria 10 Programs use object oriented program approach, have the appropriate naming convention, authors name, and brief description of the implementation in the files and the problem it is solving for main() methods 30 InsertionSort: Correctly implements raw array for data Correctly implements insertion sort algorithm that was covered in class.Correctly selects test data for the analysis and describes in the report Correctly analyzes the runtime performance of the sort, provides results and conclusions in the report explains implementation of insertion sort using raw array explains test data used, analysis, and results of sort performance shows the running program for given instance problem and explains output For extra credit: manually show the array contents after each iteration of the sort and explain what it is doing 30 BST: Correctly implements Binary Search Tree ADT with insert, delete, find, and in-order traverse where it prints the value of the node. explains implementation of BST ADT, test program, shows program running, and explains output 30 BST2List: Correctly adds findList method to modified BST2 ADT Correctly implements algorithm (implemented as method) with recursion to print all the nodes with values in the range of low and max inclusive when status=true Test program creates a BST2 and loads with data