Given the root of a binary search tree and an integer k, return the k-th smallest value in the tree, counting from 1.
Examples
Example 1:
Input: root = [3,1,4,null,2], k = 1
Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Example 3:
Input: root = [2,1,3], k = 3
Output: 3
Example 4:
Input: root = [1], k = 1
Output: 1
Constraints
1 <= k <= number of nodes <= 10^4
0 <= Node.val <= 10^4
Prerequisites
Binary trees, and recursion over them: solve the children, combine, return. The base case is almost always the empty tree. Depth-first order (pre, in, post) and breadth-first by level — and knowing which one a problem is really asking for.
How to think about it
1. In-Order, Stopping at k Optimal
Intuition
In-order traversal of a search tree emits values in sorted order, so the k-th node visited IS the answer — and there is no reason to visit the rest. An explicit stack makes stopping natural: push the left spine, pop, count, then turn right.
Algorithm
1. Walk left from the root, pushing every node. 2. Pop a node — it is the next smallest. 3. Decrement k; at zero, that node's value is the answer. 4. Otherwise move to its right child and push that left spine.
Time & Space
Time O(h + k) — only the first k nodes are visited. Space O(h). Frequent queries with updates want subtree sizes stored on the nodes.