Выполнение запросов в дереве двоичного поиска (Binary Search Tree)
Предположим, у нас есть пустое дерево двоичного поиска (BST), в котором отсутствуют любые узлы. Перед вами стоит задача выполнить три вида операций:
insert x— вставить значениеxв BST.search x— проверить, присутствует ли в BST значениеx.print— вывести все значения из BST в порядке обхода in-order.
Дано q запросов. Вам нужно написать программу, которая последовательно обработает каждый из этих запросов.
Входные данные
В первой строке находится одно число q (1 ≤ q ≤ 1000).
В следующих q строках записаны запросы. Для всех операций insert и search значение x не превышает по модулю .
Выходные данные
Для каждого запроса search выведите на отдельной строке Yes, если искомое значение есть в BST, и No — если его нет.
Для каждого запроса print выведите значения из BST при обходе in-order, разделив числа пробелом.
Примеры
Входные данные | Выходные данные |
|---|---|
6 insert 2 insert 1 search 3 insert 0 print search 1 | No 0 1 2 Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB