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

• ``````/*
* 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 ;
}
}
};``````

• 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().

• 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 !

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