Kth Smallest Element in a BST
Problem
root of a binary search tree and an integer
k (1-indexed). Return the k-th smallest value stored in the tree, i.e. the
value that would sit at position k if all values were sorted ascending.root = [3,1,4,null,2], k = 1Output1[5,3,6,2,4,null,null,1], k=3Output31 ≤ k ≤ n ≤ 104 · 0 ≤ Node.val ≤ 104 · Follow-up: what if the BST is modified often and kthSmallest is called often?
Try it yourself
class Solution {
public int kthSmallest(TreeNode root, int k) {
}
}
Instinct The tree is a BST? Its in-order walk is a sorted list and every node splits the search space - think "sorted array in tree form", not "visit everything".
Memory hack Left is less, right is more, in-order reads the sorted score - and every node lives inside a (low, high) fence set by its ancestors.
Open the Binary Search Tree & In-order guide →Approaches
Brute ForceFull In-order into a List
O(n)Space O(n)Recursively collect every value in in-order, which produces a sorted list,
then return list.get(k - 1). Correct, but it visits and stores all n
nodes even when k = 1.
public int kthSmallest(TreeNode root, int k) { List<Integer> vals = new ArrayList<>(); inorder(root, vals); return vals.get(k - 1); } private void inorder(TreeNode node, List<Integer> vals) { if (node == null) return; inorder(node.left, vals); vals.add(node.val); inorder(node.right, vals); }
Simplest to write; wastes time and memory when k is small.
BetterRecursive In-order with Counter
O(h + k)Space O(h)Instead of storing values, count them. Each visit decrements
k; when it hits 0 the current node is the answer and every pending call
returns immediately. We descend h levels and then visit about
k nodes.
private int count, result; public int kthSmallest(TreeNode root, int k) { count = k; inorder(root); return result; } private void inorder(TreeNode node) { if (node == null || count == 0) return; inorder(node.left); if (count == 0) return; // answer already found on the left if (--count == 0) { result = node.val; return; } inorder(node.right); }
No list and early exit, but relies on mutable fields and recursion depth.
OptimalIterative In-order with Stack
O(h + k)Space O(h)Run the classic stack-based in-order loop and return the moment the
k-th node is popped. No shared state, no recursion, and the early
return makes the stop condition trivial.
public int kthSmallest(TreeNode root, int k) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); if (--k == 0) return curr.val; curr = curr.right; } return -1; // unreachable for valid k }
Same bounds as Better, self-contained and safe on deep trees.
size(left)+1 and go left or right: O(h) per query, updated on insert/delete.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Full In-order into a List | O(n) | O(n) |
| Better | Recursive In-order with Counter | O(h + k) | O(h) |
| Optimal | Iterative In-order with Stack | O(h + k) | O(h) |
- Off-by-one: k is 1-indexed, so the list answer is
get(k - 1). - Recursive counter without an early-return check keeps walking or overwrites the result.
- Sorting values in a heap/array ignores the free ordering the BST already gives.
- State the BST property first: in-order = sorted.
- Quote time as O(h + k), not just O(n), to show the early exit matters.
- Answer the follow-up with size-augmented nodes (order-statistic tree).