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