Kth Smallest in a Binary Search Tree

Given a binary search tree root, and k return the kth (0-indexed) smallest value in root. It is guaranteed that the tree has at least k + 1 nodes.

Constraints

• k ≤ n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Kth-Smallest-in-a-Binary-Search-Tree

Examples

Example 1

Input

• root =

• k = 2

Output

• answer = 4

Example 2

Input

• root =

• k = 0

Output

• answer = 2

Solution