Kth Smallest Element in a BST
Medium· BST· Inorder
Problem
Given the root of a binary search tree and an integer k, return the k-th smallest value stored in the tree (counting from 1).
Examples
Input: root = [3,1,4,null,2], k = 1
Output: 1
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Sorted values are 1, 2, 3, 4, 5, 6; the third is 3.
Constraints
- • 1 <= k <= number of nodes <= 10^4
- • 0 <= Node.val <= 10^4
Hints & approach
Hint 1
Which traversal of a BST yields the values in sorted order?
Hint 2
You do not need the full sorted list; stop as soon as you have seen k values.
Approachtry the hints first
Inorder traversal of a BST visits values in ascending order. Run it iteratively with a stack, decrementing k each time you pop a node; when k reaches 0, the popped value is the answer. This stops early, costing O(h + k) rather than visiting the whole tree.
Time O(h + k) · Space O(h)