∅
stack top
An in-order traversal of a binary search tree emits its values in sorted order, so the k-th node you visit is the k-th smallest — stop the moment a running counter hits k.
Given the root of a binary search tree and an integer k (1-indexed), return the k-th smallest value in the tree. For root = [3,1,4,null,2] the sorted order is 1, 2, 3, 4, so k = 1 → 1 and k = 3 → 3.
k-th one. Because you can stop the instant the counter reaches k, you only ever touch the smallest k nodes plus the spine above them.stack and a cursor cur = root. The stack will hold ancestors whose left side we've already descended.curisn't null, push it and move to cur.left. This stacks the left spine so the smallest unvisited node ends up on top.--k; if it hits 0, this node is the answer.cur = node.right and loop. Repeat until you return.The explicit stack holds at most H nodes, so space is O(H) — O(log n) for a balanced tree, O(n)in the worst (degenerate) case. A recursive in-order with a counter is equally valid; the iterative version just makes the "stop early" logic explicit.
next() calls), and Recover BST (spot the two out-of-order pops).k-th value we visit is the answer (k = 1).class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function kthSmallest(root: TreeNode | null, k: number): number {
const stack: TreeNode[] = [];
let cur: TreeNode | null = root;
while (cur !== null || stack.length > 0) {
// Walk the left spine: smaller values go on top.
while (cur !== null) {
stack.push(cur);
cur = cur.left;
}
// Pop the next-smallest unvisited node.
cur = stack.pop()!;
if (--k === 0) return cur.val; // k-th in-order node
// Its left subtree is done; explore the right subtree.
cur = cur.right;
}
throw new Error('k is larger than the number of nodes');
}stack holds ancestors we still owe a visit; cur is the node we're currently descending from. The outer loop runs while either there is a node to descend (cur) or unvisited ancestors remain (stack.length).cur and keep moving to cur.left. This loads the entire left spine onto the stack so the smallest unvisited value sits on top.stack.pop() yields the next value in sorted order. --k decrements first; when it reaches 0 we've visited exactly k nodes, so cur.val is the answer.cur = cur.right and the loop will dive its left spine next.k exceeded the node count — an invalid input we guard with a throw.O(H + k): at most H pushes to reach the smallest node, then k pop/visit steps. Space O(H) for the stack — O(log n) balanced, O(n) worst case.O(H) by comparing k to that size at each step.k hits zero — same O(H + k).| "k-th smallest in a BST" | in-order traversal + counter |
| need sorted order from a BST | left → node → right |
| stop as soon as you can | iterative in-order, return on --k === 0 |
| "k-th largest" | reverse in-order (right → node → left) |
const stack: TreeNode[] = [];
let cur = root;
while (cur || stack.length) {
while (cur) { stack.push(cur); cur = cur.left; }
cur = stack.pop()!;
if (--k === 0) return cur.val;
cur = cur.right;
}