Binary Search Tree

BST

/* Harsh Gupta */
/* 12MA20017 */
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    struct node * parent;
    struct node * left_child;
    struct node * right_child;
    int key;
}node;

node* creat_node();
node* create_bst(node *x, const int A[], const int size);
void inorder_tree_walk(const node* x);
void inorder_tree_walk_nonrec(node* x);
node* insert_into_bst(node *x, int data);
node* search(node* x, int k);
node* max(node* x);
node* min(node* x);
node* succesor(node* x);
node* preceder(node* x);
inline void transplant( node* x, node* y);
node* Delete(node* z);

int main(){
    int A[] = {9,2,10,-10,3,4,5,6};
    int n = 8;
    node *x=NULL;
    x = create_bst(x, A, n);
    inorder_tree_walk_nonrec(x);
    /* printf("\n%d \n", (search(x, 4))->key); */
    printf("The minimum of the tree is: %d\n", min(x)->key);
    printf("The maximum of the tree is: %d\n", max(x)->key);
    printf("The succesor of 6 is: %d\n", succesor(search(x, 6))->key);
    printf("The preceder of 9 is: %d\n", preceder(search(x, 9))->key);
    Delete(search(x, 10));
    printf("The maximum of the tree is: %d\n", max(x)->key);
    Delete(search(x, 4));
    inorder_tree_walk_nonrec(x);
    /* node *y = (search(x, 6))->right_child; */
    /* printf("--%d--\n",min(y)->key); */
    return 0;
}

node* creat_node(){
    node *n = (node *)malloc(sizeof(node));
    n->parent = NULL;
    n->right_child = NULL;
    n->left_child = NULL;
    n->key = 0;
    return n;
}

node* insert_into_bst(node *x, int data){
    if(x==NULL){
        x = creat_node();
        x->key = data;
        return x;
    }
    if(data> x->key){
        if(x->right_child == NULL){
            x->right_child = creat_node();
            (x->right_child)->key = data;
            (x->right_child)->parent = x;
            return x;
        }
        else
            x->right_child = insert_into_bst(x->right_child, data);
    }
    else{
        if(x->left_child == NULL){
            x->left_child = creat_node();
            (x->left_child)->key = data;
            (x->left_child)->parent = x;
            return x;
        } 
        else
            x->left_child = insert_into_bst(x->left_child, data);
    }
    return x;
}

node* create_bst(node *x, const int A[], const int size){
    int i;
    for(i=0;i<size; i++){
        x = insert_into_bst(x, A[i]);
    }
    return x;
}

void inorder_tree_walk(const node* x){
    if(x != NULL){
        inorder_tree_walk(x->left_child);
        printf("%d ", x->key);
        inorder_tree_walk(x->right_child);
    }
}

void inorder_tree_walk_nonrec(node* x){
    /* node* r = x; */
    node* p;
    node* q;
    node* y = x;


    while(y->left_child !=NULL) y = y->left_child;
    p = y;

    y = x;

    while(y->right_child !=NULL) y = y->right_child;
    q = y;

    y = x;

    printf("%d ",p->key);

    while(p !=q ){
        p = succesor(p);
        printf("%d ",p->key);
    }
}

node* search(node*x, int k){
    while(x !=NULL && x->key != k){
        if(k < x->key){
            x = x->left_child;
        }
        else
            x= x->right_child;
    }
    return x;
}

node* max(node* x){
    while(x->right_child != NULL){
        x = x->right_child;
    }
    return x;
}

node* min(node* x){
    while(x->left_child != NULL){
        x = x->left_child;
    }
    return x;
}

node* succesor(node* x){
    if(x->right_child != NULL){
        return min(x->right_child);
    }

    node* y = x->parent;
    while(y != NULL && y->right_child == x){
        x = y;
        y = y->parent;
    }
    return y;
}

node* preceder(node* x){
    if(x->left_child != NULL){
        return max(x->left_child);
    }

    node* y = x->parent;
    while(y != NULL && y->left_child == x){
        x = y;
        y = y->parent;
    }
    return y;
}

// The function is inline to make sure the changes 
// reflect on the original tree
inline void transplant(node* x, node* y){
    if(x == (x->parent)->left_child){
        (x->parent)->left_child = y;
    }
    else 
        (x->parent)->right_child = y;
    if(y !=NULL)
        y->parent = x->parent;

}

// The Function doesn't return the root node
// Instead it returns the Deleted node so that can be 
// freed or used somewhere else
node* Delete(node* z){
    if(z->left_child == NULL)
        transplant(z, z->right_child);
    else if(z->right_child == NULL)
        transplant(z, z->left_child);
    else {
        node *y = min(z->right_child);
        if(y->parent !=z){
            transplant(y, y->right_child);
            y->right_child = z->right_child;
            (y->right_child)->parent = y;
        }
        transplant(z, y);
        y->left_child = z->left_child;
        (y->left_child)->parent = y;
    }
    return z;
        
}