hardTreesPure DSA~30 min
Kth Smallest Value in a Pricing BST
Price tiers are stored in a binary search tree. Find the k-th lowest price without flattening the whole tree.
Problem
Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed) among all node values.
Input
A BST root and an integer k.
Output
An integer: the k-th smallest value.
Constraints
- 1 <= k <= number of nodes <= 10^4
- 0 <= node value <= 10^9
- The tree satisfies the BST property.
Examples
Example 1
Input
root = [3,1,4,null,2], k = 1
Output
1
The smallest value is 1.
Example 2
Input
root = [5,3,6,2,4,null,null,1], k = 3
Output
3
In-order order is 1,2,3,4,5,6; the third is 3.