Skip to main content

230. Kth Smallest Element in a BST

mediumAsked at LinkedIn

Given a BST and integer k, return the kth smallest value. LinkedIn asks this on the BST round — they want the iterative inorder with early-stop, AND the follow-up answer if the tree is modified frequently (augment with subtree size).

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

Source citations

Public interview reports confirming this problem appears in LinkedIn loops.

  • Glassdoor (2026-Q1)— LinkedIn SWE onsite reports list this as the BST-traversal problem on the trees screen.
  • Blind (2025-11)— LinkedIn writeups describe both the iterative inorder AND the augmented-tree follow-up as expected signals.

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. Full inorder traversal then index

Inorder traversal collects all values in ascending order; return the (k-1)th element.

Time
O(n)
Space
O(n) for the value list
function kthSmallestFull(root, k) {
  const arr = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.left);
    arr.push(node.val);
    dfs(node.right);
  }
  dfs(root);
  return arr[k - 1];
}

Tradeoff: Simple but wasteful — visits every node and stores every value. Mention it then move to iterative early-stop.

2. Iterative inorder with early stop (optimal)

Use a stack to simulate inorder. Pop k times; the kth pop is the answer.

Time
O(h + k) where h is tree height
Space
O(h)
function kthSmallest(root, k) {
  const stack = [];
  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;
}

Tradeoff: Stops after k pops — best case O(log n + k), worst case O(n). The stack depth is O(h) so we never store all values.

3. Augmented tree with subtree sizes (follow-up answer)

If the BST is augmented with subtree sizes (count of nodes per subtree), find kth smallest in O(h) by descending. At each node, if left subtree has size s: k <= s recurse left; k == s + 1 return this node; k > s + 1 recurse right with k = k - s - 1.

Time
O(h) per query, O(h) per insert/delete to maintain sizes
Space
O(1) extra per query
// Assumes each node has a .size field maintained on insert/delete.
function kthSmallestAugmented(root, k) {
  let cur = root;
  while (cur) {
    const leftSize = cur.left ? cur.left.size : 0;
    if (k === leftSize + 1) return cur.val;
    if (k <= leftSize) cur = cur.left;
    else { k -= leftSize + 1; cur = cur.right; }
  }
  return -1;
}

Tradeoff: O(h) per query — best for many queries on a relatively-static tree. Maintaining sizes adds O(h) per insert/delete. This is the answer interviewers want for the 'what if the tree is frequently modified?' follow-up.

LinkedIn-specific tips

LinkedIn interviewers consistently follow up with: 'What if the tree is modified frequently (lots of inserts and deletes) and you need many kth-smallest queries?' The iterative inorder is O(n) per query; the augmented tree is O(h) per query but pays O(h) per modification. Articulate the tradeoff explicitly: 'Augmented tree wins for many queries vs few modifications.' That's the entire follow-up signal.

Common mistakes

  • Returning the full inorder array — wastes space and prevents early stop.
  • In the iterative version, decrementing k BEFORE the pop — gives off-by-one.
  • In the augmented version, using leftSize incorrectly — must compare k against leftSize + 1 (the position of the current node in inorder), not leftSize.

Follow-up questions

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

  • What if we need the kth LARGEST instead? (Reverse inorder.)
  • Kth Smallest in a Sorted Matrix (LC 378) — different structure, same kth-smallest framing.
  • What if the tree had duplicate values? (Same algorithm; the augmented version still works.)

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 is iterative inorder preferred over full traversal?

Because it can stop after k pops. Best case O(log n + k); even worst case the stack uses O(h) memory instead of O(n) for the full value list.

When is the augmented tree worth the complexity?

When you have many queries and few modifications, OR when k can be very close to n (so the iterative version is O(n) per query). Augmented gives O(h) per query independent of k.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →