Найти k-ое по величине значение в BST
Дано пустое дерево поиска без каких-либо узлов. Необходимо выполнить два вида запросов:
insert x— вставить значениеxв BST.
smallest k— вывести k-ый по величине элемент в BST.
Учитывая, что есть
q запросов, требуется написать программу, которая будет обрабатывать эти запросы.Ввод
В первой строке входных данных содержится одно число
q (1 ≤ q ≤ 1000).В следующих
q строках содержатся запросы. Для каждого запроса вида insert значение x не превышает по модулю . Для каждого запроса вида smallest значение k не превышает текущий размер дерева.Вывод
Для каждого запроса
smallest необходимо вывести k-ый по величине элемент в двоичном дереве поиска.Примеры
Ввод | Вывод |
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