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.
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
root = [3,1,4,null,2], k = 1
1
# Example 2
root = [5,3,6,2,4,null,null,1], k = 3
3
Constraints
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
- 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.
- Pop the top node; it is the next smallest unvisited value. Increment a counter.
- If the counter equals k, return that node's value at once.
- Otherwise step to the popped node's right child, push its entire leftmost path, and repeat.
- 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
- The tree has root 5 with children 3 and 6; node 3 has children 2 and 4; node 2 has left child 1.
- Push the leftmost path from the root: 5, 3, 2, 1, so 1 is on top.
- Pop 1, count 1; it has no right child, so nothing is pushed.
- Pop 2, count 2; it also has no right child.
- 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.