Kth Smallest Element in a BST

Problem

Given the root of a binary search tree and an integer k, return the k-th smallest value in the tree, counting from 1. All values are distinct and k never exceeds the number of nodes.

• The tree has between 1 and 50,000 nodes and is not necessarily balanced.
• Node values are distinct non-negative integers.
• 1 <= k <= number of nodes.

Examples

• root = [12, 6, 20, 3, 9, 15, 30], k = 1 → 3. The smallest value is the leftmost node.
• root = [40, 25, 55, 18, 33, None, 70, None, 21], k = 3 → 25. Sorted order is 18, 21, 25, 33, 40, 55, 70.
• root = [9], k = 1 → 9.

Hints

1. Which traversal order of a BST produces its values in sorted order?
2. You do not need the whole sorted sequence, only the k-th element. Can you stop early?
3. Iterative inorder with an explicit stack; pop k times and return the k-th popped value.