Skip to content

Practice Kth Smallest Element in a BST

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#230
LeetCode Problem

Kth Smallest Element in a BST

Problem Statement

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. Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Source: Kth Smallest Element in a BST on LeetCode. Use the original task for its coding environment and submissions.

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

Constraints

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

How to solve Kth Smallest Element in a BST

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

In-order traversal of a binary search tree visits values in ascending order, so the kth node visited is the kth smallest, and stopping as soon as the count reaches k avoids touching the rest of the tree.

Why brute force is not enough

Collecting all n values with any traversal and then sorting or indexing position k-1 is O(n) time and O(n) extra space; it works for n up to 10^4 but ignores the search property and cannot stop early when k is small.

Approach

  1. Use an explicit stack to drive in-order traversal: from the root, push every node along the leftmost path. The invariant is that the stack holds exactly the unvisited ancestors, smallest on top.
  2. Pop the top node; it is the next smallest unvisited value. Increment a counter.
  3. If the counter equals k, return that node's value at once.
  4. Otherwise step to the popped node's right child, push its entire leftmost path, and repeat.
  5. For the follow-up with frequent updates, store each node's subtree size and descend from the root comparing k with the left subtree's size, answering in O(h) per query.

Walkthrough of Example 2

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

  1. The tree has root 5 with children 3 and 6; node 3 has children 2 and 4; node 2 has left child 1.
  2. Push the leftmost path from the root: 5, 3, 2, 1, so 1 is on top.
  3. Pop 1, count 1; it has no right child, so nothing is pushed.
  4. Pop 2, count 2; it also has no right child.
  5. Pop 3, count 3, which equals k, so return 3 without ever visiting 4, 5, or 6.

Time and space

Time O(h + k) · Space O(h). h is the tree height and k the requested rank; the initial descent costs O(h), each later pop is amortized constant, and the stack never exceeds one root-to-leaf path.

Interview pitfalls

  • Counting from zero when k is one-indexed, which returns the (k+1)th smallest.
  • Writing a recursive traversal that keeps going after the answer is found; the result must be captured and further recursion cut off, or the whole tree is visited.
  • Pushing right children alongside left ones, which breaks the ascending order of pops.
  • After a pop, moving only to the right child instead of pushing that child's full leftmost path.
  • In the augmented follow-up, forgetting to update subtree sizes along the insertion or deletion path, which corrupts later rank queries.

Follow-up questions interviewers ask

  • How would you return the kth largest instead without reversing the entire traversal?
  • With frequent inserts and deletes, how does subtree-size augmentation behave under rotations in a balanced tree?

Further reading on the technique: Binary search tree

Related LeetCode Problems

Practice more problems similar to Kth Smallest Element in a BST.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.