Skip to main content

230. Kth Smallest Element in a BST

medium

Find the kth smallest value in a binary search tree. The BST invariant turns this into an in-order traversal stopped at the kth visit — no need to collect every value.

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

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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

In-order traversal of a BST visits values in sorted order. The kth visit IS the answer.

Hint 2

Iterative in-order with a stack lets you stop as soon as you decrement k to 0 — no need to traverse the whole tree.

Hint 3

Follow-up: if the tree is modified often and you need to query repeatedly, augment each node with its left-subtree size for O(h) queries.

Solution approach

Reveal approach

Iterative in-order with early termination. Stack and curr = root. Loop: drain the left spine by pushing curr and moving curr = curr.left until null. Pop the top, decrement k by 1, and if k == 0 return popped.val. Otherwise set curr = popped.right and continue. The first time k hits 0, the popped node is the kth in sorted order — return immediately. O(h + k) time (much less than n when k is small), O(h) space. For the follow-up with frequent modifications, store leftCount at each node: at root, if leftCount + 1 == k return root.val; if k <= leftCount recurse left; else recurse right with k - leftCount - 1.

Complexity

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

Related patterns

  • binary-search-tree
  • tree-dfs
  • in-order

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Uber

Practice these live with InterviewChamp.AI

Drill Kth Smallest Element in a BST and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →