#include <stdio.h>
#include <stdlib.h>
struct treeN
{
int data;
struct treeN *left;
struct treeN *right;
};
struct treeN *BSTcreate(struct treeN *root, int val)
{
if (root== NULL)
{
struct treeN *root = malloc(sizeof(struct treeN));
root->data = val;
root->left = NULL;
root->right = NULL;
return root;
}
if (val < root->data)
{
root->left = BSTcreate(root->left, val);
}
else
{
root->right = BSTcreate(root->right, val);
}
return root;
}
void inorder(struct treeN *root)
{
if (root != NULL)
{
inorder(root->left);
printf(" %d ", root->data);
inorder(root->right);
}
}
struct treeN *inordersucc(struct treeN *root){
struct treeN *ptr = root;
while(ptr && ptr->left != NULL){
ptr = ptr->left;
}
return ptr;
}
struct treeN* delete(struct treeN*root, int val){
if(val<root->data){
root->left = delete(root->left,val);
}
else if(val>root->data){
root->right = delete(root->right,val);
}
else{
if(root->left == NULL){ // This will delete only leaf node
struct treeN *x = root->right;
free(root);
return x;
}
else if(root->right == NULL){ // This will also delete only leaf node
struct treeN *x = root->left;
free(root);
return x;
}
else{
struct treeN *x = inordersucc(root->right);
root->data = x->data;
root->right = delete(root->right, x->data);
}
return root;
}
}
int main()
{
struct treeN *root = NULL;
root = BSTcreate(root, 43);
BSTcreate(root, 10);
BSTcreate(root, 79);
BSTcreate(root, 90);
BSTcreate(root, 12);
BSTcreate(root, 54);
BSTcreate(root, 11);
BSTcreate(root, 9);
BSTcreate(root, 50);
printf("\nRoot is: %d\n",root->data);
inorder(root);
printf("\n");
delete(root,43);
inorder(root);
printf("\nRoot is: %d",root->data);
return 0;
}
Comments
Post a Comment