Solution: The k-th In-order Visit

In-order traversal gives the values in ascending order. So the k-th value visited in-order is the k-th smallest value.

The only thing left to do is stop the traversal at the k-th visit.

One recursive solution passes a small state object through the traversal:

private static class State<T> {
  int seen;
  T value;
  boolean found;
}

Then the method looks like this:

public static <T> T kthSmallest(Node<T> root, int k) {
  if (k <= 0) {
    throw new IllegalArgumentException("k must be positive");
  }

  State<T> state = new State<>();
  kthSmallest(root, k, state);

  if (!state.found) {
    throw new IllegalArgumentException("k is larger than the tree");
  }
  return state.value;
}

private static <T> void kthSmallest(Node<T> node, int k, State<T> state) {
  if (node == null || state.found) {
    return;
  }

  kthSmallest(node.left, k, state);
  if (state.found) {
    return;
  }

  state.seen++;
  if (state.seen == k) {
    state.value = node.value;
    state.found = true;
    return;
  }

  kthSmallest(node.right, k, state);
}

The traversal order is the ordinary in-order order: left subtree, node, right subtree.

The counter increments when the node is visited. When the counter reaches $k$ , we record the value and set found so the remaining recursive calls can return without doing more work.

Here is the traversal for $k = 4$ , call by call. There are four things to know to read the trace below:

Indentation shows how deep the recursion has gone; one step in is one call deeper.
kthSmallest(n) is a call on node n, and the [...] after it says which child n is.
visit n (i) counts node n, and the number (i) is its place in the in-order order.
→ ... shows every value counted so far.

kthSmallest(50)
  kthSmallest(30)    [50's left]
    kthSmallest(20)  [30's left]
      visit 20  (1) → 20
    visit 30  (2) → 20 30
    kthSmallest(40)  [30's right]
      visit 40  (3) → 20 30 40
  visit 50  (4) → 20 30 40 50

At 50, the counter reaches 4, so the answer is 50. The trace ends there: kthSmallest(50) never recurses into its right subtree, so 60, 70, and 80 are never visited.

Here are the same numbers placed on the tree, so you can see where each visited node is. The nodes with no number are the ones the traversal never reaches, because it stops early:

                           ╭────╮
                       (4) │ 50 │
                           ╰──┬─╯
              ┌───────────────┴───────────────┐
           ╭──┴─╮                          ╭──┴─╮
       (2) │ 30 │                          │ 70 │
           ╰──┬─╯                          ╰──┬─╯
       ┌──────┴──────┐                 ┌──────┴──────┐
    ╭──┴─╮        ╭──┴─╮            ╭──┴─╮        ╭──┴─╮
(1) │ 20 │    (3) │ 40 │            │ 60 │        │ 80 │
    ╰────╯        ╰────╯            ╰────╯        ╰────╯

The iterative in-order traversal works here too. It is the loop the chapter turned into the binary search tree’s iterator. Because the loop keeps its own explicit stack, it already pauses after each visit. Each time it pops a node and visits it, increment the counter. When the counter reaches $k$ , return the value.

With the early stop, the cost is the cost to reach the smallest value, plus the first $k$ visits. That is $O (h + k)$ , which is less than $O (n)$ when the height $h$ and $k$ are both small compared to $n$ . In the worst case, $k$ is $n$ , or the tree is close enough to degenerate that reaching the smallest value already costs $O (n)$ , so the cost is $O (n)$ .

That is still better than collecting all values and sorting them, which costs $O (n lo g n)$ and ignores the order already stored in the tree.