You're given the root of a binary search tree (BST) and a number k. Return the value of the k-th smallest element, counting from 1. A BST is a binary tree where, for every node, all values in its left subtree are smaller and all values in its right subtree are larger — which means the tree already encodes a sorted order, you just have to read it out. Think of a leaderboard stored as a BST: "who's in 3rd place?" is exactly this question.
type TreeNode = {
val: number;
left: TreeNode | null;
right: TreeNode | null;
};
// k is 1-indexed: k = 1 asks for the smallest value, k = 2 the second smallest, ...
function binarySearchTreeKthSmallest(root: TreeNode | null, k: number): number;// 5
// / \
// 3 7
// / \ \
// 2 4 8
//
// Sorted order (in-order): 2, 3, 4, 5, 7, 8
binarySearchTreeKthSmallest(root, 1); // 2 — the smallest// 5
// / \
// 3 7
// / \ \
// 2 4 8
//
binarySearchTreeKthSmallest(root, 3); // 4 — third smallest
binarySearchTreeKthSmallest(root, 6); // 8 — the largest (size is 6)k is 1-indexed — k = 1 returns the smallest value, not the second-smallest. There is no k = 0.k is always valid — 1 ≤ k ≤ number of nodes. You won't be asked for the 10th smallest of a 6-node tree.{ val, left, right } — missing children are null, not undefined.k-th node you visit in-order is the answer.You'll return the value of the k-th smallest node in a binary search tree by reading the tree out in sorted order and stopping the moment you reach the k-th value.
You have a binary search tree — a tree where every node's left subtree holds only smaller values and its right subtree only larger ones. Someone asks: "what's the 3rd smallest value in here?" You could sort all the values and grab the third, but the tree already knows its own order. The trick is to read it out the right way.
The one fact that unlocks everything: an in-order traversal of a BST — visit the left subtree, then the node, then the right subtree — produces the values in ascending sorted order. So the k-th node you visit in-order is the k-th smallest value. You don't need to sort anything; you just need to walk the tree in the correct order and count.
A BST stores order implicitly. The smallest value is the leftmost node; the largest is the rightmost. Everything in between falls into place if you always finish the left subtree before touching a node, and finish the node before touching its right subtree. That left-node-right discipline is in-order traversal, and on a BST it spits out a sorted sequence.
So the whole job reduces to: produce the in-order sequence, and return its k-th entry. The only real decision is how much of that sequence you bother to produce.
The most direct version takes the insight literally: walk the entire tree in-order, push every value into an array, then return index k - 1 (the array is 0-indexed, but k is 1-indexed).
function binarySearchTreeKthSmallest(root, k) {
const values = [];
function inorder(node) {
if (node === null) return;
inorder(node.left); // 1. all smaller values first
values.push(node.val); // 2. then this node
inorder(node.right); // 3. then all larger values
}
inorder(root);
return values[k - 1]; // k is 1-indexed; arrays are 0-indexed
}This is correct. The values array comes out fully sorted, and values[k - 1] is exactly the k-th smallest. For an interview answer it would pass every test.
The weakness is that it always does the maximum amount of work. If the tree has a million nodes and you ask for k = 2, this still visits all million nodes and allocates an array of a million entries before handing back the second one. You walked the entire tree to read the front of the line. We're throwing away everything past index k - 1 — so why compute it?
The fix is to stop the instant you've seen k values. We still walk in-order, but instead of collecting into an array, we keep a running count and return the moment count hits k. An explicit stack lets us bail out of the walk early — something a plain recursive helper can't do cleanly, since a return only unwinds one frame.
function binarySearchTreeKthSmallest(root, k) {
const stack = [];
let node = root;
let count = 0;
while (node !== null || stack.length > 0) {
// 1. Dive as far left as possible, stacking nodes on the way down.
while (node !== null) {
stack.push(node);
node = node.left;
}
// 2. Pop the next node in sorted order — this is the "visit" step.
node = stack.pop();
count += 1;
if (count === k) return node.val; // 3. The k-th visited node is the answer.
// 4. Move into the right subtree; the outer loop dives left again.
node = node.right;
}
// Unreachable when k is valid (1 ≤ k ≤ size), but a sane fallback.
return -1;
}
module.exports = { binarySearchTreeKthSmallest };The shape is a textbook iterative in-order traversal with one extra line. Take the moving parts in turn.
The stack replaces the call stack. A recursive in-order does left-node-right by leaning on the language's call stack. Here we manage it ourselves with an array. The inner while (node !== null) loop pushes a node and walks to its left child repeatedly — so by the time the left pointer falls off the tree (node === null), the stack holds the path from the current position down to the leftmost unvisited node, with that leftmost node on top.
Popping is the "visit". stack.pop() hands back the smallest unvisited node. That's the in-order visit step — equivalent to the values.push(node.val) line in the naive version, except now it happens lazily, one node at a time, instead of all at once.
count += 1 then the early return. Each pop is one step further along the sorted sequence, so count tracks "how many smallest values we've seen." When count === k, the node we just popped is the k-th smallest, and we return its value immediately — no array, no remaining nodes touched.
node = node.right continues the walk. After visiting a node, the next-larger values live in its right subtree. We set node to the right child and let the outer loop's inner while dive left into it, finding the smallest value greater than the one we just visited. If there's no right child, node becomes null, the inner loop is skipped, and we pop the next node off the stack — which is the correct next-larger ancestor.
The key shift from the naive version: we never build the full array, and we exit as soon as the answer is known. For k = 1 on a left-skewed tree, we dive to the bottom-left node, pop it, and return — touching only the left spine.
Let's find k = 3 in this tree:
5
/ \
3 7
/ \ \
2 4 8
The sorted (in-order) sequence is 2, 3, 4, 5, 7, 8, so the 3rd smallest is 4. Here's the walk, step by step:
start node = 5, stack = [], count = 0
dive left from 5:
push 5 stack = [5], node = 3
push 3 stack = [5,3], node = 2
push 2 stack = [5,3,2], node = null (2 has no left child)
pop 2 stack = [5,3], count = 1 (1 != 3)
node = 2.right = null
dive left from null: (inner loop does nothing)
pop 3 stack = [5], count = 2 (2 != 3)
node = 3.right = 4
dive left from 4:
push 4 stack = [5,4], node = null (4 has no left child)
pop 4 stack = [5], count = 3 (3 === 3) -> return 4
We pop 2 (count 1), 3 (count 2), then 4 (count 3) — and stop. Nodes 5, 7, and 8 are never popped. The right subtree of the root (the 7 / 8 branch) is never even pushed onto the stack. That's the early exit earning its keep: a tree of any size answers k = 3 after touching only the first three nodes in sorted order plus the ancestors on their path.
And here is the left-node-right ordering that the stack is implementing on every node, with the count incrementing in the middle:
k is 1-indexed, arrays are 0-indexed. k = 1 is the smallest. In the naive version that means values[k - 1], not values[k]. In the iterative version, increment count before the comparison and check count === k — if you check before incrementing, or compare against k - 1, you return the wrong node.k-th value is wrong. The node must be counted between its left and right work. Pre-order on this tree gives 5, 3, 2, 4, 7, 8 — counting to 3 there yields 2, not 4.O(n) time and O(n) memory regardless of how small k is. The early-exit walk is O(h + k) time and O(h) memory, where h is the tree height. For small k on a large tree, that's the difference between touching a handful of nodes and touching all of them.node is null and the stack is empty, and an inner loop that pushes every node while walking left. Drop the inner loop and you only ever look at the root's immediate left child — the traversal never reaches the leftmost (smallest) node.k is always valid without a fallback. The problem guarantees 1 ≤ k ≤ size, so a correct walk always returns inside the loop. But if a caller ever passes a k larger than the node count, the loop ends and execution falls through. Return a sentinel (or throw) rather than letting the function return undefined silently.k-th visited value is meaningless. The problem promises a valid BST; don't try to "fix" an invalid one inside this function.O(h) lookups. If you store, on each node, the count of nodes in its subtree, you can find the k-th smallest in O(h) without visiting k nodes: at each node, compare k to the size of the left subtree. If k equals leftSize + 1, this node is the answer; if k ≤ leftSize, go left; otherwise go right with k reduced by leftSize + 1. This pays off when you query the same tree many times — you trade a little bookkeeping on insert/delete for much faster lookups. It turns the BST into an order-statistic tree.k-th largest is the mirror image. Run the traversal as right-node-left instead of left-node-right. That visits values in descending order, so the k-th node you pop is the k-th largest. Same code, swap left and right in the dive and the continue step — no need to compute the size and subtract.kth-smallest, rank-of(value), insert, and delete all in O(log n). This is the data structure behind "what's the median so far?" running-statistics problems and leaderboard ranking systems where the set keeps changing.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You're given the root of a binary search tree (BST) and a number k. Return the value of the k-th smallest element, counting from 1. A BST is a binary tree where, for every node, all values in its left subtree are smaller and all values in its right subtree are larger — which means the tree already encodes a sorted order, you just have to read it out. Think of a leaderboard stored as a BST: "who's in 3rd place?" is exactly this question.
type TreeNode = {
val: number;
left: TreeNode | null;
right: TreeNode | null;
};
// k is 1-indexed: k = 1 asks for the smallest value, k = 2 the second smallest, ...
function binarySearchTreeKthSmallest(root: TreeNode | null, k: number): number;// 5
// / \
// 3 7
// / \ \
// 2 4 8
//
// Sorted order (in-order): 2, 3, 4, 5, 7, 8
binarySearchTreeKthSmallest(root, 1); // 2 — the smallest// 5
// / \
// 3 7
// / \ \
// 2 4 8
//
binarySearchTreeKthSmallest(root, 3); // 4 — third smallest
binarySearchTreeKthSmallest(root, 6); // 8 — the largest (size is 6)k is 1-indexed — k = 1 returns the smallest value, not the second-smallest. There is no k = 0.k is always valid — 1 ≤ k ≤ number of nodes. You won't be asked for the 10th smallest of a 6-node tree.{ val, left, right } — missing children are null, not undefined.k-th node you visit in-order is the answer.You'll return the value of the k-th smallest node in a binary search tree by reading the tree out in sorted order and stopping the moment you reach the k-th value.
You have a binary search tree — a tree where every node's left subtree holds only smaller values and its right subtree only larger ones. Someone asks: "what's the 3rd smallest value in here?" You could sort all the values and grab the third, but the tree already knows its own order. The trick is to read it out the right way.
The one fact that unlocks everything: an in-order traversal of a BST — visit the left subtree, then the node, then the right subtree — produces the values in ascending sorted order. So the k-th node you visit in-order is the k-th smallest value. You don't need to sort anything; you just need to walk the tree in the correct order and count.
A BST stores order implicitly. The smallest value is the leftmost node; the largest is the rightmost. Everything in between falls into place if you always finish the left subtree before touching a node, and finish the node before touching its right subtree. That left-node-right discipline is in-order traversal, and on a BST it spits out a sorted sequence.
So the whole job reduces to: produce the in-order sequence, and return its k-th entry. The only real decision is how much of that sequence you bother to produce.
The most direct version takes the insight literally: walk the entire tree in-order, push every value into an array, then return index k - 1 (the array is 0-indexed, but k is 1-indexed).
function binarySearchTreeKthSmallest(root, k) {
const values = [];
function inorder(node) {
if (node === null) return;
inorder(node.left); // 1. all smaller values first
values.push(node.val); // 2. then this node
inorder(node.right); // 3. then all larger values
}
inorder(root);
return values[k - 1]; // k is 1-indexed; arrays are 0-indexed
}This is correct. The values array comes out fully sorted, and values[k - 1] is exactly the k-th smallest. For an interview answer it would pass every test.
The weakness is that it always does the maximum amount of work. If the tree has a million nodes and you ask for k = 2, this still visits all million nodes and allocates an array of a million entries before handing back the second one. You walked the entire tree to read the front of the line. We're throwing away everything past index k - 1 — so why compute it?
The fix is to stop the instant you've seen k values. We still walk in-order, but instead of collecting into an array, we keep a running count and return the moment count hits k. An explicit stack lets us bail out of the walk early — something a plain recursive helper can't do cleanly, since a return only unwinds one frame.
function binarySearchTreeKthSmallest(root, k) {
const stack = [];
let node = root;
let count = 0;
while (node !== null || stack.length > 0) {
// 1. Dive as far left as possible, stacking nodes on the way down.
while (node !== null) {
stack.push(node);
node = node.left;
}
// 2. Pop the next node in sorted order — this is the "visit" step.
node = stack.pop();
count += 1;
if (count === k) return node.val; // 3. The k-th visited node is the answer.
// 4. Move into the right subtree; the outer loop dives left again.
node = node.right;
}
// Unreachable when k is valid (1 ≤ k ≤ size), but a sane fallback.
return -1;
}
module.exports = { binarySearchTreeKthSmallest };The shape is a textbook iterative in-order traversal with one extra line. Take the moving parts in turn.
The stack replaces the call stack. A recursive in-order does left-node-right by leaning on the language's call stack. Here we manage it ourselves with an array. The inner while (node !== null) loop pushes a node and walks to its left child repeatedly — so by the time the left pointer falls off the tree (node === null), the stack holds the path from the current position down to the leftmost unvisited node, with that leftmost node on top.
Popping is the "visit". stack.pop() hands back the smallest unvisited node. That's the in-order visit step — equivalent to the values.push(node.val) line in the naive version, except now it happens lazily, one node at a time, instead of all at once.
count += 1 then the early return. Each pop is one step further along the sorted sequence, so count tracks "how many smallest values we've seen." When count === k, the node we just popped is the k-th smallest, and we return its value immediately — no array, no remaining nodes touched.
node = node.right continues the walk. After visiting a node, the next-larger values live in its right subtree. We set node to the right child and let the outer loop's inner while dive left into it, finding the smallest value greater than the one we just visited. If there's no right child, node becomes null, the inner loop is skipped, and we pop the next node off the stack — which is the correct next-larger ancestor.
The key shift from the naive version: we never build the full array, and we exit as soon as the answer is known. For k = 1 on a left-skewed tree, we dive to the bottom-left node, pop it, and return — touching only the left spine.
Let's find k = 3 in this tree:
5
/ \
3 7
/ \ \
2 4 8
The sorted (in-order) sequence is 2, 3, 4, 5, 7, 8, so the 3rd smallest is 4. Here's the walk, step by step:
start node = 5, stack = [], count = 0
dive left from 5:
push 5 stack = [5], node = 3
push 3 stack = [5,3], node = 2
push 2 stack = [5,3,2], node = null (2 has no left child)
pop 2 stack = [5,3], count = 1 (1 != 3)
node = 2.right = null
dive left from null: (inner loop does nothing)
pop 3 stack = [5], count = 2 (2 != 3)
node = 3.right = 4
dive left from 4:
push 4 stack = [5,4], node = null (4 has no left child)
pop 4 stack = [5], count = 3 (3 === 3) -> return 4
We pop 2 (count 1), 3 (count 2), then 4 (count 3) — and stop. Nodes 5, 7, and 8 are never popped. The right subtree of the root (the 7 / 8 branch) is never even pushed onto the stack. That's the early exit earning its keep: a tree of any size answers k = 3 after touching only the first three nodes in sorted order plus the ancestors on their path.
And here is the left-node-right ordering that the stack is implementing on every node, with the count incrementing in the middle:
k is 1-indexed, arrays are 0-indexed. k = 1 is the smallest. In the naive version that means values[k - 1], not values[k]. In the iterative version, increment count before the comparison and check count === k — if you check before incrementing, or compare against k - 1, you return the wrong node.k-th value is wrong. The node must be counted between its left and right work. Pre-order on this tree gives 5, 3, 2, 4, 7, 8 — counting to 3 there yields 2, not 4.O(n) time and O(n) memory regardless of how small k is. The early-exit walk is O(h + k) time and O(h) memory, where h is the tree height. For small k on a large tree, that's the difference between touching a handful of nodes and touching all of them.node is null and the stack is empty, and an inner loop that pushes every node while walking left. Drop the inner loop and you only ever look at the root's immediate left child — the traversal never reaches the leftmost (smallest) node.k is always valid without a fallback. The problem guarantees 1 ≤ k ≤ size, so a correct walk always returns inside the loop. But if a caller ever passes a k larger than the node count, the loop ends and execution falls through. Return a sentinel (or throw) rather than letting the function return undefined silently.k-th visited value is meaningless. The problem promises a valid BST; don't try to "fix" an invalid one inside this function.O(h) lookups. If you store, on each node, the count of nodes in its subtree, you can find the k-th smallest in O(h) without visiting k nodes: at each node, compare k to the size of the left subtree. If k equals leftSize + 1, this node is the answer; if k ≤ leftSize, go left; otherwise go right with k reduced by leftSize + 1. This pays off when you query the same tree many times — you trade a little bookkeeping on insert/delete for much faster lookups. It turns the BST into an order-statistic tree.k-th largest is the mirror image. Run the traversal as right-node-left instead of left-node-right. That visits values in descending order, so the k-th node you pop is the k-th largest. Same code, swap left and right in the dive and the continue step — no need to compute the size and subtract.kth-smallest, rank-of(value), insert, and delete all in O(log n). This is the data structure behind "what's the median so far?" running-statistics problems and leaderboard ranking systems where the set keeps changing.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.