78_deletion_BST.c

#include <stdio.h>
#include <stdlib.h>
struct node{
    int data;
    struct node* left;
    struct node* right;
};

struct node* createNode(int data){
    struct node *n;
    n = (struct node *)malloc(sizeof(struct node));
    n->data = data;
    n->left = NULL;
    n->right = NULL;
    return n;
};

void inorder(struct node* root){
    if(root!=NULL){
        inorder(root->left);
        printf("%d ",root->data);
        inorder(root->right);
    }
}
int isBST(struct node* root){
   static struct node *prev = NULL;
    if(root!=NULL){
        if(!isBST(root->left)){
            return 0;
        }
        prev = root;
        return isBST(root->right);
    }
    else{
        return 1;
    }
}

struct node *inorderPredecessor(struct node *root){
    root = root->left;
    while(root->right !=NULL){
        root =root->right;
    }
    return root;
}
struct node *deleteNode(struct node *root,int value){
    struct node *iPre;
    if(root == NULL)
    {
        return root;
    }
    if(root->left == NULL && root->right == NULL){
        free(root);
        return NULL;
    }
    //Search for the node to be deleted
    if(value<root->data){
       root->left = deleteNode(root->left,value);
    }
    else if(value>root->data){
        root->right = deleteNode(root->right,value);
}

    //Deletion Strategy when the node is found
    else{
        iPre = inorderPredecessor(root);
        root->data = iPre->data;
        root->left = deleteNode(root->left,iPre->data);
    }
    return root;
}


int main(){
    struct node *p = createNode(5);
    struct node *p1 = createNode(3);
    struct node *p2 = createNode(6);
    struct node *p3 = createNode(1);
    struct node *p4 = createNode(4);


    //Linking the root node with left and right children
    p->left = p1;
    p->right = p2;
    p1 ->left = p3;
    p1->right = p4;

    inorder(p);
    printf("\n");
    printf("|Data is %d \n",p->data);
    deleteNode(p,3);
    inorder(p);
    return 0;
}