230. Kth Smallest Element in a BST

Return the k-th smallest value (1-indexed) in a binary search tree.

Walk in-order with an explicit stack and stop as soon as the k-th node is popped. There is no need to visit the rest of the tree.

1function kthSmallest(root: TreeNode | null, k: number): number {
2  const stack: TreeNode[] = [];
3  let n = root;
4  while (true) {
5    while (n) { stack.push(n); n = n.left; }
6    n = stack.pop()!;
7    if (--k === 0) return n.val;
8    n = n.right;
9  }
10}

k = 3popped = 0

tree

stack

empty

Start at the root.

1 / 0

Space: play/pause · ←/→: step