I think we can keep both the kth smallest element and (k-1)th smallest element. If we insert or delete an element larger than the kth smallest element, the result remains unaffected. If something smaller than is inserted, compare it with the (k-1)th smallest element. The larger one becomes the new kth smallest element and adjust (k-1)th element accordingly.

We may also need to keep track of the (k+1)th smallest element in case of deleting a node smaller than the kth element. However if we keep deleting nodes, we may need the (k+2, k+3, .... )th smallest element to stay correct.

Any other ideas?