#174MediumTrees· Binary Search Tree In-Order

Kth Smallest in a Search Tree

A contest registry stores participant ids in a **binary search tree**: for every node, all ids in its left subtree are smaller and all ids in its right subtree are larger, and every id is different. The organisers want to award a prize to the participant with the **k-th smallest id** (counting from 1). Given the root of the tree and an integer `k`, return the k-th smallest value stored in the tree.

Input format

`root`: a binary search tree given in level order with `null` for missing children; `k`: an integer.

Output format

An integer: the k-th smallest value in the tree.

Examples

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

Output: 1

Sorted ids are 1, 2, 3, 4, so the smallest is 1.

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

Output: 3

Sorted ids are 1, 2, 3, 4, 5, 6, so the third smallest is 3.

Input: root = [10], k = 1

Output: 10

A single id is its own smallest.

Constraints

1 <= number of nodes <= 10^4
1 <= k <= number of nodes
0 <= node value <= 10^6; all values are distinct.

#binary-search-tree
#tree
#in-order-traversal
#stack