K-th Smallest Number In BST

Given the root node of a valid BST and a number k, return the kth smallest number in this BST (1-indexed).

Input

• bst: a binary tree representing the existing BST.
• k: an integer.

Output

The kth smallest number in bst.

Examples

Example 1:

Input:

bst = <See explanation>
k = 4

Output: 6

Explanation:

Constraints

• 1 <= k <= n <= 10^5, where n is the size of bst.

Try it yourself

Solution