What is the O(h) solution?


  • 0
    G

    The hint says that:

    The optimal runtime complexity is O(height of BST).

    What is this solution?

    At first, I thought of balancing the tree. If I am given a balanced tree, it should be fairly easy to predict the position of the kth smallest node, knowing the height of the tree.

    However, looking at the web, it seems that balancing a tree requires O(n) steps.

    Any hint?


    FWIW, so far, I have implemented a O(h + k) solution using inorder traversal.


  • 0

    Think of storing additional information inside the nodes (i.e., extend the TreeNode class).


  • 0
    G

    But how can I add such information by visiting at most O(h) nodes?


  • 0
    G

    Mh... perhaps I got it: the extra information (i.e. the number of child nodes I guess) is stored and maintained by insertions and deletions, it does not need to be computed by my code.


  • 0

    Yep, I think that's the intended way.


Log in to reply
 

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