4.48

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(logN) average time, without sacrificing the time bounds of any other operation. (C++) (start from scratch)

NOTE : please submit the .cpp file with at least three (3) test cases for each problem,