Kth Smallest Element in a BST
The Prompt
Given the `root` of a binary search tree, and an integer `k`, return the `k`-th smallest value (1-indexed) of all the values of the nodes in the tree.
Understanding the Problem
A BST stores its values in sorted order implicitly: an inorder traversal (left, node, right) visits values from smallest to largest. So "k-th smallest" translates directly to "the k-th node an inorder traversal visits".
You do not need the full sorted list. Run the inorder walk with a counter, increment it each time a node is visited, and stop the moment the counter hits k — the rest of the tree never gets touched.
The Interview Flow
Interviewer
How do you find the kth smallest element in a BST?
Candidate
The key property of a BST is that an in-order traversal (left, root, right) visits the nodes in sorted ascending order.
Interviewer
So how can you use that?
Candidate
I can perform an in-order traversal and store the node values in a list. The kth smallest element would then simply be the element at index `k-1` in this sorted list. However, this takes O(n) space and might do more work than necessary if k is small.
Interviewer
Can you optimize it to stop early?
Candidate
Yes. I can perform the in-order traversal iteratively using a stack. I would traverse down the left side, pushing nodes onto the stack. Then, I pop a node, "visit" it by decrementing k, and check if k has reached zero. If it has, that node's value is my answer. Then I move to the right child of the popped node and repeat the process. This way, I stop as soon as I've found the kth element.
Interviewer
That's a great iterative approach. It's efficient. Please code it.
Why does inorder with early exit stay cheap?
The invariant comes straight from the BST property: when the traversal visits a node, every value in its left subtree (all smaller) has already been visited, and nothing larger has been. So the visit counter equals the rank of the current value, and the k-th visit is exactly the k-th smallest — stopping there is safe.
The walk descends to the leftmost node in O(h) and then performs k visits, giving O(h + k) time and O(h) stack space. For a balanced tree that is O(log n + k), well under the O(n log n) of extracting and sorting all values.
Iterative In-order Traversal with a Stack
- Initialize an empty stack.
- Initialize a pointer `curr` to the `root`.
- Start a `while` loop that continues as long as `curr` is not null or the stack is not empty.
- Inside the loop, have another `while` loop that pushes `curr` onto the stack and moves `curr` to its left child (`curr = curr.left`) as long as `curr` is not null. This finds the smallest unvisited node.
- Once the inner loop is done, pop a node from the stack. Let this be `node`.
- Decrement `k`. This represents "visiting" the node in sorted order.
- If `k` becomes 0, we have found our target. Return `node.val`.
- Move to the right subtree to find the next smallest elements: `curr = node.right`.
- The loop continues until the kth element is found.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function kthSmallest(root, k) {
const stack = [];
let curr = root;
while (curr || stack.length > 0) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
k--;
if (k === 0) {
return curr.val;
}
curr = curr.right;
}
}Explanation
Find the 3rd smallest in the BST [5, 3, 6, 2, 4] — the inorder walk counts visits and stops at k = 3.
1Descend the left spine 5 → 3 → 2. Node 2 has no left child, so it is visited first: count = 1. Smallest value confirmed.
2Unwind to 2's parent: visit 3, count = 2. Its right subtree (holding 4) comes next in sorted order.
3Visit 4: count = 3 = k — stop and return 4. Nodes 5 and 6 are never visited; the traversal ends early.
Complexity Analysis
TIME
O(h + k)
SPACE
O(h)
Finished working through this one?
Mark it complete to track it on your Data Structures path.