Kth Smallest Element in a BST
MediumTrees
Given the root of a binary search tree and an integer k, return the k-th smallest value in the tree, counting from 1 (so k = 1 asks for the minimum).
In a binary search tree, every value in a node's left subtree is smaller than the node's value and every value in its right subtree is larger. All values are distinct.
Trees are written in level order: values are listed level by level, left to right, and null marks a missing child (trailing nulls are omitted).
Example 1
- Input:
- root = [6,3,9,1,4,null,11,null,2], k = 4
- Output:
- 4
- Explanation
- Reading the tree in sorted order gives 1, 2, 3, 4, 6, 9, 11. The fourth value is 4.
Example 2
- Input:
- root = [50,30,70,20,40,60,80], k = 5
- Output:
- 60
- Explanation
- Sorted, the values are 20, 30, 40, 50, 60, 70, 80, so the fifth smallest is 60, which lives in the root's right subtree.
Example 3
- Input:
- root = [10,null,20,null,30], k = 3
- Output:
- 30
- Explanation
- The tree is a right-leaning chain whose sorted order is 10, 20, 30, so the third smallest is the deepest node.
Constraints
- The number of nodes is
n, with1 <= k <= n <= 10^4 0 <= Node.val <= 10^4- All values are distinct