Kth Smallest Element in a BST

Problem in simple words

Given a binary search tree and a number k, find the kth smallest value it contains (1st smallest, 2nd smallest, and so on).

Core idea

Sorted order plus a running counter is all a 'kth smallest' question ever needs -- a BST's inorder traversal produces that sorted order for free, so just count until you reach k.

How the algorithm thinks

1. 1

   Count this node's sorted position

   VISIT

   Inorder order is sorted order, so a running counter incremented at each visit tells you exactly which sorted position you're currently at.

   Watch: The current node's value and the running count.

2. 2

   The counter reaches k

   FOUND

   The count-th value visited in sorted order is, by definition, the count-th smallest value in the whole tree -- no further searching is needed once this matches k.

   Watch: The matching node's value and that it equals k.

3. 3

   Stop immediately once found

   RETURN

   Continuing to traverse after the answer is already known would only visit larger values that can't possibly still be relevant.

   Watch: Which pending recursive calls short-circuit once the result is set.

Step-by-step logic

• -Initialize count to 0 and result to null (or 'not found yet').
• -Recursively visit the left subtree first -- but stop immediately if result has already been set.
• -At the current node, increment count by 1.
• -If count now equals k, record the current node's value as the result and stop.
• -Otherwise, recursively visit the right subtree (again stopping immediately if result gets set partway through).
• -Once the traversal ends (naturally or via early stop), result holds the answer.

Complexity

Time O(h + k)·Space O(h)

In the best case, the traversal stops as soon as the kth value is found; it visits at most h (the tree's height) nodes just to reach the leftmost value, plus up to k nodes total before stopping.

Implementation

This is the JavaScript implementation that generates the simulator timeline.

function kthSmallest(root, k) {
  let count = 0;
  let result = null;

  function inorder(node) {
    if (node === null || result !== null) return;

    inorder(node.left);
    if (result !== null) return;

    count++;
    if (count === k) {
      result = node.val;
      return;
    }

    inorder(node.right);
  }

  inorder(root);
  return result;
}

Common mistakes