0. Problem

No matter where you are in the BST, all the left children will have a smaller value, and all the right children will have a greater value:

A useful trick is that inorder traversals visit the nodes in a BST from smallest to largest. This is because inorder traversals visit left subtree, then the current node, then the right subtree, L c R. So on a BST, they end up visiting all the "smaller" left nodes, then the current node, then all the "larger" right nodes.

This means to solve this problem, we can just do an inorder traversal and keep track of which element we're on. The kth element is the answer.

1. Recursion

We want to do an inorder traversal, keeping track which element we're on. When we get to the kth element, we want to set it as the solution.

2. Base case

We stop traversing when there are no nodes left or if we already found a value:

3. Code

Combining the recursion and base case gives:

Time Complexity $O(k)$. We iterate through $k$ nodes in the traversal.

Space Complexity $O(k)$. The variables $\tt c$ and $\tt found$ take up O(2) memory. The recursion goes to a depth of k, so the Call Stack grows to a height of O(k), and each call in the Call Stack uses O(1) memory. This is O(2) + O(k)*O(1) = O(k) total memory.