Given the root of a binary search tree and an integer k, return the kth smallest value in the tree, counting from 1.
Trees are written level by level, with null for a missing child.
Examples
Example 1
- Input
- root = [3, 1, 4, null, 2], k = 1
- Output
- 1
Example 2
- Input
- root = [5, 3, 6, 2, 4, null, null, 1], k = 3
- Output
- 3
Constraints
- The tree has
nnodes, with1 <= k <= n <= 10^4. 0 <= Node.val <= 10^4