Kth Smallest Element in a BST

Examples

Input: root = [3,1,4,null,2], k = 1
Output: 1

The values in sorted order are 1, 2, 3, 4 — the 1st smallest is 1.

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

The values in sorted order are 1, 2, 3, 4, 5, 6 — the 3rd smallest is 3.

Constraints

• The number of nodes is in the range [1, 10^4].

• 1 <= k <= number of nodes.

Approach

The defining fact about a BST is that its in-order traversal (left, then node, then right) produces values in strictly increasing order. So the kth smallest value is simply the kth value produced by that traversal — the only question is whether you collect everything first or stop as soon as you've counted k values.

Solutions

Brute Force — Collect All Values, Then Index

Run a full in-order traversal, collecting every value into an array in sorted order. Once that's done, the answer is simply the value at index k - 1.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function kthSmallest(root, k) {
  const values = [];

  function inorder(node) {
    if (node === null) return;
    inorder(node.left);
    values.push(node.val);
    inorder(node.right);
  }

  inorder(root);
  return values[k - 1];
}

Time: O(n) · Space: O(n) — storing every value even when k is small

Optimal — Iterative In-Order with Early Stop

Do the same in-order traversal, but iteratively with an explicit stack, and stop the instant you've produced the kth value instead of visiting the rest of the tree. This matters a lot when k is small relative to the size of the tree.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function kthSmallest(root, k) {
  const stack = [];
  let node = root;

  while (node !== null || stack.length > 0) {
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }

    node = stack.pop();
    k--;
    if (k === 0) return node.val;

    node = node.right;
  }

  return -1;
}

Time: O(h + k) — descends to the leftmost node, then advances k times · Space: O(h) — the explicit stack, where h is the tree's height