8618: ALDS1_8_B : Binary Search Tree II
[Creator : ]
Description
Write a program which performs the following operations to a binary search tree T by adding the find operation to A: Binary Search Tree I.
- insert k: Insert a node containing k as key into T.
- find k: Report whether T has a node containing k.
- print: Print the keys of the binary search tree by inorder tree walk and preorder tree walk respectively.
Input
In the first line, the number of operations m is given.
In the following m lines, operations represented by insert k, find k or print are given.
Output
For each find k operation, print "yes" if T has a node containing k, "no" if not.
In addition, for each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key.
Constraints
The number of operations ≤500,000
The number of print operations ≤10.
−2,000,000,000≤key≤2,000,000,000
The height of the binary tree does not exceed 100 if you employ the above pseudo code.
The keys in the binary search tree are all different.
The number of print operations ≤10.
−2,000,000,000≤key≤2,000,000,000
The height of the binary tree does not exceed 100 if you employ the above pseudo code.
The keys in the binary search tree are all different.
Sample 1 Input
10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print
Sample 1 Output
yes
no
1 12 17 20 25 30 88
30 12 1 20 17 25 88