Kth Smallest Element in a BST
Find the k-th smallest value stored in a binary search tree.
Given the root of a binary search tree (BST) and an integer k, return the k-th smallest value among all node values in the tree.
k is 1-indexed, so k = 1 asks for the smallest value in the tree.
Example 1
Input: root = [5,3,8,2,4,7,9], k = 1
Output: 2
Explanation: In sorted order the values are 2, 3, 4, 5, 7, 8, 9 -- the smallest is 2.
Example 2
Input: root = [5,3,8,2,4,7,9], k = 4
Output: 5
Explanation: The 4th value in sorted order (2, 3, 4, 5, ...) is 5.
Example 3
Input: root = [5], k = 1
Output: 5
Constraints
- The number of nodes in the tree is in the range [1, 10000].
- 0 <= Node.val <= 1000000
- 1 <= k <= the number of nodes in the tree
- root is guaranteed to be a valid binary search tree.
- All node values are unique.
Follow-up
If the BST is modified often (insertions and deletions) and you need to find the k-th smallest value repeatedly, how would you optimize the search?
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.