Standard Bar Binary Search Trees · Practice Problems O(h + k) · O(h)
A power grid console keeps substations in a sorted tree by load. During a rolling audit, the operator must report the substation holding the kth smallest load. Instead of collecting every reading, the console plays back the tree in its natural sorted order and simply counts out loud — the meter at count k is the answer.
Input: A binary search tree as a level-order array (null marks a missing child) and an integer k (1-indexed rank).
Output: Return the kth smallest value in the tree.
1 <= number of nodes <= 10^51 <= k <= number of nodes-10^9 <= node value <= 10^9Input: {"tree":[3,1,4,null,2],"k":1}
Output: 1
The sorted order is 1, 2, 3, 4 — the 1st smallest is 1.
Input: {"tree":[3,1,4,null,2],"k":3}
Output: 3
Counting three steps through the sorted order lands on 3.