You are given root, the root of a binary search tree, and a number k. The values in the tree
are all different; every node's left subtree holds smaller values and its right subtree larger
ones.
Return the kth smallest value in the tree, counting from 1, so k = 1 asks for the minimum.
Trees are written in level order, row by row from the top, with null where a node is missing:
[4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the right child of 2.
Example 1
- Input
- root = [6, 3, 9, 1, 4, 8], k = 3
- Output
- 4
Example 2
- Input
- root = [2, null, 5], k = 1
- Output
- 2
Constraints
- The tree holds n nodes, and 1 ≤
k≤ n ≤ 1000. - Values are distinct, between 0 and 10⁴.
Show the pattern
Trees
An in-order traversal of a binary search tree visits its values in increasing order, so the kth value it visits is the answer, and you can stop right there.
See trees in a visualiserShow the approach
An in-order traversal (left subtree, node, right subtree) visits a binary search tree's values in increasing order. Run it with an explicit stack: from the current node, push nodes while going left. When you can't go further, pop a node and visit it; it is the next smallest value. Then move to its right child and repeat.
The kth node visited is the answer, and the rest of the tree is never touched.
Time: O(h + k), h the tree's height · Space: O(h)