Question

(Java) Suppose we want to add the operation findKth to our repertoire. The operation 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 operation in O(logN) average time, without sacri?cing the time bounds of any other operation.

EXPERT ANSWER

Following is the Code for Binary Search Tree :

public class KthSmallest

{

public