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

struct node{
    struct node *right;
    struct node *left;
    int data;
};

void insertnode(struct node **p_treetop,int data1);
void inorder(struct node *treetop);
void preorder(struct node *treetop);
void postorder(struct node *treetop);
int depth(struct node *treetop);
signed int del(struct node **p_treetop,int elmt);

int main() {
    struct node *treetop = NULL;
    int elmt,choice;

    puts("1.depth");
    puts("2.insert element");
    puts("3.inorder");	
    puts("4.pretorder");
    puts("5.postoder");
    puts("6.delete elmt");
    puts("7.exit");

    while(1) {	
        puts("pls enter choice:");
        scanf("%d",&choice); 	
	
        switch(choice) {
        case 1:
            printf("depth = %d\n",(elmt=depth(treetop))?elmt-1:0);
            break;       
        case 2:			
            puts("pls enter elmt to insert");
            scanf("%d",&elmt);
            insertnode(&treetop,elmt);				
            break;
        case 3:			
            inorder(treetop);
            puts("");
            break;				
        case 4:			
            preorder(treetop);
            puts("");
            break;				
        case 5:			
            postorder(treetop);
            puts("");
            break;				
        case 6:			
            puts("pls enter elmt to delete");
            scanf("%d",&elmt);
            elmt = del(&treetop,elmt);
            if(elmt < 0) puts("elmt not found");
            else printf("deleted %d\n",elmt);
            break;
        case 7:
            exit(0);
        default:
            puts("wrong choice");
        }
    }
    return 0;
}

void insertnode(struct node **p_treetop,int data1) {

    if(*p_treetop == NULL) {
        struct node *new = (struct node*) malloc(sizeof(struct node));
        new -> data = data1;
        *p_treetop = new;
    }
    else {
        if((*p_treetop) -> data > data1)
            insertnode(&((*p_treetop)->left),data1);
        else
            insertnode(&((*p_treetop)->right),data1);
    }
}

void inorder(struct node *treetop) {
    if(treetop) {
        inorder(treetop->left);
        printf("%d ",treetop->data);
        inorder(treetop->right);
    }
    else
        return;	
}

void preorder(struct node *treetop) {
    if(treetop) {
        printf("%d ",treetop->data);
        preorder(treetop->left);
        preorder(treetop->right);
    }
    else
        return;	
}

void postorder(struct node *treetop) {
    if(treetop) {
        postorder(treetop->left);
        postorder(treetop->right);
        printf("%d ",treetop->data);
    }
    else
        return;	
}

int depth(struct node *treetop) {
    int max,temp;

    if(!treetop)
        return 0;
    else {
        temp = max;
        max = depth(treetop -> left);
        if(max < (temp = depth(treetop -> right)))            
            max = temp;
        return (max+1);
    }
}

signed int del(struct node **p_treetop,int elmt) {
    signed int tmp;
    struct node **tmp1;

    if ((*p_treetop) == NULL)
        return -1; 
    else if((*p_treetop) -> data == elmt) {        
        if((*p_treetop) -> left) { //does node to del has left sub tree            
            tmp = (*p_treetop) -> data;

            struct node **trav = &((*p_treetop) -> left);

            while((*trav) -> right) //search for largest elmt in right sub tree
                *trav = (*trav) -> right;
            (*p_treetop) -> data = (*trav) -> data; //replace node data with this elmt

            while((*trav) -> left) { //does it have further elmt to the left
                (*trav) -> data = (*trav) -> left -> data; //shift tree one step up
                (*trav) = (*trav) -> left;
            }
            free(*trav);

            *trav = NULL;
            return tmp;
        }
        else if((*p_treetop) -> right) { //does node to del has a right subtree
            tmp = (*p_treetop) -> data;

            struct node **trav = &((*p_treetop) -> right);


            while((*trav) -> left) { //search for smallest elmt in left sub tree
                *tmp1 = *trav;
                *trav = (*trav) -> left;
            }

            (*p_treetop) -> data = (*trav) -> data; //replace node data with this elmt

            while((*trav) -> right) { //does it have further elmt to the right?
                (*trav) -> data = (*trav) -> right -> data; //shift tree one step up
                (*trav) = (*trav) -> right;
            }

            free(*trav);
            *trav = NULL;

            return tmp;
        }
        else {
            tmp = (*p_treetop) -> data;
            free((*p_treetop));
            *p_treetop = NULL;
            return tmp;
        }

    }
    else if((*p_treetop) -> data > elmt)
        return(del(&((*p_treetop) -> left),elmt));
    else if((*p_treetop) -> data < elmt)
        return(del(&((*p_treetop) -> right),elmt));    
}

struct node *new = (struct node*) malloc(sizeof(struct node));

struct node *new = (struct node*) calloc(1,sizeof(struct node));