Given the root of a binary search tree and an integer k, return the k-th smallest value in the tree (1-indexed).
In a BST, an in-order traversal visits values in ascending order, so the k-th value produced by an in-order walk is the answer.
The tree is given as a level-order array where null marks a missing child: [3, 1, 4, null, 2].
Example
In-order is [1,2,3,4]; the 1st smallest is 1.
Constraints
- The number of nodes in the tree is n.
- 1 <= k <= n <= 10^4
- 0 <= Node.val <= 10^4
Intuition
In a binary search tree an in-order traversal (left, node, right) visits values in ascending order. So the most direct solution does a full in-order walk into an array and returns the element at index k - 1.
function kthSmallest(root, k) {
const sorted = [];
// In-order traversal of a BST yields values in ascending order.
const inorder = (node) => {
if (!node) return;
inorder(node.left);
sorted.push(node.val);
inorder(node.right);
};
inorder(root);
return sorted[k - 1]; // 1-indexed
}This is O(n) time, but it always walks the entire tree and builds a full array even when k is tiny. Can we do better?
The key observation: we don't need the whole sorted sequence — only its k-th element. Walk in-order but count as we go and stop the moment the count hits `k`. Using an explicit stack makes the early exit clean: dive left pushing nodes, then pop-and-count; the k-th pop is the answer.
The lane below is the in-order output sequence of the BST [5, 3, 6, 2, 4, null, null, 1] — i.e. [1, 2, 3, 4, 5, 6] — with the counter walking it; we stop at k = 3:
in-order output of the BST: [1, 2, 3, 4, 5, 6], counting up to k = 3
Dive to the leftmost node (1). First pop: count 1, not yet k.
Next in-order value. count 2 < 3, keep going.
Third pop: count reaches k. Return 3 — the rest of the tree is never visited.
Values 4, 5, 6 are never popped: the O(h + k) early exit beats walking all n nodes.
Optimization
In-order traversal with early stop
An in-order walk of a BST yields values in ascending order, so the k-th value it emits is the answer. Use an explicit stack: go left as far as possible, then pop and count; the moment the count reaches k, that node's value is the result — no need to finish the traversal.
O(h + k) time (descend to the leftmost, then pop k nodes), O(h) space for the stack.
function kthSmallest(root, k) {
const stack = [];
let curr = root;
let count = 0;
while (curr || stack.length) {
// Dive to the leftmost unvisited node.
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
// This pop is the next-smallest value in order.
if (++count === k) return curr.val;
curr = curr.right;
}
return -1; // unreachable given 1 <= k <= n
}Complexity analysis
Time complexity: O(h + k). Here's why:
- The walk descends to the leftmost node — O(h) pushes.
- Then it pops in-order until the count reaches
k— O(k) more pops.
So O(h + k), which beats the brute force's full O(n) traversal when k is small.
Space complexity: O(h). Here's why:
- The explicit stack holds at most one root-to-leaf path at a time — O(h).
O(log n) balanced, O(n) for a degenerate tree. No full array of values is built.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| root = [8]8k = 1 | 8 | Single node, k = 1. |
| root = [4,2,6]246k = 1 | 2 | k = 1 returns the leftmost (smallest) value. |
| root = [4,2,6]246k = 3 | 6 | k at the maximum returns the largest value. |
| root = [6,4,8,2,5,7,9]2456789k = 4 | 6 | In-order [2,4,5,6,7,8,9]; the 4th is the root, 6. |
| root = [20,10,30,5,15,25,35]5101520253035k = 5 | 25 | In-order [5,10,15,20,25,30,35]; the 5th is 25. |
Try it yourself
Write your solution against the real judge before checking the reference.