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