Kth Smallest Element in a BST
Problem Statement
Given the root of a Binary Search Tree and an integer k, return the kth smallest value among all nodes in the tree. The tree follows the BST property, so every left subtree value is smaller than the node and every right subtree value is larger.
Input
The root pointer of a BST and a positive integer k using one-based order.
Output
An integer value: the kth smallest node value in sorted order.
Constraints
- •
1 <= number of nodes <= 10^4 - •
0 <= Node.val <= 10^4 - •
1 <= k <= number of nodes - •
All Node.val values are unique
Examples
Example 1
root = [3,1,4,null,2], k = 1
1Example 2
root = [5,3,6,2,4,null,null,1], k = 3
3Learning Objectives
- Use inorder traversal as the sorted-order stream of a BST.
- Stop traversal as soon as the **kth** node is visited.
- Compare recursive counter and iterative stack implementations.
- Discuss subtree-count augmentation for frequent order-statistic queries.
Intuition
Pattern Recognition
The technique is inorder order-statistic traversal. The signal is a BST plus a rank request such as kth smallest. In a BST, inorder traversal visits values in ascending order, so the problem becomes streaming the sorted sequence until the kth item appears.
The common trap is building a full list when the answer may arrive early. Both the recursive counter and iterative stack versions can stop as soon as the counter reaches k. For frequent queries on a changing or reused tree, the follow-up is to augment each node with its subtree size so you can jump left, return current, or jump right in O(h) per query.
Common mistakes
- ×Using preorder or level order and losing the sorted property.
- ×Treating **k** as zero-based even though the problem uses one-based rank.
- ×Traversing the entire tree after the answer has already been found.
- ×Forgetting that a balanced BST gives small stack height but a skewed BST can use linear stack space.
Algorithm Explanation
Key idea
Inorder means left subtree, current node, right subtree. For a BST, that exact order is sorted ascending. Count nodes as they are visited in inorder order and stop when the count reaches k.
Recursion walkthrough
Use [5,3,6,2,4,null,null,1] with k = 3. Inorder first walks down to 1, visits it as count 1, then returns to 2 as count 2. The next inorder node is 3, so count becomes 3 and the answer is 3. The traversal does not need to visit 4, 5, or 6.
The iterative stack simulates the same call stack. It pushes 5, 3, 2, 1 while going left. It pops 1, then 2, then 3; the third pop is the answer.
Algorithm
- Traverse the BST in inorder order.
- Each time a node is visited, decrement a remaining counter or increment a visited count.
- When the visited node is the kth one, record or return its value immediately.
- Avoid exploring the remaining right-side work after the answer is known.
- For frequent rank queries, store subtree sizes on nodes and compare k with the left subtree size at each step.
Solutions
Solution 1: Recursive inorder with counter
Use this when recursion is acceptable and you want the shortest explanation of the BST sorted-order property.
Perform inorder DFS and keep a remaining counter. Each visited node consumes one rank. When the remaining count becomes 0, store the value and let later recursive frames return without extra work.
Step-by-step
- Store k in a mutable remaining counter.
- Recursively visit the left subtree first.
- If the answer was already found, return immediately.
- Visit the current node by decrementing the counter.
- When the counter reaches 0, save the current value.
- Otherwise continue into the right subtree.
O(h + k)
O(h)
Early exit visits only the path to the first node plus the first **k** inorder nodes; recursion stack height is **h**.
Java implementation
Solution 2: Iterative inorder with explicit stack
Use this when you want to avoid recursion or make the early-exit mechanics very explicit.
Simulate inorder traversal with a stack. Push the left spine, pop the next smallest node, decrement k, and return immediately when that pop is the desired rank.
Step-by-step
- Start with current = root and an empty stack.
- Push nodes while walking left until current becomes null.
- Pop the stack to visit the next smallest node.
- Decrement the remaining rank and return this value if the rank reaches 0.
- Move to the popped node right child and repeat.
O(h + k)
O(h)
The stack stores at most one root-to-leaf path, and early exit stops after the **kth** pop.
Java implementation
Dry Run
Sample input
root = [5,3,6,2,4,null,null,1], k = 3. Track the inorder visits until the answer appears.
| visit order | node visited | remaining after visit | action |
|---|---|---|---|
| 1 | 1 | 2 | not enough nodes visited yet |
| 2 | 2 | 1 | continue inorder |
| 3 | 3 | 0 | return **3** immediately |
Because inorder over a BST is sorted, the third visited node is exactly the third smallest value.
Interview Tips
Lead with the BST invariant: inorder is sorted. Then mention early exit so you do not look like you are dumping every value into an array. If the interviewer asks about many kth queries, propose storing a subtree node count at each node. The rank of the current node is leftSize + 1, which tells you whether to go left, return current, or go right with an adjusted k.
Likely follow-ups
- How would you support many **kth** smallest queries efficiently?
- How would insertions and deletions update subtree counts?
- How would you find the **kth** largest element instead?
- What changes if duplicate values are allowed?
Similar Problems
Key Takeaways
- Inorder traversal of a BST is the sorted sequence of values.
- The **kth** smallest value is the **kth** inorder visit.
- Early exit avoids unnecessary traversal after the answer is found.
- Subtree sizes turn a repeated rank query into an order-statistic search.