All problems

Kth Smallest Element in a BST

Medium · tree dfs

You are given the root of a binary search tree (BST) and an integer k. Return the kth smallest value stored in the tree, counting from 1.

The tree is a valid BST: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. All values are distinct. k is always between 1 and the number of nodes, so an answer always exists.

Examples

Example 1

Input: root = [3, 1, 4, null, 2], k = 1

Output: 1

Sorted, the values are [1, 2, 3, 4]. The smallest is 1.

Example 2

Input: root = [5, 3, 6, 2, 4, null, null, 1], k = 3

Output: 3

Sorted, the values are [1, 2, 3, 4, 5, 6]. The 3rd smallest is 3.

Example 3

Input: root = [2, 1, 3], k = 3

Output: 3

Constraints

• The number of nodes n is in the range [1, 500].
• 1 <= k <= n
• -10^4 <= Node.val <= 10^4, and all values are distinct.
• The tree is a valid binary search tree.