DSA problem
Kth Smallest Element in a BST
Given the root of a Binary Search Tree (BST) and an integer k, return the k-th smallest value among all node values. The problem is 1-indexed: k = 1 asks for the minimum.
A naive solution does a full inorder traversal into an array of size n, then returns array[k - 1]. That is correct and easy to write, but it touches every node even when k is tiny, and it allocates O(n) space.
The optimal approach takes advantage of two facts. First, inorder traversal of a BST yields values in strictly ascending order, so the k-th node visited in inorder is exactly the k-th smallest. Second, we do not need to finish the traversal: we can stop as soon as we have popped k nodes from the stack.
We therefore run an iterative inorder traversal with an explicit stack, decrementing a counter on each pop. The first time the counter hits zero, the value just popped is the answer. In the best case (small k) we touch only O(h + k) nodes; in the worst case (k near n) we still touch O(n). The stack never grows beyond the height of the tree, so the space usage is O(h).
Examples
root = [3,1,4,null,2], k = 11root = [5,3,6,2,4,null,null,1], k = 33root = [3,1,4,null,2], k = 44Constraints
- The number of nodes in the tree is n.
- 1 <= k <= n <= 10^4
- 0 <= Node.val <= 10^4
- The tree is guaranteed to be a valid BST.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.