Find the K-th Largest Value in a Search Tree
Implement kthLargest
You are given the root of a binary search tree with distinct values and an integer k. Return the k-th largest value in the tree, where k = 1 means the largest. If the tree has fewer than k values, return -1.
Visiting the tree right subtree first, then the node, then the left subtree produces the values from largest to smallest — so the k-th largest is the k-th value visited, and the walk can stop there.
Example 1:
Input: root = [48,20,70,10,35,58,85,null,null,30,40,null,65,null,90], k = 3
Output: 70
Example 2:
Input: root = [48,20,70,10,35,58,85,null,null,30,40,null,65,null,90], k = 11
Output: 10
Example 3:
Input: root = [48,20,70,10,35,58,85,null,null,30,40,null,65,null,90], k = 12
Output: -1
+ 12 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 largest value in the tree (k = 1 is the largest). If the tree has fewer than k values, return -1
root =
k =