Given the root of a binary search tree and an integer k, return the kth smallest key (1-indexed).
Before you code
An inorder traversal lists a BST's keys in sorted order, so the answer is the kth key it visits. There is no need to collect the rest.
Hints
- Traverse inorder with an explicit stack and count nodes as you pop them; stop at k.
- That costs O(h + k) rather than O(n).
- Follow-up: if the tree changes often and kth queries are frequent, store each node's subtree size. Then you can walk straight to the kth key in O(h).
Production & complexity notes
When solving Kth smallest element in a BST on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Binary search trees to reinforce the underlying pattern.
What it practices
Sorted order from inorder traversal, from Binary search trees.