MediumTreesAI interview only
Kth Smallest Element in a BST
Asked atamazonmetagoogleuberbloombergoracle
01 · 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.
02 · Examples
Example 01
3
/ \
1 4
\
2Input
root = [3,1,4,null,2], k = 1
Output
1
The sorted values in the BST are [1, 2, 3, 4]. The 1st smallest element is 1.
Example 02
5
/ \
3 6
/ \
2 4
/
1Input
root = [5,3,6,2,4,null,null,1], k = 3
Output
3
The sorted values in the BST are [1, 2, 3, 4, 5, 6]. The 3rd smallest element is 3.
03 · Constraints
- 01The number of nodes in the tree is n.
- 021 <= k <= n <= 104
- 030 <= Node.val <= 104
04 · Optimal complexity
- Time
- O(H + k)
- Space
- O(H)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.