Kth Smallest Element in a BST: A Step-by-Step Interview Walkthrough
Kth Smallest Element in a BST is a problem interviewers reach for when they want to see whether you actually understand what a BST gives you, or whether you treat it as "just a tree." Candidates who don't internalize the BST invariant tend to write the brute-force solution: collect every node, sort, return the k-th. That answer works, but it ignores the entire point of using a BST in the first place — the values are already in sorted order, encoded in the structure. The interviewer is watching for whether you exploit that ordering or wastefully recompute it. The signal here is whether you treat a data structure's invariants as algorithmic information.
Order-statistic queries — "find the k-th smallest," "find the median," "find the rank of this value" — are everyday operations in database query engines (SELECT ... ORDER BY ... LIMIT k), percentile computations in monitoring systems, leaderboard implementations, statistical analysis libraries, and quantile sketches in streaming systems. Whenever you're maintaining a dynamic set and need fast rank-based queries, the BST family of structures (and augmented variants like order-statistic trees) is the canonical solution.
Problem Statement
Given the root of a binary search tree and an integer k, return the k-th smallest value among all the nodes in the tree.
You may assume k is always valid, where 1 ≤ k ≤ n (n being the total number of nodes).
Example:
5
/ \
3 6
/ \
2 4
/
1For k = 3, the answer is 3 (the inorder sequence is 1, 2, 3, 4, 5, 6).
1. Clarify Requirements Before Jumping Into Code
Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.
Input: the root of a valid BST and an integer k.
Output: the value of the k-th smallest node.
Details to clarify:
Is k 1-indexed or 0-indexed? Conventionally 1-indexed for this problem — k = 1 returns the smallest value.
Is k guaranteed to be valid? Yes — we don't have to handle out-of-range cases.
Is the tree guaranteed to be a valid BST? Yes.
Are duplicate values allowed? Typically not, but the algorithm works regardless of how duplicates are placed.
How big can the tree be? Worth asking — for very deep trees, recursion depth could matter.
The thing to flag is that we're told the input is a binary search tree specifically, not just any binary tree. The BST invariant — every node's left subtree contains smaller values, right subtree contains larger — is the entire reason this problem has a clean solution.
2. Identify the Category of the Question
A few signals jump out:
The data structure is a BST.
The question asks for an ordered result (the k-th smallest by value).
We need to stop as soon as we've found the answer — there's no benefit to processing more of the tree than necessary.
That combination — BST input, order-based query, early termination — points to inorder traversal with a counter. This is the canonical BST traversal pattern. Same family as "find the median of a BST," "convert BST to sorted doubly linked list," and "validate BST via inorder."
3. Brute Force Solution
The most obvious approach would be to traverse the tree, collect every value into a list, sort the list, and return the k-th element.
public int kthSmallest(TreeNode root, int k) {
List<Integer> values = new ArrayList<>();
collect(root, values);
Collections.sort(values);
return values.get(k - 1);
}
private void collect(TreeNode node, List<Integer> values) {
if (node == null) return;
values.add(node.val);
collect(node.left, values);
collect(node.right, values);
}This is correct, and it works on any binary tree — but that's exactly the problem. It works on any binary tree because it doesn't use the fact that this one is a BST. It pays for sorting (O(n log n) time) and full-list storage (O(n) space) to produce information the BST already encodes implicitly.
The brute force teaches us the key question: what is the BST giving us that we're throwing away? The answer is order. A BST's structure encodes the sorted ordering of its values. Sorting them again is redundant work.
4. Brainstorm More Solutions
Step 1: What does the BST already know about order?
Let's think carefully about the BST invariant. At any node, every value in the left subtree is smaller, and every value in the right subtree is larger. So if I had to list the values in sorted order, where would I start? I'd start with the smallest value, which is the leftmost node — the one you reach by going left as far as possible from the root.
After that, what's next? It's either the leftmost node's parent (if it has no right child of its own), or the leftmost node of the parent's right subtree if it has one. Either way, the pattern is recursive: visit all the smaller values first, then this node, then all the larger values.
That recipe — left subtree, then node, then right subtree — is exactly inorder traversal. And applying it to a BST visits nodes in strictly increasing order of value.
Let me verify on the example:
5
/ \
3 6
/ \
2 4
/
1Inorder traversal goes: visit left subtree of 5 (which means visit left subtree of 3 first, which means visit left subtree of 2, which is left subtree of 1...). Once we bottom out at 1, we backtrack and visit nodes in the order 1, 2, 3, 4, 5, 6. Sorted, as promised.
So the BST gives us sorted order for free — we just have to traverse it inorder.
Step 2: How do we find the k-th value efficiently?
If inorder traversal visits values in sorted order, then the k-th value visited is the k-th smallest. So one approach is: do a full inorder traversal, build the sorted list, return the k-th element.
But that's still O(n) time even though we only need the first k values. We can do better: stop as soon as we've visited k nodes.
So the structure becomes:
Maintain a running count of nodes visited.
Traverse inorder.
When the count hits k, save the current node's value and short-circuit.
count = 0
result = null
inorder(node):
if node is null or result is found: return
inorder(node.left)
count++
if count == k:
result = node.val
return
inorder(node.right)This visits nodes in sorted order, stops as soon as the k-th is found, and never explores any value larger than necessary. Time complexity is O(h + k), where h is the tree's height — the h accounts for descending to the leftmost node, and the k accounts for visiting up to k nodes after that.
Step 3: A small concern about shared state
The recursion above uses external variables (count, result) to communicate across calls. That works but isn't ideal — it makes the function harder to test in isolation and harder to reason about under concurrent use. Let's think about cleaner alternatives:
Option A: pass the counter as a parameter and return early. This is slightly trickier to implement because each recursive call has to thread the counter through the return value, but it avoids shared state entirely.
Option B: use iterative inorder with an explicit stack. This makes the early termination natural — when the counter hits k, we just return out of the loop. It also avoids the recursion stack for very deep trees.
Here's the iterative version:
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
// Walk as far left as possible, pushing nodes onto the stack
while (node != null) {
stack.push(node);
node = node.left;
}
// Pop and "visit" the smallest unvisited node
node = stack.pop();
if (--k == 0) return node.val;
// Move to the right subtree to continue inorder
node = node.right;
}
return -1; // unreachable given the problem's guarantees
}This is the same algorithm, just unrolled. Each pop returns the next-smallest unvisited node, so the k-th pop returns the answer. The early return is clean because no state needs to leak out of recursive calls.
I'd lead with the iterative version in an interview if I'm worried about deep trees, or the recursive version if I want maximum clarity. Both are correct; pick the one whose structure you can explain comfortably.
Step 4: A follow-up worth knowing about — augmented BSTs
Interviewers sometimes ask: "What if we needed to support many kthSmallest queries on the same tree, with insertions and deletions interleaved?" The O(h + k) per query starts to hurt when k is large or when we run many queries. Can we do better?
Let's think about what makes the current algorithm slow. The cost is dominated by walking through k nodes in sorted order — we have to count nodes one at a time to know when we've hit the k-th. That feels wasteful.
What would let us skip the counting? If, at any node, we already knew how many nodes were below it, we wouldn't need to count them — we'd just compare numbers.
So the question becomes: how do we make sure every node knows its subtree size?
The naive answer would be to compute subtree sizes on demand each time we need them — but computing a node's subtree size requires visiting every descendant, which is O(n) per node. We've just moved the cost from one place to another.
The better answer is to store the subtree size as a field on each node. Then reading it is O(1). The cost shifts from query time to insertion and deletion time — when we add or remove a node, we have to update the size field of every ancestor on the path from the new node to the root. That's O(h) extra work per insertion or deletion. We've traded O(h) write overhead for O(h) per-query reads, which is a great deal when reads outnumber writes.
This pattern has a name: augmenting a data structure. We're storing extra metadata at each node beyond what the basic structure requires, so that derived queries become fast. Augmented BSTs (sometimes called order-statistic trees) are the canonical solution to "find the k-th smallest in a dynamic set."
Step 5: Complexity
For the basic inorder approach: the algorithm walks down the leftmost path (O(h) work), then visits up to k nodes before stopping. Total time: O(h + k). For balanced trees this is O(log n + k); for skewed trees it's O(n + k) in the worst case.
Space is O(h) for either the recursion stack or the explicit stack. Both versions are space-equivalent.
The brute force was O(n log n) time and O(n) space. The inorder version is strictly better on every axis.
5. Discuss Trade-Offs Between Solutions
Approach | Time | Space | When I'd use it |
Collect all values, sort | O(n log n) | O(n) | Never — wastes the BST property |
Recursive inorder with counter | O(h + k) | O(h) | Default interview answer — cleanest expression of the idea |
Iterative inorder with stack | O(h + k) | O(h) | When the tree might be deep enough to risk stack overflow, or when early termination needs to be very explicit |
Augmented BST with subtree sizes | O(h) per query | O(n) tree overhead | Production code with many repeated rank queries; mention as a follow-up |
The recursive inorder with early termination is the standard interview answer. The iterative version is a strong second choice. The augmented BST is a follow-up that shows you can think beyond the basic solution.
6. Pseudocode
count = 0
result = unset
kthSmallest(root, k):
inorder(root, k)
return result
inorder(node, k):
if node is null or result is set: return
inorder(node.left, k)
count++
if count == k:
result = node.val
return
inorder(node.right, k)7. Edge Cases
Things to verify before claiming we're done:
Single-node tree → inorder visits the one node; k = 1 returns its value. ✓
k = 1 (smallest) → algorithm bottoms out at the leftmost node and returns immediately.
k = n (largest) → algorithm traverses the entire tree before returning.
Highly unbalanced (skewed) tree → recursion depth is O(n) in the worst case; the iterative version avoids stack overflow risk.
Tree where the leftmost path is very long → no special handling needed; the algorithm naturally descends and processes nodes in order.
The problem guarantees k is valid, so we don't need to handle out-of-range cases. If we did, we'd return some sentinel or throw an exception after exhausting the traversal without hitting k.
8. Full Code
import java.util.*;
public class KthSmallestInBST {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
// Recursive inorder with a counter — O(h + k) time, O(h) space.
// The inorder traversal of a BST visits nodes in sorted order,
// so the k-th node visited is the k-th smallest value.
private static int count = 0;
private static int result = 0;
public static int kthSmallest(TreeNode root, int k) {
count = 0;
result = 0;
inorder(root, k);
return result;
}
private static void inorder(TreeNode node, int k) {
if (node == null || count >= k) return;
inorder(node.left, k);
count++;
if (count == k) {
result = node.val;
return;
}
inorder(node.right, k);
}
// Iterative inorder with an explicit stack — same complexity,
// but easier to terminate early and safer for very deep trees.
public static int kthSmallestIterative(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
// Descend to the leftmost unvisited node, stacking along the way
while (node != null) {
stack.push(node);
node = node.left;
}
// Pop the next node in sorted order
node = stack.pop();
if (--k == 0) return node.val;
// Continue inorder with this node's right subtree
node = node.right;
}
return -1; // unreachable given the problem's guarantees
}
}9. Test the Code
TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(6);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.left.left.left = new TreeNode(1);
// Inorder sequence: 1, 2, 3, 4, 5, 6
System.out.println(kthSmallest(root, 1)); // 1
System.out.println(kthSmallest(root, 3)); // 3
System.out.println(kthSmallest(root, 6)); // 6
// Single node
TreeNode single = new TreeNode(42);
System.out.println(kthSmallest(single, 1)); // 42
// Skewed right
TreeNode skewed = new TreeNode(1);
skewed.right = new TreeNode(2);
skewed.right.right = new TreeNode(3);
System.out.println(kthSmallest(skewed, 2)); // 2
// Verify iterative produces the same answers
System.out.println(kthSmallestIterative(root, 1)); // 1
System.out.println(kthSmallestIterative(root, 6)); // 6These hit the meaningful cases: smallest, middle, and largest within a balanced-ish tree; a single-node tree; a skewed tree where the algorithm still works correctly; and a sanity check that the iterative version matches the recursive one.
10. Key Lessons
When a problem gives you a specific data structure, ask what that structure guarantees that a generic structure doesn't. A "binary tree" gives you nothing about ordering. A "binary search tree" gives you sorted order for free — but only if you exploit it.
Inorder traversal of a BST visits nodes in increasing order of value. This single fact powers a whole family of problems: kth smallest, kth largest (mirror it), median, range queries, predecessor/successor, BST validation. Recognize when the problem is asking for an order-based answer and reach for inorder.
Early termination matters. If you only need the first k results, don't process all n. Even O(n) algorithms can be slow when n is large and k is small.
When recursion needs to share state (a counter, a result), pause and consider whether iteration would be cleaner. The iterative version of inorder traversal is one of the few cases where the iterative form is genuinely competitive with the recursive form on clarity.
Augmenting nodes with auxiliary information (subtree sizes, balance factors, parent pointers) lets you trade write-time cost for read-time speed. Worth knowing as a follow-up upgrade, and is great opportunity to show off your ability to think about production-level systems.
The thing that makes Kth Smallest Element in a BST click isn't the inorder traversal — most candidates know how to do an inorder traversal. It's the recognition that the BST's structure already encodes the answer you need, and your job is to read it out efficiently rather than rebuild it. Once you train yourself to ask "what does this data structure already know?", every order-based query problem starts to feel like a walk instead of a search.
Good Luck and Happy Coding!
Comments