A Binary Search Tree [BST] is a binary tree whose internal nodes each store a value that is greater than all the values in its left subtree and less than all the values in its right subtree. Begin with a copy of the code from last night's lecture for this activity.
a. For this lab, you may assume that the values are integers, that no duplicates are allowed, and that you start with an empty tree. Write a replacement for the insert method. This version should accept a new value and add it to the tree, while preserving the "sorted" property. You might want to tweak this method's signature to return a boolean value (true if the value was new and was inserted and false if the value was already present).
b. Check whether the remove method still works correctly. Is there are more efficient way to find the node you need to remove, given that you know the tree is in sorted order? [OPTIONAL: Sketch pseudocode for your method to do that. You can just include this as commentary in your resulting .java file; you don't need to fully implement the improved method.
c. Write a main method that reads integer values from the terminal and adds them to the tree using your modified insert method. It should stop reading and growing the tree when there is no input (or when you provide some special stop value such as -9999). It should then print the resulting tree in sorted order. [OPTIONAL: what is the time complexity of this method of sorting? Why?]