## Algorithm

Problem Name: beecrowd | 1200

Marcela needs your help to write a computer program about binary search tree. The program must have the following commands:

• I n: Insert the n element in the current Binary Search Tree.
• PREFIXA: print the pre-order traversal for the current tree
• INFIXA: print the in-order traversal for the current tree
• POSFIXA: print the post-order traversal for the current tree
• P n: Search the n element, printing a message indicanding if n exist.
By using this program, at any time must be possible to insert a new element, print the Pre-order, In-order or Post-order traversal or search any element inside the tree.

## Input

The input contains N lines and each line contains an operation using letters (A-Z, a-z) over a binary search tree, that initially will be empty. The first line of input contains an insertion (I). The next lines can have any command described above, like the given example. The end of input is determined by EOF.

Obs: Consider that will not be repeated elements in the tree.

## Output

Each line of the input excepting the lines with the "I" command must produce one output line. The output must be acording to the given example, remembering that "existe" means exist and "nao existe" means don't exist in portuguese. There is no blank space after the last line char, otherwise you`ll get Presentation Error.

 Sample Input Sample Output I c I f I a I h INFIXA PREFIXA POSFIXA P z P h I g INFIXA a c f h c a f h a h f c z nao existe h existe a c f g h

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

bool b;

struct Node
{
char data;
Node* left;
Node* right;
};

Node* GetNewroot(int data)
{
Node* newroot = new Node();
newroot -> data = data;
newroot -> left = NULL;
newroot -> right = NULL;
return newroot;
}

Node* Insert(Node* root, int data)
{
if(root == NULL){
root = GetNewroot(data);
return root;
}else if(data  < = root -> data){
root -> left = Insert(root -> left, data);
}else{
root -> right = Insert(root -> right, data);
}

return root;
}

bool lookup(struct Node* root, int target)
{
if (root == NULL){
return false;
}else {
if (target == root->data){
return true;
}else{
if (target  <  root->data) return lookup(root->left, target);
else return lookup(root->right, target);
}
}
}

void printPreOrder(struct Node* root)
{
if (root == NULL)
return;
if(b){
printf("%c", root -> data);
b = false;
}else{
printf(" %c", root -> data);
}

printPreOrder (root -> left);
printPreOrder (root -> right);
}

void printInOrder(struct Node* root)
{
if (root == NULL)
return;
printInOrder (root -> left);
if(b){
printf("%c", root -> data);
b = false;
}else{
printf(" %c", root -> data);
}
printInOrder (root -> right);
}

void printPosOrder(struct Node* root)
{
if (root == NULL)
return;
printPosOrder (root -> left);
printPosOrder (root -> right);
if(b){
printf("%c", root -> data);
b = false;
}else{
printf(" %c", root -> data);
}
}

int main(int argc, char const *argv[])
{
string s;

Node* root = NULL;

while(getline(cin, s))
{
if(s == "INFIXA"){
b = true;
printInOrder(root);
printf("n");
}else if(s == "PREFIXA"){
b = true;
printPreOrder(root);
printf("n");
}else if(s == "POSFIXA"){
b = true;
printPosOrder(root);
printf("n");
}else if(s[0] == 'P' && s[1] == ' '){
if(lookup(root, s[2])) printf("%c existen", s[2]);
else printf("%c nao existen", s[2]);
}else{
root = Insert(root, s[2]);
}
}

return 0;
}
``````
Copy The Code &

Input

cmd
I c I f I a I h INFIXA PREFIXA POSFIXA P z P h I g INFIXA

Output

cmd
a c f h c a f h a h f c z nao existe h existe a c f g h