Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) among all node values.
Example 1
Input: root = [3,1,4,null,2], k = 1
Output: 1
Explanation: Inorder traversal visits 1, 2, 3, 4 — the 1st smallest is 1.
The number of nodes is n1 <= k <= n0 <= Node.val <= 10^4What traversal order of a BST visits nodes in ascending sorted order automatically?
You don't need to collect every value into a list first — you can stop as soon as you've visited the kth node.
An iterative inorder traversal (the same stack-based technique from Binary Tree Inorder Traversal) lets you stop early without the awkwardness of returning early from deep recursion.
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
int count = 0;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
count++;
if (count == k) return curr.val; // stop the instant we've visited the kth node — no need to finish the traversal
curr = curr.right;
}
throw new IllegalArgumentException("k is out of range");
}Time: O(h + k) · Space: O(h)