Problem. Given the root of a binary search tree and an integer k (1-based), return the k-th smallest value.
5
/ \
3 6 k = 4 → 4 (sorted: 1, 2, 3, 4, 5, 6)
/ \
2 4
/
1
Lesson 10.9 showed that an in-order walk of a BST visits values in sorted order. The questions here are how early you can stop, and how to answer many such queries on a tree that keeps changing.
ML context. "What is the k-th best score?" and its reverse "what rank is this score?" are leaderboard and percentile questions: the rank of a new checkpoint among all evaluated ones, the percentile of a request's latency among recent requests, the median of a growing set of scores. When the set changes constantly, recomputing from scratch is wasteful; a tree that stores subtree counts answers both in O(log n) (Changes A and B).