deletion in BST
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
Comments