From what I can tell, the running time is O(height of BST) + O(k), optimal means lower bound?
size to BST node. Looks like:
class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None self.size = 1 # the size of subtree whose root is current node
size too. Then we can get kth smallest element according to
root of the
root.size == k, return
root.size > k, search the
ksmallest element of
root.size < k, search the
k - root.sizesmallest element of
At most we search
height of BST times, so it's
O(height of BST).
I have the same thought as shiyanhui.
The additional size property is to be maintained when inserting or deleting the node.
Simply when you find the position to insert/delete, you update the size property(+1 / -1) along the parent path all the way to the root.
I think this pretty much completes the interview question.