1. Modify Binary SearchST (Algorithm 3.2 in textbook on page 379) so that inserting a key that is larger than all keys in the table takes con- stant time (so that building a table by calling put() for keys that are in order takes linear time). [6 marks] 2. Given a standard binary search tree (BST) (where each key is greater than the keys in its left subtree and smaller than the keys in its right subtree), design a linear-time algorithm to transform it into a reverse BST (where each key is smaller than the keys in its left subtree and greater than the keys in its right subtree). The resulting tree shape 1 should be symmetric to the original one. It is not required of you to output the tree from your code (if you implement it in JAVA). Marks will be given based on the logic and correctness of the algorithm. [7 marks)