Design a data structure D that supports the following operat

Design a data structure D that supports the following operations in O(log n) time: insert(x)-insert x into D find(k) -returns the k th smallest element from D. search(x) -returns true if and only if x D You may assume that all elements of D are integers.

Solution

We can use augmented self balancing binary search tree.

We know insert and search in self balanced binary search tree is O(log n)

And for kth smallest because of count of smallest element than current element is present in node, we can get kth smallest element in O(log n)