#include<stdio.h>
#include<stdlib.h>
//This structure will store the contents of a node ([left child pointer | Data | right child pointer]).
//Both the pointers will have to point another node so, they has to be of type node.
//If we want to store the address of an int we used to declare the point as int *p, similarly,
//here we want to store the address of child nodes (represented by our structure BST) that's why,
//struct BST *lchild, *rchild
//typedef is used so that we can use "node" variable name for our structure instead of "struct BST" 
typedef struct BST {
   int data;
   struct BST *lchild, *rchild;
} node;
// "insert" function is written to add a new element to the BST. Two arguments are passed into this, first one is
//the address of root node of the BST and second is address of the newly created node, to be inserted. 
void insert(node *, node *);
//"inorder" function is written to display the tree with in-order traversal. The argument passed is the address of 
//the root node.
void inorder(node *);
//"preorder" function is written to display the tree with pre-order traversal. The argument passed is the address 
//of the root node.
void preorder(node *);
//"postorder" function is written to display the tree with post-order traversal. The argument passed is the address 
//of the root node.
void postorder(node *);
//"get_node" function is written to create a new node and return the address of the newly created node
node *get_node(); 

int main() {
   int choice;  // this variable is used to select the display method of the tree
   char ans = 'N'; //to ask user whether to insert more nodes. Default is "N" and will continue for "y"
   //new_node is to store the address of newly created node, root is store the address of root node (required
   //as the starting point of the tree. (Same as start pointer in a link list).
   node *new_node, *root, *tmp; 
   root = NULL; //initializing the root to be NULL
 
   printf("\nProgram For Binary Search Tree ");
    do {
            new_node = get_node();    // a node is created
            printf("\nEnter The Element ");
            scanf("%d", &new_node->data);  // data of the node
 
            if (root == NULL) // The tree is empty (no root node)
               root = new_node;  // created node is treated as root ode and used for futur to start with
            else
               //root node is created, call insert to add newly created node to tree, passing the address of 
               //root node to (starting point of the link list/tree) and the address of newly created node
               insert(root, new_node);  
             printf("\nWant To enter More Elements?(y/n)");
            scanf("%s",&ans);
        } while (ans == 'y');
 
        if (root == NULL)
            printf("Tree Is Not Created");
        else 
         {
            printf("\nThe Inorder display : ");
            inorder(root);    //the address of root is passed so start with (start of link list)
            printf("\nThe Preorder display : ");
            preorder(root);
            printf("\nThe Postorder display : ");
            postorder(root);
         }
       
 return 0;     
}
/*
 Get new Node
 */
node *get_node() {
   node *temp;
   temp = (node *) malloc(sizeof(node));  //memory is created of size node and address of it is returned 
   temp->lchild = NULL;  //both the child nodes are pointing to NULL (no children are created for it till now).
   temp->rchild = NULL;
   return temp; // return the address of newly created node
}
/*
 This function is for creating a binary search tree
 */
void insert(node *root, node *new_node) {
   //to check whether the node has to be inserted in left or right side
   if (new_node->data < root->data) { //if new nodes data is < the root node data, add to the left side
      if (root->lchild == NULL) //if no left child is created till now
         root->lchild = new_node; //add the new node as left child
      else
         insert(root->lchild, new_node); //otherwise, assume the left child as root node and insert new node to this sub-tree
   }
 
   if (new_node->data > root->data) {//if new nodes data is > the root node data, add to the right side
      if (root->rchild == NULL) //if no right child is created till now
         root->rchild = new_node; //add the new node as right child
      else
         insert(root->rchild, new_node); //otherwise, assume the right child as root node and insert new node to this sub-tree
   }
}
      
/*
 This function displays the tree in inorder fashion
 */
void inorder(node *temp) {  //temp is the address of root of the tree
   if (temp != NULL) { //to check that tree is not empty
      inorder(temp->lchild); //traverse the left sub-tree first recursively, until the NULL is found
      printf("%d", temp->data); // print the data
      inorder(temp->rchild); //traverse the right sub-tree recursively
   }
}
/*
 This function displays the tree in preorder fashion
 */
void preorder(node *temp) {
   if (temp != NULL) {
      printf("%d", temp->data);
      preorder(temp->lchild);
      preorder(temp->rchild);
   }
}
 
/*
 This function displays the tree in postorder fashion
 */
void postorder(node *temp) {
   if (temp != NULL) {
      postorder(temp->lchild);
      postorder(temp->rchild);
      printf("%d", temp->data);
   }
}