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.
Examples
Input:
root = [3,1,4,null,2], k = 1Output:
1Explanation:
The smallest element is 1.
Input:
root = [5,3,6,2,4,null,null,1], k = 3Output:
3Explanation:
The 3rd smallest is 3.
Input:
root = [10,5,15,3,7,12,20], k = 5Output:
12Explanation:
The BST contains values [3,5,7,10,12,15,20] in sorted order. The 5th smallest element is 12.
Constraints
- •
The number of nodes in the tree is n. - •
1 ≤ k ≤ n ≤ 10⁴ - •
0 ≤ Node.val ≤ 10⁴