K-th Smallest: Why It Works

At each node, you're partitioning values into lower half (left) and upper half (right).

The count of elements going left tells us: are the first $k$ smallest values all in the left subtree?

• If yes ($k \leq \text{leftCount}$): recurse left with same $k$
• If no ($k > \text{leftCount}$): recurse right with $k - \text{leftCount}$

You're doing binary search on the value space, guided by position counts.

Each level eliminates half the values. After $\log \sigma$ levels, you reach a leaf containing the answer.