Implement data structure with efficient insert/findKthSmallest operations

I was asked this question by an interviewer. I tried solving it using an array, such that I make sure the array in sorted when I insert. However I don't think this is the best solution. What would be a good solution for this problem?

• Is $k$ constant across the lifetime of the data structure? Dec 23 '19 at 6:08

Make an augmented search tree. This is an ordinary binary search tree, where each node additionally stores the number of elements in its subtree. This data structure is known as order statistic tree.

If we balance the BST (making it an AVL tree for instance) then insertion can, of course, be done in logarithmic time (incrementing the node count along the search path).

Also finding the k-th element is logarithmic time. Let $$n$$ be the number of nodes in the left subtree of the root. If $$k=n+1$$ we return the root. If $$k\le n$$ we continue in the left subtree. If $$k>n$$ we return the $$k-(n+1)$$-st node in the right subtree.

• The specific name for this application of an augmented search tree is an order statistic tree. Dec 22 '19 at 4:14
• Thanks @AaronRotenberg for your observation. I added the name to the main text. Dec 22 '19 at 18:53
• An anonymous(?) editor suggested the following C++ specific reference to the data structure: GNU C++ - PBDS - geeksforgeeks.org/ordered-set-gnu-c-pbds Dec 22 '19 at 18:54

You can use Heaps. Min heaps can find kth smallest element in O(k* logn) i.e O(logn) times if heap is already build. If not in O(n + k*logn) times i.e. in O(n) time if heap is to be build from the scratch.