Because of the BST ordering, an in-order traversal (left subtree, node, right subtree) visits the values in sorted order. That means the k-th node visited is the k-th smallest value, with no sorting required.
Given the root of a BST and an integer k, return the k-th smallest value in the tree (1-indexed).
Examples
3
/ \
1 4
\
2
Input: root = [3, 1, 4, None, 2], k = 1
Output: 1
5
/ \
3 6
/ \
2 4
/
1
Input: root = [5, 3, 6, 2, 4, None, None, 1], k = 3
Output: 3
Constraints
1 <= k <= number of nodes <= 1000- All values are distinct.
Goals
- Exploit the BST invariant: in-order traversal yields values in ascending order
- Implement in-order traversal iteratively with an explicit stack
- Stop a traversal early once the answer is known