MediumDepth-First SearchBinary Search TreeTreeUpdated Sep 2026

230. Kth Smallest Element in a BST

Asked at Google, Meta, Amazon, Microsoft and 2 more

Difficulty

Medium

Time

O(k + h)

Space

O(h)

Pattern

Depth-First Search

Companies

6

Problem

You are given the root of a binary search tree (BST) and an integer k. Return the k-th smallest value among all node values in the tree. Counting is 1-indexed, so k = 1 means the smallest value.

A BST has a useful property: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. Because of this, an in-order traversal (visit left subtree, then the node, then right subtree) walks the values in sorted order from smallest to largest.

So the task becomes: walk the tree in-order and stop at the k-th node you visit. You do not need to collect all values into a list — just count as you go and return the value when the count reaches k.

In-order gives sorted values

11st22nd33rd44thIn-order order is 1, 2, 3, 4 — the numbers show visitorder.sorted values12340123For k = 1 the answer is the first element, 1.
Walking left → node → right on a BST lists values from smallest to largest, so the k-th one is the answer.

Constraints

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

Examples

Example 1
Inputroot = [3,1,4,null,2], k = 1
Output1
WhyIn-order traversal gives 1, 2, 3, 4. The 1st smallest value is 1.
Example 2
Inputroot = [5,3,6,2,4,null,null,1], k = 3
Output3
WhyIn-order traversal gives 1, 2, 3, 4, 5, 6. The 3rd value in that sorted order is 3.

Asked At

6 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
UberMediumView all Uber questions →

How to Think About It

1

In-order traversal of a BST visits nodes in sorted order (left → root → right).

2

Do an in-order traversal and stop after visiting k nodes. The kth node visited is the answer.

3

You don't need to store all values — just count nodes as you visit them and stop at k.

4

Alternative: store the count of nodes in each subtree. If left subtree has >= k nodes, recurse left. If left + 1 = k, return root. Otherwise recurse right with k - leftCount - 1.

5

Edge cases: k = 1 (leftmost node), k = n (rightmost node), single node tree.

Optimal Approach

In-order traversal:
Step 1: Define inorder(node) that yields values in sorted order.
Step 2: Iterate through the generator, decrementing k each time.
Step 3: When k = 0, return the current value.

Alternatively, iterative inorder with explicit stack:
Push all left children. Pop (this is next smallest). Decrement k. If k=0, return. Push all left children of the right child.

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

Count as you traverse

go left as far as possiblevisit node → count += 1if count == k, return valueelse go rightThe in-order rule: left subtree first, then the node,then the right subtree.1count=12count=2 = k34For k = 2: visit 1 (count 1), then visit 2 (count 2)and stop.inorder: left → node → rightstop when count == k
We keep a counter. Each in-order visit adds one; when the counter hits k we return that value.
ComplexityTime O(k + h)Space O(h)We visit at most k nodes plus the height h of the tree to reach them; the recursion stack (or explicit stack) holds at most h frames.

What Trips People Up in Real Interviews

1

Doing a full in-order traversal. You can stop after k nodes — don't traverse the entire tree.

2

Confusing "kth smallest" with "kth largest." Smallest means leftmost in a BST. For kth largest, you could reverse the traversal or use n - k + 1.

3

Not handling the case where k is larger than the number of nodes. The problem guarantees valid k, but in an interview, clarify this.

4

Using a sort instead of BST properties. Sorting all values is O(n log n). In-order traversal is O(k + h) where h is tree height.

5

Using iterative in-order traversal but forgetting to push all left children before processing. The pattern is: push all left descendants, pop and process, then push all left of the right child.

Solution Code

O(k + h) time
def kthSmallest(root, k):
    def inorder(node):
        if not node:
            return
        yield from inorder(node.left)
        yield node.val
        yield from inorder(node.right)
    for val in inorder(root):
        k -= 1
        if k == 0:
            return val

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Kth Smallest Element in a BST problem?

Given the root of a binary search tree and an integer `k`, return the kth smallest value (1-indexed) of all the node values in the `BST`.

How do you solve Kth Smallest Element in a BST?

The optimal approach runs in O(k + h) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Kth Smallest Element in a BST?

Kth Smallest Element in a BST is asked at Google, Meta, Amazon, Microsoft, Apple, Uber. It is a medium difficulty problem.

What are common mistakes on Kth Smallest Element in a BST?
  • Doing a full in-order traversal. You can stop after k nodes — don't traverse the entire tree.
  • Confusing "kth smallest" with "kth largest." Smallest means leftmost in a BST. For kth largest, you could reverse the traversal or use n - k + 1.
  • Not handling the case where k is larger than the number of nodes. The problem guarantees valid k, but in an interview, clarify this.
  • Using a sort instead of BST properties. Sorting all values is `O(n log n)`. In-order traversal is `O(k + h)` where h is tree height.
  • Using iterative in-order traversal but forgetting to push all left children before processing. The pattern is: push all left descendants, pop and process, then push all left of the right child.