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

/*--------- STRUCTURE DECLARATION ----------*/
struct bin_tree_node
{
    int val,count;;
    struct bin_tree_node* left;
    struct bin_tree_node* right;
};
typedef struct bin_tree_node BTNODE;

/*--------PRESS ENTER------ - */
void  press_enter()
{
    printf("\nPress ENTER to continue");
    getchar();
    while (getchar() != '\n');
}
/*--------- CREATE A NODE ------------------*/
BTNODE* newnode(int val)
{
    BTNODE *btnode = (BTNODE*)malloc(sizeof(BTNODE));
    //btnode->count = 0;
    btnode->val = val;
    btnode->left = NULL; 
    btnode->right = NULL;
    return btnode;
}
/*---------- ADD A NODE IN THE TREE ------------------*/
BTNODE* addnode(BTNODE* root, int val) 
{
    BTNODE* p;
    // ! printf("\n%p:(%d)\n", root,val);
    if (root == NULL)
    {
        p = newnode(val);
     // ! printf("\n%p:(%d) l:%p r:%p\n", p,p->val, p->left, p->right);// to Display
        return p;
    }
    if (val < root->val)
    {
      //  printf("\n%p:(%d) l:%p r:%p\n", root, root->val, root->left, root->right); // to Display
        root->left = addnode(root->left, val);
      //  printf("\n%p:(%d) l:%p r:%p\n", root, root->val, root->left, root->right); // to Display
    }
    else if (val > root->val)
    {
     //   printf("\n%p:(%d) l:%p r:%p\n", root, root->val, root->left, root->right); // to Display
        root->right = addnode(root->right, val);
     //   printf("\n%p:(%d) l:%p r:%p\n", root, root->val, root->left, root->right); // to Display
    }
        
    // ! printf("\n%p:(%d) l:%p r:%p\n", root,root->val, root->left, root->right); // to Display
    return root;
}
/*--------- ADD A NODE IN THE TREE ALTERNATIVELY ---------*/
/*--------- USING A VOID FUNCTION  -----------------------*/
void addnode1(BTNODE** subroot, int val)
{
    BTNODE* p;
    p = *subroot;
    if (p == NULL) p = newnode(val);//*subroot= newnode(val);
    else
    {
        if (val < p->val) addnode1(&(p->left), val);
        else if (val > p->val) addnode1(&(p->right), val);
    }
}

/*--------- SEARCH A NODE IN THE TREE----------*/
BTNODE* searchnode(BTNODE* p, int val)
{  
   if (p == NULL || p->val == val) return p;
   
   if (val < p->val) 
       return searchnode(p->left, val);
   else 
       return searchnode(p->right, val);
}
/*---------- DELETE THE TREE AND FREE THE MEMORY -------*/
void deltree(BTNODE* p) {
    if (p != NULL)
    {
        deltree(p->left);
        deltree(p->right);
        free(p);
    }
}
/*-------------------------*/
void preorder(BTNODE*  p)
{
    if (p != NULL)
    {
        printf("%u(%d): left:%u, right:%u\n",(int)p, p->val,(int)p->left, (int)p->right);
        preorder(p->left);
        preorder(p->right);
    }
}
/*-------------------------*/
void inorder(BTNODE* p)
{
    if (p != NULL)
    {
        inorder(p->left);
        //inorder(p->right); /*descending order*/
        printf("%u(%d): left:%u, right:%u\n", (int)p, p->val, (int)p->left, (int)p->right);
        inorder(p->right);
        //inorder(p->left);  /*descending order*/
    }
}
/*---------------------------*/
void postorder(BTNODE* p)
{
    if (p != NULL)
    {
        postorder(p->left);
        postorder(p->right);
        printf("%u(%d): left:%u, right:%u\n", (int)p, p->val, (int)p->left, (int)p->right);
    }
}

/*-------------------------------------------*/
BTNODE* findLeftOfRightSubTree(BTNODE* p) 
{
    while (p->left != NULL) p = p->left;
    return p;
}
/*-- delete a node from the binary tree --*/
BTNODE* deleteNode(BTNODE* p, int value)
{
    BTNODE* temp;

    if (p == NULL) {
        return p; 
    }
    
    /* find the node to delete */
    if (value < p->val) 
       p->left = deleteNode(p->left, value);
    else if (value > p->val) 
       p->right = deleteNode(p->right, value);
    else 
    {
        /* Node with the value found */
        if (p->left == NULL) {
            /*  No left child  */
            temp = p->right;
            free(p);
            return temp;
        }
        else if (p->right == NULL) {
            /*  No right child  */
            temp = p->left;
            free(p);
            return temp;
        }
        /* Node with two children */
        temp = findLeftOfRightSubTree(p->right);  
        p->val = temp->val;             
        p->right = deleteNode(p->right, temp->val); 
    }
    return p;
}
/*----------------------------*/

void main(void)
{
    BTNODE* root=NULL, *p;
   
    root = addnode(root, 4);
    root = addnode(root, 5);
    root = addnode(root, 3);
    root = addnode(root, 8);
   
    inorder(root);
    printf("-- Delete node --\n");
    root = deleteNode(root, 4);
    inorder(root);
    
    root = addnode(root, 10);
    root = addnode(root, 20);
    root = addnode(root, 25);
    addnode1(&root, 1);
    addnode1(&root, 15);
    addnode1(&root, 7);
    root = addnode(root, 30);
    
    
    printf("\n-- Inorder --\n");
    inorder(root);
    
    printf("\n-- Preorder --\n");
    preorder(root);
        
    printf("\n-- Postorder --\n");
    postorder(root);

    printf("\n-- Search a value in the tree --\n");
    p = searchnode(root, 5);
    if (p) printf("%p:%d\n",p, p->val);
    else printf("value not found\n");
    
    deltree(root);
}