230. Kth Smallest Element in a BST
1. Description
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
2. Example
Example 1:
Input: root = [3,1,4,null,2], k = 1
Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
3. Constraints
- The number of nodes in the tree is n.
- 1 <= k <= n <= $10^4$
- 0 <= Node.val <= $10^4$
4. Follow Up
If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?
5. Solutions
Hash Table
// if we need to query frequently, we can use the Hash Table to save all nodes
// if we need to modify frequently, we need to use the balanced binary search tree
// it's too hard to write a balanced binary search tree
class Solution {
public:
int kthSmallest(TreeNode *root, int k) {
init_(root);
return node_index_[k];
}
private:
int count_ = 0;
unordered_map<int, int> node_index_;
void init_(TreeNode *root) {
if (root != nullptr) {
init_(root->left);
++count_;
node_index_[count_] = root->val;
init_(root->right);
}
}
};