Find the K-th Smallest Value in a Search Tree
Implement kthSmallest
You are given the root of a binary search tree with distinct values and an integer k. Return the k-th smallest value in the tree, where k = 1 means the smallest. If the tree contains fewer than k values, return -1.
An inorder walk visits a search tree's values in ascending order, so the k-th smallest is the k-th value visited — and the walk can stop right there.
Example 1:
Input: root = [52,30,75,18,41,63,90,10,25,35,47], k = 4
Output: 30
Example 2:
Input: root = [52,30,75,18,41,63,90,10,25,35,47], k = 1
Output: 10
Example 3:
Input: root = [52,30,75,18,41,63,90,10,25,35,47], k = 12
Output: -1
+ 13 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ●
The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node - ●
1 ≤ k ≤ 150 (k may be larger than the number of nodes) - ●
Return the k-th smallest value in the tree (k = 1 is the smallest). If the tree has fewer than k values, return -1
root =
[52, 30, 75, 18, 41, 63, 90, 10, 25, 35, 47]
k =
4