1. a. Show that via AVL single rotations, any binary search tree T1 can be transformed into another search tree T2 (with the same items).
b. Give an algorithm to perform this transformation using O(N log N) rotations on average.
c. Show that this transformation can be done with O(N) rotations, worst-case.
2. Suppose we want to add the operation findKth to our repertoire. The opera- tion findKth(k) returns the kth smallest item in the tree. Assume all items are distinct. Explain how to modify the binary search tree to support this opera- tion in O(log N) average time, without sacri?cing the time bounds of any other operation.