Kth Cheapest Listing

medium

A marketplace keeps its live listings in a binary search tree keyed by price. A bargain-hunting feature needs the k-th cheapest listing — without dumping the whole index into a sorted array first.

Given the root of a BST and an integer k (1-indexed), return the k-th smallest value in the tree.

Tests pass a level-order array and k; implement the core in _kth_smallest on real nodes.

Example 1

in values = [3, 1, 4, null, 2], k = 1

out 1

Example 2

in values = [5, 3, 6, 2, 4, null, null, 1], k = 3

out 3

Sorted order is 1, 2, 3, 4, 5, 6 — the third is 3.

Example 3

in values = [2, 1, 3], k = 3

out 3

Constraints

· 1 <= k <= number of nodes <= 10^4
· 0 <= node value <= 10^4
· all values distinct