Skip to main content

76. Kth Smallest Element in a BST

mediumAsked at Workday

Find the kth smallest value in a BST. Workday uses this to test in-order traversal awareness — same shape as 'the kth-earliest hire date in a salary-sorted directory'.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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. Inorder collect + index

Inorder traversal into array; return array[k-1].

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

Tradeoff: Stores all values; doesn't early-exit at k.

2. Iterative inorder with early exit

Push-left-spine + pop. Decrement k each pop; return on k == 0.

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

Tradeoff: Early exit at k. Only walks O(h + k) nodes, useful for small k.

Workday-specific tips

Workday grades for the early-exit. The iterative inorder is the canonical pattern. If they ask for the followup 'what if the BST is modified frequently and you need many kth queries?', mention augmenting nodes with subtree counts for O(h) queries.

Common mistakes

  • Doing recursive inorder and storing everything — works but skipping the early exit.
  • Off-by-one: kth smallest at decrement-and-check vs check-then-decrement order.
  • Forgetting that k is 1-indexed.

Follow-up questions

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

  • Augment with subtree counts for O(h) kth queries with updates.
  • Kth Largest in BST — mirror in-order (right, root, left).
  • Closest BST Value (LC 270).

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 over recursive?

Iterative inorder supports clean early-exit. Recursive needs a global counter and a 'found' flag to unwind the stack.

Subtree counts?

Augment each node with subtree size. At each step, compare k to left subtree size to decide direction. O(h) per query.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →