Performing Queries on a Binary Search Tree
Given an empty binary search tree with no nodes, you are asked to perform 3 kinds of queries:
insert x
- insert the valuex
in the BST
search x
- check if the valuex
is in the BST
print
- print the BST in the in-order traversal order.
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
and search
queries the value of x
does not exceed in absolute value. Output
For each
search
query, the program should print Yes
if the value is present in the BST, and No
otherwise on a new line.For each
print
query, the program should print the in-order traversal of the BST, where the values should be separated by a space. Examples
Input | Output |
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