85. Kth Smallest Element in a BST
Consider the tree's values in increasing order and identify the value at rank k. The first rank corresponds to the smallest stored value.
Use the BST ordering instead of treating the tree as an arbitrary collection. Follow the contract for invalid k and any absent-result representation.
Example 1
Input
tree=[3,1,4,null,2], k=2
Output
2
Explanation: Inorder values are 1,2,3,4; stop at the second emitted node.
Example 2
Input
tree=[0,MIN,MAX], k=3
Output
MAX
Explanation: Values are returned directly, not used as sentinels.
Example 3
Input
tree=[], k=1
Output
IllegalArgumentException
Explanation: The rank has no witness.
Constraints
0 <= node count per tree <= 105-231 <= node.value <= 231 - 11 <= k <= node count- Each input is a proper binary tree: no cycles or shared child nodes. Null trees are permitted.
- The input is a strict BST. k must identify an existing node.
Hints
Hint 1
What traversal emits BST values in increasing order?
Hint 2
An explicit stack can suspend ancestors while descending left.
Hint 3
Count pops, return on the kth one, and reject if traversal ends first.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Consume rank only on inorder emission
[3,1,4,null,2]
2
2