March 24
Kth Smallest Element in a BST
How to use inorder traversal to exploit the BST ordering and stop as soon as the counter reaches k.
Trees Intermediate 15 min TypeScript
Given the root of a binary search tree and an integer k, return the kth smallest value in the tree.
Treat k as 1-based.
Example:
Input:
root = [3,1,4,null,2]
k = 1
Output:
1
What to notice before coding
- In a BST, inorder is already sorted. There is no need to sort afterward.
- `k` is 1-based, so the first real inorder visit can already be the answer.
- If you only need the kth value, you can stop early.
Common mistakes
- treating `k` as if it were 0-based
- ignoring the BST property and traversing as if it were just any tree
Step 1 - Remember what a BST gives you for free
In a BST:
- everything on the left is smaller
- everything on the right is larger
That means there is a traversal that already returns values in order.
That traversal is inorder:
- left
- current node
- right
Step 2 - Write the most direct baseline
A good baseline is:
- do full inorder
- store the values in an array
- return
values[k - 1]
It works and makes the ordering property visible.
Step 3 - Ask what really needs to be stored
The problem does not ask for all values in sorted order.
It only asks for:
- the kth visited value
So a whole array may be more state than you need.
Step 4 - Count during inorder and stop early
Instead of storing everything, you can:
- keep a counter
- increment it on every real visit
- stop when the counter reaches
k
That turns the BST property into a direct answer.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function kthSmallest(root, k) {
// root is an object like { val: number, left: ..., right: ... } or null
// your solution here
return null
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(h + k)
Space: O(h)
Solution 1 - Full inorder plus array
Good baseline because it makes the natural BST ordering explicit.
export function kthSmallest(root, k) {
const values = []
function inorder(node) {
if (node === null) {
return
}
inorder(node.left)
values.push(node.val)
inorder(node.right)
}
inorder(root)
return values[k - 1] ?? null
}It works.
But it stores more state than the problem really needs.
Solution 2 - Inorder with counter and early stop in DFS
Now the traversal stops as soon as it reaches the answer.
export function kthSmallest(root, k) {
let seen = 0
let result = null
function inorder(node) {
if (node === null || result !== null) {
return
}
inorder(node.left)
if (result !== null) {
return
}
seen += 1
if (seen === k) {
result = node.val
return
}
inorder(node.right)
}
inorder(root)
return result
}The strong insight here is that inorder is not just a nice traversal. It is how you read a BST in sorted order.
What to say in the interview
A strong short explanation would be:
Because the structure is a BST, inorder visits values in increasing order. The baseline does full inorder and returns
values[k - 1]. The better version only counts visited nodes and stops as soon as it reaches the kth one, without storing everything, so the traversal only goes as far as the answer forces it to go.
That shows that you:
- used a property of the structure, not brute force
- made it clear why inorder is the right traversal
- avoided unnecessary state
When this pattern shows up again
This pattern comes back when you need to:
- read a BST in increasing order
- find a relative position inside an ordered structure
- turn a traversal into a counter
- decide when early stop is worth it in
DFS
The point is not memorizing
kthSmallest.
The point is learning when the ordering is already embedded in the structure itself.