Problem: The k-th Smallest Value

In-order traversal reads a binary search tree from smallest to largest. This problem asks you to use that order without doing extra sorting.

public static <T> T kthSmallest(Node<T> root, int k) {

}

Use this tree for examples:

                ╭────╮
                │ 50 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 30 │                │ 70 │
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│ 20 │    │ 40 │      │ 60 │    │ 80 │
╰────╯    ╰────╯      ╰────╯    ╰────╯

The sorted order is:

20  30  40  50  60  70  80

So:

• k = 1 returns 20,
• k = 4 returns 50,
• k = 7 returns 80.

The brute-force answer is to collect every value into a list, sort the list, and return the element at index $k-1$.

But sorting is not necessary, because in-order traversal already visits the values in sorted order. So the question is: Can we traverse in-order and stop at the k-th visit?

Attempt the problem before reading the solution.