#230 Kth Smallest Element in a BST
frequently reported atUberOracleBloombergAmazonMicrosoftGoogle
the problem
In plain words
Return the kth smallest value (1-indexed) among all node values of the BST.
in root = [3,1,4,null,2], k = 1
out 1
in root = [5,3,6,2,4,null,null,1], k = 3
out 3
- 1 ≤ k ≤ n ≤ 10⁴
- 0 ≤ Node.val ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBST propertyIterative tree DFS (explicit stack)
Inorder pops values in ascending order. The kth pop is the answer — stop there.
solutions
From brute force to optimal
Collect all values sorted, return index k − 1.
- Inorder traversal into a list.
- Return list.get(k − 1).
Visits every node even when k is small.
The list.
class Solution { public int kthSmallest(TreeNode root, int k) { List<Integer> sorted = new ArrayList<>(); collect(root, sorted); // inorder of a BST is sorted return sorted.get(k - 1); } private void collect(TreeNode node, List<Integer> out) { if (node == null) return; collect(node.left, out); out.add(node.val); collect(node.right, out); }}Explicit-stack inorder; count pops; return on the kth.
- Push the left spine.
- Pop → k−−; if k == 0 return the value.
- Move to the right child and repeat.
Walk down the left spine once, then k pops (each with amortized O(1) pushes).
The stack holds at most one root-to-leaf spine.
class Solution { public int kthSmallest(TreeNode root, int k) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while (true) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); // the next smallest value if (--k == 0) return cur.val; // the k-th one we popped cur = cur.right; } }}Dry run
in the room
How to say it in the interview
talk track
- Say "inorder of a BST is sorted" first — then the rest is just stopping early.
traps
- Off by one: k is 1-indexed, so the first pop is k = 1, and the list version reads
get(k − 1). - Using preorder or level order — only inorder gives a BST's values in ascending order.
- A recursive counter kept in a local
intparameter: each call gets its own copy, so the count is lost. Use a field or an explicit stack.
what they ask next
Follow-ups
The BST is modified often and you query kth smallest often?
Store a subtree size in every node (an order-statistic tree). Then compare k with left.size to go left, stop, or go right with k − left.size − 1: O(h) per query, and sizes update along the insert/delete path.
before you submit
Edge cases to test
- k = 1 → the leftmost node.
- k = n → the rightmost node; you end up visiting every node.
- A left-skewed tree → the first push loop goes n deep, so the stack holds n nodes.
practise next
Similar problems
- #173Binary Search Tree IteratorMediumin BST
- #94Binary Tree Inorder TraversalEasyin Traversals
- #215Kth Largest Element in an ArrayMediumin Heaps