Kth Smallest Element in a BST

MediumTreesTreeDFSBinary Search Tree

Problem

Given a binary search tree and an integer k, return the k-th smallest value stored in it, counting the smallest value as the first.

Example. For a tree with root 5, left child 3 (children 2 and 4), and right child 6, the sorted values are 2, 3, 4, 5, 6, so for k = 3 the answer is 4.

Key idea

The naive approach collects every value into a list, sorts it, and reads off the k-th entry. It works, but it throws away order a binary search tree already encodes for free: an in-order traversal (left subtree, then node, then right subtree) visits every value in strictly increasing order with no explicit sorting.

So walk the tree in order and count nodes as they are emitted. The moment the count reaches k, the node just visited holds the answer, and the traversal can stop instead of touching the rest. An explicit stack, rather than plain recursion, makes that early stop straightforward, since in-progress recursive calls cannot be abandoned as cleanly as popping a stack.

Solution

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, 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 node = root;
  let count = 0;

  while (node !== null || stack.length > 0) {
    // Descend as far left as possible, stacking ancestors still owed a visit.
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }

    // Popping the stack visits nodes in strictly increasing order.
    node = stack.pop()!;
    count++;
    if (count === k) {
      // Stop as soon as the k-th value is found, without touching the rest of the tree.
      return node.val;
    }

    node = node.right;
  }

  throw new Error('k is out of bounds for this tree');
}

Complexity

  • Time: O(h + k). Up to h steps to reach the leftmost node, then k more visited before stopping; worst case O(n) when k is close to the tree's size.
  • Space: O(h). The stack, bounded by the tree's height.

Watch out for

  • Confirm whether k is 1-indexed and count consistently against it; an off-by-one is easy to introduce.
  • A plain recursive in-order traversal with no way to short-circuit visits the entire tree regardless of k, turning O(h + k) into O(n); use an iterative stack to stop early.
  • If the tree changes often and this query runs repeatedly, augmenting each node with its subtree size turns each lookup into O(h).

Pattern

This relies on in-order traversal of a binary search tree equaling sorted order, the same property behind BST validation and successor lookups. Recognizing when a structure already encodes an ordering, instead of paying to compute one, is a recurring shortcut.

Related questions