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 kthSmallestBruteForce(TreeNode root, int k) {
List<Integer> values = new ArrayList<>();
inorder(root, values);
return values.get(k - 1);
}
private void inorder(TreeNode node, List<Integer> values) {
if (node == null) return;
inorder(node.left, values);
values.add(node.val);
inorder(node.right, values);
}Time: O(n) · Space: O(n)