Kth Number: Implementation

function kth(nodeL, nodeR, l, r, k)
    // nodeL = root of version L
    // nodeR = root of version R+1
    if l = r then
        return l  // found the value

    mid := (l + r) / 2
    leftCount := nodeR.left.count - nodeL.left.count

    if k <= leftCount then
        return kth(nodeL.left, nodeR.left, l, mid, k)
    else
        return kth(nodeL.right, nodeR.right, mid + 1, r, k - leftCount)

You walk down both trees simultaneously, comparing their counts to traverse.

To answer "kth in range $[L, R]$":

answer := kth(roots[L], roots[R + 1], 0, maxVal, k)

Time: $O(\log n)$ per query. Space: $O(n \log n)$ total.