deletion in BST

PHOTO EMBED

Sat Jun 18 2022 06:30:41 GMT+0000 (Coordinated Universal Time)

Saved by @KanishqJ8

#include <stdio.h>
#include <malloc.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);
    }
}

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 NULL;
    }
    if(root->left==NULL && root->right==NULL){
        free(root);
        return NULL;
    }
    //searching 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);
    }
    //node 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);
    
    p->left=p1;
    p->right=p2;
    p1->left=p3;
    p1->right=p4;
    
    InOrder(p);
    deleteNode(p,3);
    printf("\n");
    InOrder(p);
    
    return 0;
}
content_copyCOPY