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.
FWIW, so far, I have implemented a O(h + k) solution using inorder traversal.
Think of storing additional information inside the nodes (i.e., extend the TreeNode class).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.