Find the k-th smallest value in a BST
Given an empty binary search tree with no nodes, you are asked to perform 2 kinds of queries:
insert x- insert the valuexin the BST
smallest k- print thekth smallest element in the BST
Given
q queries, you are asked to write a program to perform these queries.Input
The first line of the input contains a single number
q (1 ≤ q ≤ 1000).The next
q lines contain queries. For all the insert queries, the value of x does not exceed in absolute value. For all the smallest queries, the value of k does not exceed the current tree size.Output
For each
smallest query, the program should print the smallest kth element in the binary search tree.Examples
Input | Output |
8
insert 2
insert 1
smallest 1
smallest 2
insert 10
insert 20
smallest 3
smallest 2 | 1
2
10
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB