504. Kth Smallest Key
A tournament organiser stores player ratings in a binary search tree, where keys in a node's left subtree are smaller, keys in its right subtree are larger, and every rating is distinct. She wants to know who sits at a given position when the ratings are listed from lowest to highest.
Given the tree root and an integer k (counting from 1), return the key of the k-th smallest node. For example, k = 1 asks for the minimum and k equal to the number of nodes asks for the maximum. The tree is never empty and k is always valid.
Example 1
- Input:
- root = [20,10,30,5,15,25,35], k = 3
- Output:
- 15
- Explanation:
The keys in increasing order are 5, 10, 15, 20, 25, 30, 35, so the 3rd smallest is 15.
Example 2
- Input:
- root = [20,10,30,5,15,25,35], k = 7
- Output:
- 35
- Explanation:
The 7th smallest of the seven keys is the maximum, 35.
Constraints
1 ≤ number of nodes ≤ 104
1 ≤ k ≤ number of nodes
-109 ≤ Node.val ≤ 109
The tree is a valid binary search tree with distinct keys.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(h + k)
- Space
- O(h)