Find the K-th Smallest Value in a Search Tree
Solve this ProblemYou are given the root of a binary search tree with distinct values and an integer k. Return the k-th smallest value in the tree, where k = 1 means the smallest. If the tree contains fewer than k values, return -1.
An inorder walk visits a search tree's values in ascending order, so the k-th smallest is the k-th value visited — and the walk can stop right there.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ◆
The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node - ◆
1 ≤ k ≤ 150 (k may be larger than the number of nodes) - ◆
Return the k-th smallest value in the tree (k = 1 is the smallest). If the tree has fewer than k values, return -1
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Write Out the Whole Sorted List, Then Index It
BruteAn inorder walk of a binary search tree gives the values in ascending order. Collect all of them in a list, then the k-th smallest is simply the item at position k − 1 (or -1 if the list has fewer than k items). It always walks the entire tree and stores every value: O(n) time and O(n) space.
O(n)O(n)1class Solution {
2 public int kthSmallest(TreeNode root, int k) {
3 List<Integer> vals = new ArrayList<>();
4 inorder(root, vals);
5 return k <= vals.size() ? vals.get(k - 1) : -1;
6 }
7
8 private void inorder(TreeNode node, List<Integer> vals) {
9 if (node == null) return;
10 inorder(node.left, vals);
11 vals.add(node.val);
12 inorder(node.right, vals);
13 }
14}Optimal — Iterative Inorder That Stops at the K-th Visit
OptimalRun the inorder walk with an explicit stack, but count the nodes as they are visited and stop the moment the counter reaches k — the k-th visited node IS the k-th smallest. From the current node keep going left, pushing nodes; then pop one (that is the next smallest value), count it, and continue with its right child. Only the leftmost path and the nodes needed up to the k-th value are touched: O(h + k) time and a stack of at most h nodes; no list is built.
O(h + k)O(h)1class Solution {
2 public int kthSmallest(TreeNode root, int k) {
3 Deque<TreeNode> stack = new ArrayDeque<>();
4 TreeNode cur = root;
5 int count = 0;
6 while (cur != null || !stack.isEmpty()) {
7 while (cur != null) {
8 stack.push(cur);
9 cur = cur.left;
10 }
11 cur = stack.pop();
12 count++;
13 if (count == k) return cur.val;
14 cur = cur.right;
15 }
16 return -1;
17 }
18}