Write a program that will implement actions in the "insert" binary search tree; and "find" (by value). The program must process requests of three types:
ADD n — if the specified number is not yet in the tree, insert it and output the word "DONE" if — leave the tree as it was and display the word "ALREADY".
SEARCH — should output the word «YES» (if the value is found in the tree) or the word "NO" (if not found). The tree does not change.
PRINTTREE — output the entire tree, always using the algorithm specified in the output format.
Input
Each line of the input contains one of the queries ADD n or SEARCH n or PRINTTREE. It is guaranteed that PRINTTREE queries will only be called when the tree is not empty. The total number of requests does not exceed 1000, of which no more 20 PRINTTREE.
requests
Output
For each request, display the answer to it. For ADD and SEARCH — the corresponding word on a separate line. For the PRINTTREE request, a tree must be output, necessarily according to the following algorithm:
template void print_tree(Node *p, int level)
{
if(p==NULL)
return;
print_tree(p->left, level+1);
for(int i=0; i < level; i++)
cout << ".";
cout << p->data << endl;
print_tree(p->right, level+1);
}
(Initial call to this function — print_tree(root,0).)
Examples
| # |
Input |
Output |
| 1 |
ADD2
ADD 3
ADD2
SEARCH 2
ADD 5
PRINTTREE
SEARCH 7
|
DONE
DONE
ALREADY
YES
DONE
2
.3
..5
NO
|