Kth Smallest Element in a BST
Asked at Google, Meta, Amazon, Microsoft, Apple, Uber
Problem
Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) of all the node values in the BST.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
In-order traversal of a BST visits nodes in sorted order (left → root → right).
Do an in-order traversal and stop after visiting k nodes. The kth node visited is the answer.
You don't need to store all values — just count nodes as you visit them and stop at k.
Alternative: store the count of nodes in each subtree. If left subtree has >= k nodes, recurse left. If left + 1 = k, return root. Otherwise recurse right with k - leftCount - 1.
Visual walkthrough for BST: 3
/ \n 1 4
\n 2
In-order: 1, 2, 3, 4. k=2 → second element is 2.
Visit 1 (count=1), visit 2 (count=2=k) → return 2.
Edge cases: k = 1 (leftmost node), k = n (rightmost node), single node tree.
Optimal Approach
In-order traversal:
Step 1: Define inorder(node) that yields values in sorted order.
Step 2: Iterate through the generator, decrementing k each time.
Step 3: When k = 0, return the current value.
Alternatively, iterative inorder with explicit stack:
Push all left children. Pop (this is next smallest). Decrement k. If k=0, return. Push all left children of the right child.
Time: O(k + h). Space: O(h).
What Trips People Up in Real Interviews
Doing a full in-order traversal. You can stop after k nodes — don't traverse the entire tree.
Confusing "kth smallest" with "kth largest." Smallest means leftmost in a BST. For kth largest, you could reverse the traversal or use n - k + 1.
Not handling the case where k is larger than the number of nodes. The problem guarantees valid k, but in an interview, clarify this.
Using a sort instead of BST properties. Sorting all values is O(n log n). In-order traversal is O(k + h) where h is tree height.
Using iterative in-order traversal but forgetting to push all left children before processing. The pattern is: push all left descendants, pop and process, then push all left of the right child.
Solution Code
def kthSmallest(root, k):
def inorder(node):
if not node:
return
yield from inorder(node.left)
yield node.val
yield from inorder(node.right)
for val in inorder(root):
k -= 1
if k == 0:
return valFrequently Asked Questions
What is the Kth Smallest Element in a BST problem?
Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) of all the node values in the BST.
How do you solve Kth Smallest Element in a BST?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Kth Smallest Element in a BST?
Kth Smallest Element in a BST is asked at Google, Meta, Amazon, Microsoft, Apple, Uber. It is a medium difficulty problem.
What are common mistakes on Kth Smallest Element in a BST?
- Doing a full in-order traversal. You can stop after k nodes — don't traverse the entire tree.
- Confusing "kth smallest" with "kth largest." Smallest means leftmost in a BST. For kth largest, you could reverse the traversal or use n - k + 1.
- Not handling the case where k is larger than the number of nodes. The problem guarantees valid k, but in an interview, clarify this.
- Using a sort instead of BST properties. Sorting all values is `O(n log n)`. In-order traversal is `O(k + h)` where h is tree height.
- Using iterative in-order traversal but forgetting to push all left children before processing. The pattern is: push all left descendants, pop and process, then push all left of the right child.