BINARY SEARCH TREE WITH ALL OPERATIONS

Guys !!! This post is not a part of spoj - solution. Actually, i've made it to letting you all know how to implement BST with all possible operation. I tried  my level best to make it easier and readable. But still, if you are facing problem in any part, feel free to ask. And do comment if you get any mistake , bug or anything regarding it. 

Program Design Strategy :

1. Main Function. -  At very first, it will ask to make a tree.
It uses function ( FPN - insert( node **,int ) )  and all three traversal using recursion.
     
                                                                   Menu bar

    1.1. Append Tree.      ( FPN -  insert_own(node **,int ) ).

    1.2. Search node.      ( FPN -  search_own(node *,int ) ).

    1.3. Delete node.       ( FPN -  del_own(node **,int ) ).
            Firstly, it will look for the node to be deleted exits or not.print "Not Found " if not present or else check whether its a root or else and according call the function ( FPN -  del_root( node ** ).

    1.4. Preorder Traversal     ( FPN - preorder_own( node *) )    using STACK.
    
    1.5. Inorder  Traversal     ( FPN - inorder_own( node * ) )     using STACK.

    1.6. Postorder Traversal     (   FPN - postorder_own ( node * ) )    using STACK.
     
    And  at last make the tree empty, and terminate.

    FPN - ( Function Prototype name ).
    
    I prefer mail over comment. So, do email me up,here is my email id : surajjumpy@gmail.com 
    
   Thanks.

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

#define S struct

S node
{
    int val;
    S node *left, *right;
}*root = NULL,*stack[100];


int hold_stack[100000];  ////  USED IN POSTORDER TRAVERSAL TO HOLD VALUES IN REVERSE ORDER   


/////////         INSERTING NODE RECURSIVELY              

void insert(S node **root, int val)
{
    S node *temp;

    if( *root == NULL)
    {
        temp = (S node *)malloc(sizeof(S node));

        if(temp == NULL)
        {
            printf(" Sorry !!! Overflow node couldn't be created");     ////   PRINT WHEN UNABLE TO ALLOCATE MEMORY TO THE NODE
            return;
        }

        temp->val = val;    temp->left = temp->right = NULL;    //////    INITIALIZE THE NODE

        printf("Create Node %i\n",temp->val);

        *root = temp;

        return;
    }

    else
    {
        if(val >= (*root)->val)
        {
            printf("Turn Right\n");              /////       TRACE       /////
            insert( &((*root)->right) , val);    ////        THE        /////
        }                                       /////        PATH       /////
        else
        {
            printf("Turn Left\n");
            insert( &((*root)->left) , val);
        }
    }
}

////////      CREATION OF NODE WITH ITERATIVE METHOD      

void insert_own(S node **root,int val)
{
    S node *temp, *trav = *root;

    temp = (S node *)malloc(sizeof(S node));

    if(temp == NULL)
    {
        printf(" Sorry !!! Overflow node couldn't be created");    ///// PRINT WHEN UNABLE TO CREATE NODE
        return;
    }

    temp->val = val;    temp->left = temp->right = NULL;

    if( *root == NULL )
    {
        *root = temp;
        printf(" HEY !!! ITs A ROOT NODE \n");   /////    SPECIFY THE ROOT NODE CREATION
        return;
    }

    else
    {
        while( ( val >= trav->val && trav->right != NULL ) || ( val < trav->val && trav->left != NULL ) )
        {
            if( val >= trav->val )
            {
                printf("Turn Right \n");         //////     TRACE     ///////
                trav = trav->right;              //////     THE       ///////
            }                                    //////    PATH       //////

            else
            {
                printf("Turn Left\n");
                trav = trav->left;
            }
        }

        if( val >= trav->val )
        {
            printf("Put %i right to the %i\n",val,trav->val);
            trav->right = temp;
        }
                    ///////   FINALLY, CLARIFY PLACE TO PUT NODE /////
        else
        {
            printf("Put %i left to the %i\n",val,trav->val);
            trav->left = temp;
        }
    }
}

//////    RECURSIVE PRE - ORDER TRAVERSAL      

void preorder( S node *temp )
{
    if(temp != NULL)
    {
        printf("%i, ",temp->val);
        preorder(temp->left);
        preorder(temp->right);
    }

    return;
}

///////       RECURSIVE  IN - ORDER TRAVERSAL        /////////

void inorder( S node *temp )
{
    if(temp != NULL)
    {
        inorder(temp->left);
        printf("%i, ",temp->val);
        inorder(temp->right);
    }

    return;
}

///////    RECURSIVE POST-ORDER TRAVERSAL       ////////


void postorder( S node *temp )
{
    if(temp != NULL)
    {
        postorder(temp->left);
        postorder(temp->right);
        printf("%i, ",temp->val);
    }
}


///////   SEEK FOR A NODE  && TRACE THE PATH  ////////////


void search_own(S node *temp,int val)
{
   S node *hold_temp;   char str[40];   int i = -1,j;

   while(temp != NULL)
   {
        hold_temp = temp;

        if(val == temp->val)
            break;

        else if( val > temp->val && temp->right != NULL)
        {
            str[++i] = 'R';
            temp = temp->right;
        }

        else if( val < temp->val && temp->left != NULL)
        {
            str[++i] = 'L';
            temp = temp->left;
        }

        if( hold_temp == temp )
            break;
   }

   if(val == temp->val)
   {
        printf("\nPick the ROOT node\n");

        j = -1;
        while(++j <= i)
            ( str[j] == 'R' ) ? ( printf("Turn Right\n") ) : ( printf("Turn Left \n") );
   }

   else
   {
        printf("\n  Number wasn't found \n");
        return;
   }
}

/////////      DELETE THE SELECTED NODE          ///////////


void del_root(S node **root)
{
    S node *temp = *root,*hold, *temp_hold_root = *root;

    if( (*root)->left == NULL && (*root)->right == NULL )
    {
        *root = NULL;
        free(temp);
    }

    else
    {
        if(temp->right != NULL)
        {
            hold = temp;
            temp = temp->right;

            while( temp->left != NULL)
            {
                hold = temp;
                temp = temp->left;
            }

            if(hold != *root)
                hold->left = temp->right;
            else
                (*root)->right = temp->right;
            temp->left = (*root)->left;
            temp->right = (*root)->right;
            *root = temp;
            free(temp_hold_root);
        }

        else
        {
            (*root) = (*root)->left;
            free(temp);
        }
    }
}

//////         SEARCH FOR THE DELETING NODE            ///////////

void del_own(S node **root,int val)
{
    S node *temp = *root,*back = NULL,*hold;    char ch;

    if(*root == NULL)
    {
        printf(" Sorry !!! But Tree is empty \n");
        return;
    }

    else if( (*root)->val == val )
    {
       del_root(root);
    }

    else
    {

        while(temp != NULL)
        {
            hold = temp;

            if( val == temp->val )
                break;

            else if( val > temp->val && temp->right != NULL)
            {
                back = temp;
                ch = 'R';
                temp = temp->right;
            }

            else if( val < temp->val && temp->left != NULL)
            {
                back = temp;
                ch = 'L';
                temp = temp->left;
            }

            if( hold == temp )
                break;
        }

        if(val == temp->val)
        {
            if(ch == 'L')
                del_root(&(back->left));
            else
                del_root(&(back->right));
        }
        else
        {
            printf("\nNode wasn't found \n");
            return;
        }
    }
    printf("\n");
    inorder(*root);
    printf("\n");
}

///////      PREORDER TRAVERSAL USING STACK    ////////

void preorder_own(S node *temp)
{
    int i = -1,flag = 0;

    if( temp != NULL )
        flag = 1;

    while( flag )
    {
        printf("%i , ",temp->val);

        if(temp->right != NULL)
            stack[++i] = temp->right;

        if(temp->left != NULL)
        {
            temp = temp->left;
        }
        else
        {
            if(i >= 0)
            {
                temp = stack[i];
                i--;
            }
            else
                flag = 0;
        }
    }

    printf("\n");
}

////////      IN - ORDER TRAVERSAL      ///////////

void inorder_own(S node *root)
{
    int i = -1, flag = 0;   char trace = 'F';

    while( 1 )
    {
        if(root != NULL)
        {
            stack[++i] = root;
            root = root->left;
        }

        else if(root == NULL && i >= 0)
        {
            root = stack[i];
            printf("%i, ",root->val);
            root = root->right;
            i--;
        }

        else
            break;
    }
}

///////    POST - ORDER TRAVERSAL    /////////

void postorder_own(S node *temp)
{
    int i = -1,index = 0;

    while(1)
    {
        if(temp != NULL)
        {
            if(temp->left != NULL)
                stack[++i] = temp->left;

            hold_stack[index++] = temp->val;
            temp = temp->right;
        }

        else if(temp == NULL && i >= 0)
        {
            temp = stack[i];
            i--;
        }

        else
            break;
    }

    while(--index >= 0)
        printf("%i, ",hold_stack[index]);

}


//////////       DELETE ALL LEFT NODES         /////////////

void del_all_node(S node **temp)
{
    S node *hold = *temp;
    if(*temp != NULL)
    {
        del_all_node(&(*temp)->left);
        del_all_node(&(*temp)->right);

        *temp = NULL;

        free(hold);
    }
}



/////////      MAIN FUNCTION             ////////////////

int main()
{
    int i,j,n;  char ch;

    printf("First of all create Binary tree\n\n");
    printf("Enter number of nodes  :  ");
    scanf("%i",&n);

    while(n--)
    {
        scanf("%i",&i);
        insert(&root,i);
    }

    printf("Preorder Traversal  \n");
    preorder(root);

    printf("\nInorder Traversal  \n");
    inorder(root);

    printf("\nPostorder Traversal \n");
    postorder(root);

    do
    {
        printf("\n");

        i=0;
        while(++i <= 80)
            printf("-");

        printf("\n MENU \n");
        printf(" 1. Append Tree\n");
        printf(" 2. Search \n");
        printf(" 3. Delete Node\n");
        printf(" 4. PREorder Traversal\n");
        printf(" 5. INorder Traversal\n");
        printf(" 6. POSTorder Traversal\n");

        printf(" Enter your choice  :  ");
        scanf("%i",&i);

        switch(i)
        {
            case   1:   printf("Enter the value to be inserted  :  ");
                        scanf("%i",&i);
                        insert_own(&root,i);
                        break;

            case   2:   printf("Enter the value to be searched  :  ");
                        scanf("%i",&i);
                        search_own(root,i);
                        break;

            case   3:   printf("Enter the value to be deleted  :  ");
                        scanf("%i",&i);
                        del_own(&root,i);
                        break;

            case   4:   preorder_own(root);
                        break;

            case   5:   inorder_own(root);
                        break;

            case   6:   postorder_own(root);
                        break;

            default :   printf("\n!!!  Wrong choice !!!\n");
        }

        i = 1;
        printf("\n\n      ...!!!  Enter 0 to exit & else to continue !!!...\n");
        scanf("%i",&i);

    }while(i);


    if(root != NULL)
    {
        // delete all node and move to AVAIL stack

        del_all_node(&root);
    }

    return 0;
}