Найти второе наименьшее значение в BST
Допустим, у нас имеется пустое бинарное дерево поиска (BST) без каких-либо узлов. Необходимо выполнить два вида запросов:
insert x— вставить значениеxв BST
smallest— вывести второе наименьшее значение в BST
Пусть количество запросов равно
q. Требуется написать программу, которая будет обрабатывать эти запросы.Входные данные
В первой строке входных данных содержится единственное число
q (1 ≤ q ≤ 1000).В следующих
q строках приводятся запросы. Для всех операций insert значение x не превышает по модулю . Для всех запросов smallest гарантируется, что в BST содержится как минимум 2 элемента.Выходные данные
Для каждого запроса
smallest программа должна выводить второе наименьшее значение в бинарном дереве поиска.Примеры
Входные данные | Выходные данные |
7
insert 2
insert 1
smallest
insert 10
smallest
insert -1
smallest | 2
2
1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB