//Binary tree

#include<iostream>
using namespace std;
struct node{
    int data;
    struct node* left;
    struct node* right;
    node(int value): data(value),left(nullptr),right(nullptr){
    };
};
struct node* NewNode(int value){
    struct node* temp = new node(value);
    temp -> data = value;
    temp -> left = nullptr;
    temp -> right = nullptr;
    return temp;
};
void inorder(struct node* temp){
    if(temp!=nullptr){
        inorder(temp->left);
        cout<<" "<<temp->data;
        inorder(temp->right);
    }
}
void preorder(struct node* temp){
    if(temp!=nullptr){
        cout<<" "<<temp->data;
        preorder(temp->left);
        preorder(temp->right);
    }
}
void postorder(struct node* temp){
    if(temp!=nullptr){
        postorder(temp->left);
        postorder(temp->right);
        cout<<" "<<temp->data;
    }
}
int main(){
    int x, y, z;
    cin>>x>>y>>z;
    struct node* root = NewNode(x);
    root->left = NewNode(y);
    root->right = NewNode(z);
    cout<<"Inorder: ";
    inorder(root);
    cout<<endl;
    cout<<"Preorder: ";
    preorder(root);
    cout<<endl;
    cout<<"Postorder: ";
    postorder(root);
    cout<<endl;
return 0;
}


//Binary search tree


#include<iostream>
using namespace std;
struct node{
    int data;
    struct node* left;
    struct node* right;
    node(int value): data(value),left(nullptr),right(nullptr){
    };
};
struct node* NewNode(int value){
    struct node* temp = new node(value);
    temp->data = value;
    temp->left = nullptr;
    temp->right = nullptr;
    return temp;
};
struct node* insert_element(struct node* root,int value){
    if(root==nullptr){
        return NewNode(value);
    }
    if(value<root->data){
        root->left = insert_element(root->left,value);
    }else{
        root->right = insert_element(root->right,value);
    }
};
bool search_BST(struct node* temp,int value){
    if(temp==nullptr){
        false;
    }
    if(temp->data==value){
        return true;
    }else if(value<temp->data){
        return search_BST(temp->left,value);
    }else{
        return search_BST(temp->right,value);
    }
}
void inorder(struct node* temp){
    if(temp!=nullptr){
        cout<<" "<<temp->data;
        inorder(temp->left);
        inorder(temp->right);
    }
}
void preorder(struct node* temp){
    if(temp!=nullptr){
        preorder(temp->left);
        cout<<" "<<temp->data;
        preorder(temp->right);
    }
}
void postorder(struct node* temp){
    if(temp!=nullptr){
        postorder(temp->left);
        postorder(temp->right);
        cout<<" "<<temp->data;
    }
}
int main(){
    struct node* ptr_root = nullptr;
    int value,n;
    cout<<"Enter the element number to be inserted: ";
    cin>>n;
    cout<<endl;
    cout<<"Enter the values: "<<endl;
    for(int i=0; i<n; i++){
        cin>>value;
        ptr_root = insert_element(ptr_root,value);
    }
    cout<<"Inorder: ";
    inorder(ptr_root);
    cout<<endl;
    cout<<"Preorder: ";
    preorder(ptr_root);
    cout<<endl;
    cout<<"Postorder: ";
    postorder(ptr_root);
    cout<<endl;
return 0;
}