Skip to main content

230. Kth Smallest Element in a BST

mediumAsked at Amazon

Given a BST and integer k, return the k-th smallest element. Amazon asks this to test whether you reach for inorder traversal (which visits BST nodes in sorted order) and can short-circuit early.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as a recurring BST problem.
  • Blind (2025-11)— Recurring Amazon interview problem.

Problem

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Constraints

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4

Examples

Example 1

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

Example 2

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

Approaches

1. Recursive inorder

Inorder traversal collects values in sorted order. Return the (k-1)-th.

Time
O(n)
Space
O(n)
function kthSmallestRec(root, k) {
  const out = [];
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    out.push(node.val);
    inorder(node.right);
  }
  inorder(root);
  return out[k - 1];
}

Tradeoff: Simple but visits the whole tree. Mention before offering the short-circuit version.

2. Iterative inorder with early exit (optimal)

Iterative inorder via stack. Pop nodes one at a time; the k-th pop is the answer.

Time
O(h + k)
Space
O(h)
function kthSmallest(root, k) {
  const stack = [];
  let node = root;
  while (node || stack.length) {
    while (node) { stack.push(node); node = node.left; }
    node = stack.pop();
    if (--k === 0) return node.val;
    node = node.right;
  }
  return -1;
}

Tradeoff: Best case O(h + k) — only traverses what's needed. Short-circuits as soon as we've popped k nodes.

Amazon-specific tips

Amazon interviewers want the early-exit iterative version. State out loud: 'Inorder traversal visits BST nodes in sorted order. The k-th node popped is the k-th smallest.' Then add: 'I can short-circuit — no need to traverse the whole tree.' The early exit is the senior-IC signal.

Common mistakes

  • Returning the k-th visited node instead of the (k-1)-th (1-indexed vs 0-indexed confusion).
  • Recursing the whole tree even when k is small — wastes work.
  • Forgetting that BST property holds (so left subtree values < node.val < right subtree values).

Follow-up questions

An interviewer at Amazon may pivot to one of these next:

  • What if the BST is huge and we need many kth-smallest queries? (Augment BST with subtree size counts for O(log n) per query.)
  • Kth Largest Element in a Stream (LC 703) — heap-based.
  • What if values can be updated frequently?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why iterative instead of recursive?

Iterative lets us return immediately when we hit the k-th node. Recursive would require either a global counter or threading a return value through the call stack.

What if the tree has duplicates?

Strict BSTs don't have duplicates, but if they did, inorder still works — duplicates appear consecutively in sorted order. Just decrement k normally.

Practice these live with InterviewChamp.AI

Drill Kth Smallest Element in a BST and other Amazon interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →