A game keeps high scores in a binary search tree with distinct values. Return the k-th highest score (k = 1 is the best score). Return None if the tree holds fewer than k scores.
Examples
12
/ \
7 18
/ \ / \
3 9 15 22
\
5
Input: root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), k = 1
Output: 22
Input: root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), k = 3
Output: 15
Constraints
0 <= number of nodes <= 3000,k >= 1- All values are distinct integers
- O(h + k) time
Goals
- Visit values in descending order with a reverse inorder walk
- Stop as soon as the k-th value is reached