Kth Smallest in BST

The problem

BST root + integer k (1-indexed). Return the k-th smallest value.

      3
     / \
    1   4
     \
      2
k = 1 → 1

Inorder of BST is sorted order.

Brute: full inorder array

function kthSmallestBrute(root: TreeNode | null, k: number): number {
  const vals: number[] = [];
  function inorder(n: TreeNode | null) {
    if (!n) return;
    inorder(n.left);
    vals.push(n.val);
    inorder(n.right);
  }
  inorder(root);
  return vals[k - 1];
}

Time	O(n)
Space	O(n)

Optimal: iterative inorder, stop early

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 cur = root;

  while (cur || stack.length) {
    while (cur) {
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop()!;
    k--;
    if (k === 0) return cur.val;
    cur = cur.right;
  }
  return -1; // constraints guarantee k valid
}

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

Recursive early stop

function kthSmallestRec(root: TreeNode | null, k: number): number {
  let count = k;
  let ans = 0;
  function dfs(n: TreeNode | null): boolean {
    if (!n) return false;
    if (dfs(n.left)) return true;
    count--;
    if (count === 0) {
      ans = n.val;
      return true;
    }
    return dfs(n.right);
  }
  dfs(root);
  return ans;
}

Follow-up: frequent insert/delete + kth queries

Augment each node with subtree size. Binary search down: if leftSize+1 === k return node; if k <= leftSize go left; else go right with k - leftSize - 1. Query O(h).

Edge cases

• k = 1 (minimum)
• k = n (maximum)
• Skewed tree

Common mistakes

• Reverse inorder for kth largest without adjusting
• 0-index vs 1-index k
• Full array when early stop is easy

Interview delivery

1. Inorder = sorted.
2. Stack iterative stop at k.
3. Complexity O(h+k).
4. Augmented tree follow-up.
5. Code carefully.

Mental model

BST inorder is sorted ascending. The k-th visit in inorder is the answer. Iterative stack lets you stop without walking the whole tree.

Follow-up depth

If the tree mutates often and queries are frequent, store subtree sizes and walk like order-statistic trees. Mentioning this is free points.

Out-loud answer

“Inorder traversal, return when count hits k. Iterative stack O(h+k) time O(h) space. Full array also works but uses O(n) memory. Augment sizes for O(h) queries if asked.”

Complexity table

Approach	Time	Space
Full inorder array	O(n)	O(n)
Iterative early stop	O(h+k)	O(h)
Augmented sizes	O(h) query	O(n) build

Interview delivery

1. Inorder sorted.
2. Stack walk until k.
3. 1-indexed k.
4. Follow-up sizes.
5. Complexities.

Related

• Validate Binary Search Tree
• Lowest Common Ancestor BST
• Binary Tree Level Order
• K Closest Points to Origin
• JavaScript Interview Guide

Further reading

• LeetCode 230 — Kth Smallest Element in a BST
• Binary search tree