#include <stdio.h>
#include <stdlib.h>
struct node
{   int value;
    struct node* left;
    struct node* right;};
void search(struct node* r,int number);
struct node* root;
struct node* insert(struct node* r, int data);
void inOrder(struct node* r);
void preOrder(struct node* r);
void postOrder(struct node* r);
int main()
{   root = NULL;
    int n, v,i,c,e,ele;
    c=1;
    while(c!=4)
    {
       printf("Enter your choice :\n1.Insert\n2.Search\n3.Recursive Traversal\n4.Exit\n");
       scanf("%d",&c);
       if(c==1)
       {
           printf("Enter the element to insert : ");
           scanf("%d",&ele);
           root=insert(root,ele);
       }
       else if(c==2)
       {
            printf("\nEnter the element to search : ");
            scanf("%d",&ele);
            search(root,ele);
       }
       else if(c==3)
       {
           printf("Enter your choice :\n1.Preorder\n2.Postorder\n3.Inorder\n");
           scanf("%d",&n);
           if(n==1)
           {
               printf("Preorder Traversal: ");
               preOrder(root);
           }
           else if(n==2)
           {
               printf("Postorder Traversal: ");
               postOrder(root);
               printf("\n");

           }
           else
           {
               printf("Inorder Traversal: ");
               inOrder(root);
               printf("\n");
           }
       }
    return 0;
}

struct node* insert(struct node* r, int data)
{
    if(r==NULL)
    {
        r = (struct node*) malloc(sizeof(struct node));
        r->value = data;
        r->left = NULL;
        r->right = NULL;
    }
    else if(data < r->value){
        r->left = insert(r->left, data);
    }
    else {
        r->right = insert(r->right, data);
    }
    return r;

}

void inOrder(struct node* r)
{
    if(r!=NULL){
        inOrder(r->left);
        printf("%d ", r->value);
        inOrder(r->right);
    }
}

void preOrder(struct node* r)
{
    if(r!=NULL){
        printf("%d ", r->value);
        preOrder(r->left);
        preOrder(r->right);
    }
}

void postOrder(struct node* r)
{
    if(r!=NULL){
        postOrder(r->left);
        postOrder(r->right);
        printf("%d ", r->value);

    }
}
void search(struct node* root,int number)
{
    if(root==NULL){
        printf("The tree is empty\n");
    }
    else if(root->value==number){
       printf("The data  is found\n");
    }
    else if(number<=root->value){
        return search(root->left,number);
    }
    else{
        return search(root->right,number);
    }


}