Skip to main content

78. Kth Smallest Element in a BST

mediumAsked at Reddit

Find the kth smallest in a BST. Reddit uses this to test inorder + early termination — relevant for ranked-paginated retrieval from an in-memory BST of upvote scores.

By Sam K., Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, BST canonical.

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 + index

Build full inorder list, return list[k-1].

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

Tradeoff: Linear time but builds full list.

2. Iterative inorder with early-stop (optimal)

Use an explicit stack; stop as soon as we've popped k elements.

Time
O(h + k)
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();
    if (--k === 0) return cur.val;
    cur = cur.right;
  }
}

Tradeoff: Doesn't traverse the whole tree. Sublinear when k << n.

Reddit-specific tips

Reddit interviewers want the early-stop version. Bonus signal: discuss how the answer changes if the BST is modified frequently — Morris traversal preserves O(1) extra space, or maintain a size attribute per node for O(log n) selection.

Common mistakes

  • Forgetting that k is 1-indexed.
  • Recursing right before left (gives kth largest).
  • Building the full list when iterative early-stop is asked for.

Follow-up questions

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

  • Kth largest in BST.
  • What if the BST is modified often? (Maintain rank — augmented BST.)
  • Kth smallest in sorted matrix (LC 378).

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 better here?

Early-stop saves work when k is small. Recursive needs to track 'how many remaining' through return values.

What about Morris traversal?

O(1) extra space using threading. More code, same complexity.

More Reddit coding interview questions

See all Reddit problems →