Recursive inorder traversal solution and follow up


  • 0
    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.


Log in to reply
 

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