Why the hint says "The optimal runtime complexity is O(height of BST)." ?


  • 1

    From what I can tell, the running time is O(height of BST) + O(k), optimal means lower bound?


  • 9

    Add property 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
    

    When insert/delete, update size too. Then we can get kth smallest element according to size.

    Visit from root of the BST:

    • if root.size == k, return root.val.
    • if root.size > k, search the k smallest element of root.left
    • if root.size < k, search the k - root.size smallest element of root.right

    At most we search height of BST times, so it's O(height of BST).


  • 0
    O

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.