Return the -th smallest value in a binary search tree.
Problem
Given the root of a binary search tree (BST) and an integer , return the value of the -th smallest node in the tree.
A BST has the property that for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.
You may assume that is valid and there is exactly one answer.
Input Format
- The root of a BST.
- An integer .
Output Format
- Return the value of the -th smallest node in the BST.
Constraints
- The tree is a valid BST.
- , where is the number of nodes in the tree.
- Node values are distinct.
Hints
- In a BST, an in-order traversal visits nodes in sorted order.
- You do not need to traverse the entire tree if you can stop once the answer is found.
Input Format
root: root node of a valid binary search treek: a valid positive integer
Output Format
- The value of the -th smallest node in the BST
Constraints
- Valid BST
- Distinct node values
Example 1
Input
root = [3,1,4,null,2], k = 1
Output
1
Explanation
The in-order traversal is [1,2,3,4]. The 1st smallest value is 1.
Example 2
Input
root = [5,3,6,2,4,null,null,1], k = 3
Output
3
Explanation
The in-order traversal is [1,2,3,4,5,6]. The 3rd smallest value is 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.