Kth Smallest Element in a BST — Practice

Problem

Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) among all node values.

Examples

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.

Constraints

•The number of nodes is n
•1 <= k <= n
•0 <= Node.val <= 10^4

Hints

Hint 1

What traversal order of a BST visits nodes in ascending sorted order automatically?

Hint 2

You don't need to collect every value into a list first — you can stop as soon as you've visited the kth node.

Hint 3

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.

Solutions

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)