#include <stdio.h>
#include <stdlib.h>



typedef struct Node {
    struct Node *left;
    struct Node *right;
    int data;
}Node;


Node *create_node(int value){
   Node * n = malloc(sizeof(Node));
   n->left =  NULL;
   n->right = NULL;
   n->data = value;
   return n;
}

//-------------------------Traversals----------------------------------
void prerder_traversal(Node * current){
    if(current==NULL){
        return;
    }
    printf("-> %d",current->data);
    prerder_traversal(current->left);
    prerder_traversal(current->right);
}

void inorder_traversal(Node * current){
    if(current==NULL){
        return;
    }
    inorder_traversal(current->left);
    printf("-> %d",current->data);
    inorder_traversal(current->right);
}


void postorder_traversal(Node * current){
    if(current==NULL){
        return;
    }
    printf("-> %d",current->data);
    postorder_traversal(current->left);
    postorder_traversal(current->right);
}
//---------------------------------------------------


void insert_data(int value , Node *root_){

   Node *t = malloc(sizeof(Node));
   t->left =  NULL;
   t->right = NULL;
   t->data = value;

   if(root_==NULL){
      root_ = t;
   }
   else
   {
      Node *curr, *parent;
      curr = root_;

      while(curr){
           parent = curr;
          // printf("Current traversing node :- %d\n",curr->data);

           if(value > curr->data){
               curr = curr->right;
           }else{
               curr = curr->left;
           }
      }

  //parent pointer is now at the correct position
  if(parent->data > value){
     parent->right = t;

  }else if(parent->data < value){
     parent->left = t;

  }else{
    printf("Duplicate found !");
  }
}

}




int main(){

Node * root = create_node(20);



root->left = create_node(10);
root->right = create_node(30);


insert_data(70,root);
insert_data(13,root);
printf("\n\n");
insert_data(23,root);
insert_data(11,root);
insert_data(24,root);
insert_data(9,root);
insert_data(12,root);
insert_data(10,root);
insert_data(21,root);
insert_data(47,root);
insert_data(50,root);
insert_data(35,root);

printf("Pre order traversal \n");
prerder_traversal(root);
printf("\n\n");

printf("In order traversal \n");
inorder_traversal(root);
printf("\n\n");

printf("Post order traversal \n");
postorder_traversal(root);
printf("\n\n");

return 0;
}