# Recursive inorder traversal solution and follow up

• ``````class Solution {
private:
bool inorder( TreeNode* root, int& k, int& val ) {
if( root->left ) if(inorder(root->left, k, val)) return true;
if( k <= 1 ) { val = root->val; return true; }
else k--;
if( root->right ) if( inorder(root->right, k, val)) return true;
return false;
}
public:
int kthSmallest(TreeNode* root, int k) {
int val = 0;
inorder( root, k, val);
return val;
}
};
``````

As for the follow up question, what if the bst is being modified very frequently? Inorder traversal takes at least k + log(n) steps to get the right answer.

I think we can maintain two heaps, one for the first k elements, a max heap(the root node is the kth smallest element), the other for the left elements, a min heap ( the root node is the kth+1 smallest element). Whenever the bst is modified, we update the two heaps accordingly.

In theory, each time we just need at most log(k) + log(n-k) steps to update the two heaps, and O(1) to get the answer. If k is big, that would be worth it.

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