Kth Smallest Element in a BST: In-Order Traversal with Early Exit
Find the kth smallest value in a binary search tree with an in-order traversal that counts down and stops early — code, walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A binary search tree hides a sorted list in plain sight. Every node's left subtree is smaller and its right subtree is larger, which means one specific walk — left, node, right — visits values in ascending order. That single fact turns "find the kth smallest" from a sorting problem into a counting problem.
The trick worth internalizing is not just that in-order traversal is sorted, but that you can stop the moment you've counted k nodes. You never need to finish the tree. For a small k on a large tree, that's the difference between touching a handful of nodes and walking all of them.
The problem
Given the root of a binary search tree and an integer k, return the kth smallest value in the tree. k is 1-indexed, so k = 1 asks for the minimum.
Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
Output: 3 // in-order order is 1, 2, 3, 4, 5, 6 → the 3rd value is 3The values aren't stored in sorted order in the tree structure — but an in-order traversal reads them in sorted order. The 3rd node that traversal touches is the answer.
The brute force baseline
The most direct approach ignores the early-exit opportunity: do a full in-order traversal, dump every value into an array, then index into it.
function kthSmallest(root, k) {
const values = [];
const inorder = (node) => {
if (!node) return;
inorder(node.left);
values.push(node.val); // collects the whole tree, sorted
inorder(node.right);
};
inorder(root);
return values[k - 1];
}This is correct and clean, and for a BST the array comes out already sorted — no explicit sort needed. But it does too much work. If the tree has 100,000 nodes and k = 2, you still walk all 100,000 nodes and allocate an array to match, only to read values[1]. The traversal has no reason to keep going once it has seen enough.
The key insight: count down and bail out
You don't need the whole sorted sequence — you need its kth entry. So instead of collecting values, count them off as the in-order walk visits each node, and quit the instant the count reaches the target.
Seed a counter with k. On every in-order visit, decrement it. When it hits zero, the node you're standing on is the kth smallest — capture it and unwind. A closure-captured ans flag, checked at the top of every recursive call, lets outstanding frames return immediately instead of continuing the traversal.
This is the in-order traversal pattern with an early exit bolted on: the sorted order comes free from the BST shape, and the countdown gives you a precise place to stop.
The optimal solution
This is exactly the algorithm the visualizer steps through: a recursive helper that shares ans and count by closure, so every frame reads and writes the same two variables.
var kthSmallest = function (root, k) {
let ans = null;
let count = k;
let traversal = (curr) => {
if (ans != null) return; // answer found — stop descending
curr.left && traversal(curr.left); // in-order: left subtree first
--count; // visit curr (this is one node in sorted order)
if (count == 0) {
ans = curr.val; // kth visit — lock it in
}
curr.right && traversal(curr.right); // then the right subtree
};
traversal(root);
return ans;
};Three details carry the whole solution:
if (ans != null) returnat the top is the early exit. Once a deeper frame setsans, every remaining call returns without work, so the walk stops as soon as the kth node is found.--countsits between the left and right recursion. That placement is the in-order visit point — it fires after the entire left subtree is done and before any right subtree, which is exactly when nodes appear in sorted order.count == 0fires exactly once. After it setsans, the counter keeps decrementing in ancestor frames and goes negative, but the equality check never triggers again, so the first (and correct) answer stays put.
Walkthrough
Tracing root = [5,3,6,2,4,null,null,1], k = 3. The counter starts at 3 and drops by one on each in-order visit.
| # | Call | What happens | count | ans |
|---|---|---|---|---|
| 1 | traversal(5) | ans null; has left → descend to 3 | 3 | null |
| 2 | traversal(3) | ans null; has left → descend to 2 | 3 | null |
| 3 | traversal(2) | ans null; has left → descend to 1 | 3 | null |
| 4 | traversal(1) | no left; --count; 2 ≠ 0; no right; return | 2 | null |
| 5 | back in traversal(2) | --count; 1 ≠ 0; no right; return | 1 | null |
| 6 | back in traversal(3) | --count; 0 → ans = 3; right child 4 guards out; return | 0 | 3 |
| 7 | back in traversal(5) | --count; −1; right child 6 guards out; return | −1 | 3 |
The in-order visit order is 1, 2, 3 — and the third visit, node 3, is the answer. Nodes 4, 6 are never truly visited: when frames 6 and 7 try their right subtrees, the if (ans != null) return guard fires immediately and those calls do nothing. Node 5's frame still runs --count (dropping it to −1), but since count == 0 already fired once, that stray decrement is harmless. Out of six nodes, the answer landed after touching only three.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Full in-order + array | O(n) | O(n) | walks every node, stores every value |
| In-order with early exit | O(H + k) | O(H) | descend H levels to the smallest, then k in-order steps; stack depth is the tree height |
H is the tree's height. You spend O(H) getting down to the leftmost (smallest) node, then O(k) steps advancing through the sorted order until the countdown hits zero. Space is the recursion stack, bounded by H. For a balanced BST that's O(log n + k) time and O(log n) space; for a degenerate, list-shaped tree H approaches n, so both collapse to O(n).
Common mistakes
- Decrementing at the wrong spot.
--countmust sit between the left and right recursion. Put it before the left call and you're counting in pre-order (root-first), which is not sorted, so the kth value is wrong. - Treating
kas 0-indexed.k = 1is the minimum, not the second-smallest. Seedingcount = kand firing oncount == 0gets the 1-indexing right. - Forgetting the early-exit guard. Without
if (ans != null) return, the recursion keeps walking the entire tree after finding the answer. It's still correct, but you've thrown away the whole point — the early stop. - Overwriting a found answer. If you used
if (count <= 0)instead ofcount == 0, later decrements would keep reassigningansto larger nodes. The strict== 0check is what makes exactly one capture happen.
Where this pattern shows up next
BST traversal and the ordering invariant power a whole cluster of tree problems:
- Validate Binary Search Tree — the same in-order-is-sorted idea used to check an ordering instead of exploiting it.
- Search in a Binary Search Tree — the left-smaller/right-larger invariant as a targeted O(H) lookup.
- Insert into a Binary Search Tree — walking the same invariant to find where a new value belongs.
- Lowest Common Ancestor of a Binary Search Tree — using value comparisons to steer a single descent.
You can also step through the Kth Smallest Element in a BST visualizer to watch the countdown, the call stack, and the early-exit guard fire node by node.
FAQ
Why does in-order traversal of a BST give sorted order?
A binary search tree guarantees that every node's left subtree holds smaller values and its right subtree holds larger ones. In-order traversal visits the left subtree, then the node, then the right subtree — so for any node, everything smaller is emitted before it and everything larger after it. Apply that recursively at every node and the full sequence comes out in ascending order, which is why the kth node visited is the kth smallest value.
What is the time complexity of finding the kth smallest element in a BST?
O(H + k), where H is the height of the tree. You spend O(H) descending to the smallest node, then O(k) in-order steps until the countdown reaches zero, and the early-exit guard stops the walk there. For a balanced tree H is O(log n), giving O(log n + k); for a skewed, list-like tree H approaches n, so it degrades to O(n). Space is O(H) for the recursion stack.
Do I have to traverse the entire tree?
No, and that's the main win over the brute-force approach. The countdown starts at k and the traversal quits the instant it reaches the kth node, so you only touch the k smallest values plus the path down to them. A full in-order collection walks all n nodes regardless of k; the early-exit version touches far fewer when k is small relative to the tree size.
How would I handle frequent kth-smallest queries on a changing tree?
For a one-off query the in-order walk is ideal. But if the tree is modified often and you query k repeatedly, augment each node with the size of its subtree. Then you can navigate directly: compare k against the left subtree's size to decide whether the answer is in the left subtree, is the current node, or is the (k − leftSize − 1)th smallest in the right subtree. That turns each query into an O(H) descent without a full traversal, at the cost of maintaining subtree sizes on every insert and delete.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.