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 valuexin the BSTsearch x- check if the valuexis in the BSTprint- 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