Kth Smallest Element in a BST
Given the root of a binary search tree, and an integer k, return the k^th smallest value (1-indexed) of all the values of the nodes in the tree.
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?
Example 1
3
/ \
1 4
\
2Input
root = [3,1,4,null,2], k = 1Output
1The smallest value in the BST is 1.
Example 2
5
/ \
3 6
/ \
2 4
/
1Input
root = [5,3,6,2,4,null,null,1], k = 3Output
3The values in sorted order are [1, 2, 3, 4, 5, 6], so the 3rd smallest value is 3.
Constraints
- The number of nodes in the tree is
n. - 1 <= k <= n <= 10^4
- 0 <= Node.val <= 10^4