A follow up solution with query kth smallest time complexity O(height of tree)


  • 0
    A
    /*
     * Follow up:
      * What if the BST is modified (insert/delete operations) often and you need to find the kth smallest           frequently?
      * How would you optimize the kthSmallest routine?
      * Hint:
      * 1. Try to utilize the property of a BST.
      * 2. What if you could modify the BST node's structure?
      * 3. The optimal runtime complexity is O(height of BST).
      * Solution:
      * Change the structure of TreeNode, add the number of left child(cnt_left_child) and the number of right      child(cnt_right_child);
      * Insert/ delete a node of BST, update the cnt_left_child and cnt_right_child, time complexity: O(height of the tree);
      * Query the Kth smallest, just count the cnt_left_child and cnt_right_child, time complexity: O(height of the tree);
      */
    

    Welcome to discuess !

    /here comes the cut line******/

    class Solution {
    public:
        int kthSmallest(TreeNode* root, int k) {
            int val = 0, count = 0;
            //inorderBST(root, k, count, val);    //solution to the original question
            findKthSmallest(root, k - 1, count, val);  //solution to the following up question
            return val;
        }
    private:
        void inorderBST(TreeNode* node, int k, int &count, int &val){
            if(node == nullptr)
                return;
    
            inorderBST(node->left, k, count, val);
            count++;
            if(count == k) {
                val = node->val;
                return ;
            }
            inorderBST(node->right, k, count, val);
        }
     
        void findKthSmallest(TreeNode* node, int k, int &count, int &val){
            if(node == nullptr)
                return ;
            if(k == node->cnt_left_child){
                val = node->val;
                return ;
            }
            else if(k < node->cnt_left_child){
                findKthSmallest(node->left, k, count, val);
                return ;
            }
            else{
                count -= node->cnt_left_child - 1;
                findKthSmallest(node->right, k, count, val);
                return ;
            }
        }
    };

  • 0
    1

    I think the time complexity of your solution is O(n), in which n is the number of nodes in the tree. and the function findKthSmallest() is redundant, since val is just the kthSmallest after you run the function inorderBST().


  • 0
    A

    inorderBST() is the solution for original problem, while findKthSmallest() is the solution for the folllowing up question. inorderBST() is O(N) time complexity, while findKthSmallest() is O(logN). Sorry for bring you ambiguity since I put two functions in the public method. I have modified. Thank you !


Log in to reply
 

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