#include <stdio.h>
#include <stdlib.h>
struct node
{
int data; //node will store an integer
struct node *right_child; // right child
struct node *left_child; // left child
};
struct node* search(struct node *root, int x)
{
if(root==NULL || root->data==x) //if root->data is x then the element is found
return root;
else if(x>root->data) // x is greater, so we will search the right subtree
return search(root->right_child, x);
else //x is smaller than the data, so we will search the left subtree
return search(root->left_child,x);
}
//function to find the minimum value in a node
struct node* find_minimum(struct node *root)
{
if(root == NULL)
return NULL;
else if(root->left_child != NULL) // node with minimum value will have no left child
return find_minimum(root->left_child); // left most element will be minimum
return root;
}
//function to create a node
struct node* new_node(int x)
{
struct node *p;
p
= malloc(sizeof(struct node
)); p->data = x;
p->left_child = NULL;
p->right_child = NULL;
return p;
}
struct node* insert(struct node *root, int x)
{
//searching for the place to insert
if(root==NULL)
return new_node(x);
else if(x>root->data) // x is greater. Should be inserted to right
root->right_child = insert(root->right_child, x);
else // x is smaller should be inserted to left
root->left_child = insert(root->left_child,x);
return root;
}
// funnction to delete a node
struct node* delete(struct node *root, int x)
{
//searching for the item to be deleted
if(root==NULL)
return NULL;
if (x>root->data)
root->right_child = delete(root->right_child, x);
else if(x<root->data)
root->left_child = delete(root->left_child, x);
else
{
//No Children
if(root->left_child==NULL && root->right_child==NULL)
{
return NULL;
}
//One Child
else if(root->left_child==NULL || root->right_child==NULL)
{
struct node *temp;
if(root->left_child==NULL)
temp = root->right_child;
else
temp = root->left_child;
return temp;
}
//Two Children
else
{
struct node *temp = find_minimum(root->right_child);
root->data = temp->data;
root->right_child = delete(root->right_child, temp->data);
}
}
return root;
}
void inorder(struct node *root)
{
if(root!=NULL) // checking if the root is not null
{
inorder(root->left_child); // visiting left child
printf(" %d ", root
->data
); // printing data at root inorder(root->right_child);// visiting right child
}
}
int main()
{
/*
20
/ \
/ \
5 30
/ \ /\
/ \ / \
1 15 25 40
/ \
/ \
9 45
/ \ /
/ \ /
7 12 42
*/
struct node *root;
root = new_node(20);
insert(root,5);
insert(root,1);
insert(root,15);
insert(root,9);
insert(root,7);
insert(root,12);
insert(root,30);
insert(root,25);
insert(root,40);
insert(root, 45);
insert(root, 42);
inorder(root);
root = delete(root, 1);
/*
20
/ \
/ \
5 30
\ /\
\ / \
15 25 40
/ \
/ \
9 45
/ \ /
/ \ /
7 12 42
*/
root = delete(root, 40);
/*
20
/ \
/ \
5 30
\ /\
\ / \
15 25 45
/ /
/ /
9 42
/ \
/ \
7 12
*/
root = delete(root, 45);
/*
20
/ \
/ \
5 30
\ /\
\ / \
15 25 42
/
/
9
/ \
/ \
7 12
*/
root = delete(root, 9);
inorder(root);
/*
20
/ \
/ \
5 30
\ /\
\ / \
15 25 42
/
/
12
/
/
7
*/
return 0;
}
CiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RkbGliLmg+CgpzdHJ1Y3Qgbm9kZQp7CiAgICBpbnQgZGF0YTsgLy9ub2RlIHdpbGwgc3RvcmUgYW4gaW50ZWdlcgogICAgc3RydWN0IG5vZGUgKnJpZ2h0X2NoaWxkOyAvLyByaWdodCBjaGlsZAogICAgc3RydWN0IG5vZGUgKmxlZnRfY2hpbGQ7IC8vIGxlZnQgY2hpbGQKfTsKCnN0cnVjdCBub2RlKiBzZWFyY2goc3RydWN0IG5vZGUgKnJvb3QsIGludCB4KQp7CiAgICBpZihyb290PT1OVUxMIHx8IHJvb3QtPmRhdGE9PXgpIC8vaWYgcm9vdC0+ZGF0YSBpcyB4IHRoZW4gdGhlIGVsZW1lbnQgaXMgZm91bmQKICAgICAgICByZXR1cm4gcm9vdDsKICAgIGVsc2UgaWYoeD5yb290LT5kYXRhKSAvLyB4IGlzIGdyZWF0ZXIsIHNvIHdlIHdpbGwgc2VhcmNoIHRoZSByaWdodCBzdWJ0cmVlCiAgICAgICAgcmV0dXJuIHNlYXJjaChyb290LT5yaWdodF9jaGlsZCwgeCk7CiAgICBlbHNlIC8veCBpcyBzbWFsbGVyIHRoYW4gdGhlIGRhdGEsIHNvIHdlIHdpbGwgc2VhcmNoIHRoZSBsZWZ0IHN1YnRyZWUKICAgICAgICByZXR1cm4gc2VhcmNoKHJvb3QtPmxlZnRfY2hpbGQseCk7Cn0KCi8vZnVuY3Rpb24gdG8gZmluZCB0aGUgbWluaW11bSB2YWx1ZSBpbiBhIG5vZGUKc3RydWN0IG5vZGUqIGZpbmRfbWluaW11bShzdHJ1Y3Qgbm9kZSAqcm9vdCkKewogICAgaWYocm9vdCA9PSBOVUxMKQogICAgICAgIHJldHVybiBOVUxMOwogICAgZWxzZSBpZihyb290LT5sZWZ0X2NoaWxkICE9IE5VTEwpIC8vIG5vZGUgd2l0aCBtaW5pbXVtIHZhbHVlIHdpbGwgaGF2ZSBubyBsZWZ0IGNoaWxkCiAgICAgICAgcmV0dXJuIGZpbmRfbWluaW11bShyb290LT5sZWZ0X2NoaWxkKTsgLy8gbGVmdCBtb3N0IGVsZW1lbnQgd2lsbCBiZSBtaW5pbXVtCiAgICByZXR1cm4gcm9vdDsKfQoKLy9mdW5jdGlvbiB0byBjcmVhdGUgYSBub2RlCnN0cnVjdCBub2RlKiBuZXdfbm9kZShpbnQgeCkKewogICAgc3RydWN0IG5vZGUgKnA7CiAgICBwID0gbWFsbG9jKHNpemVvZihzdHJ1Y3Qgbm9kZSkpOwogICAgcC0+ZGF0YSA9IHg7CiAgICBwLT5sZWZ0X2NoaWxkID0gTlVMTDsKICAgIHAtPnJpZ2h0X2NoaWxkID0gTlVMTDsKCiAgICByZXR1cm4gcDsKfQoKc3RydWN0IG5vZGUqIGluc2VydChzdHJ1Y3Qgbm9kZSAqcm9vdCwgaW50IHgpCnsKICAgIC8vc2VhcmNoaW5nIGZvciB0aGUgcGxhY2UgdG8gaW5zZXJ0CiAgICBpZihyb290PT1OVUxMKQogICAgICAgIHJldHVybiBuZXdfbm9kZSh4KTsKICAgIGVsc2UgaWYoeD5yb290LT5kYXRhKSAvLyB4IGlzIGdyZWF0ZXIuIFNob3VsZCBiZSBpbnNlcnRlZCB0byByaWdodAogICAgICAgIHJvb3QtPnJpZ2h0X2NoaWxkID0gaW5zZXJ0KHJvb3QtPnJpZ2h0X2NoaWxkLCB4KTsKICAgIGVsc2UgLy8geCBpcyBzbWFsbGVyIHNob3VsZCBiZSBpbnNlcnRlZCB0byBsZWZ0CiAgICAgICAgcm9vdC0+bGVmdF9jaGlsZCA9IGluc2VydChyb290LT5sZWZ0X2NoaWxkLHgpOwogICAgcmV0dXJuIHJvb3Q7Cn0KCi8vIGZ1bm5jdGlvbiB0byBkZWxldGUgYSBub2RlCnN0cnVjdCBub2RlKiBkZWxldGUoc3RydWN0IG5vZGUgKnJvb3QsIGludCB4KQp7CiAgICAvL3NlYXJjaGluZyBmb3IgdGhlIGl0ZW0gdG8gYmUgZGVsZXRlZAogICAgaWYocm9vdD09TlVMTCkKICAgICAgICByZXR1cm4gTlVMTDsKICAgIGlmICh4PnJvb3QtPmRhdGEpCiAgICAgICAgcm9vdC0+cmlnaHRfY2hpbGQgPSBkZWxldGUocm9vdC0+cmlnaHRfY2hpbGQsIHgpOwogICAgZWxzZSBpZih4PHJvb3QtPmRhdGEpCiAgICAgICAgcm9vdC0+bGVmdF9jaGlsZCA9IGRlbGV0ZShyb290LT5sZWZ0X2NoaWxkLCB4KTsKICAgIGVsc2UKICAgIHsKICAgICAgICAvL05vIENoaWxkcmVuCiAgICAgICAgaWYocm9vdC0+bGVmdF9jaGlsZD09TlVMTCAmJiByb290LT5yaWdodF9jaGlsZD09TlVMTCkKICAgICAgICB7CiAgICAgICAgICAgIGZyZWUocm9vdCk7CiAgICAgICAgICAgIHJldHVybiBOVUxMOwogICAgICAgIH0KCiAgICAgICAgLy9PbmUgQ2hpbGQKICAgICAgICBlbHNlIGlmKHJvb3QtPmxlZnRfY2hpbGQ9PU5VTEwgfHwgcm9vdC0+cmlnaHRfY2hpbGQ9PU5VTEwpCiAgICAgICAgewogICAgICAgICAgICBzdHJ1Y3Qgbm9kZSAqdGVtcDsKICAgICAgICAgICAgaWYocm9vdC0+bGVmdF9jaGlsZD09TlVMTCkKICAgICAgICAgICAgICAgIHRlbXAgPSByb290LT5yaWdodF9jaGlsZDsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgdGVtcCA9IHJvb3QtPmxlZnRfY2hpbGQ7CiAgICAgICAgICAgIGZyZWUocm9vdCk7CiAgICAgICAgICAgIHJldHVybiB0ZW1wOwogICAgICAgIH0KCiAgICAgICAgLy9Ud28gQ2hpbGRyZW4KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBzdHJ1Y3Qgbm9kZSAqdGVtcCA9IGZpbmRfbWluaW11bShyb290LT5yaWdodF9jaGlsZCk7CiAgICAgICAgICAgIHJvb3QtPmRhdGEgPSB0ZW1wLT5kYXRhOwogICAgICAgICAgICByb290LT5yaWdodF9jaGlsZCA9IGRlbGV0ZShyb290LT5yaWdodF9jaGlsZCwgdGVtcC0+ZGF0YSk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIHJvb3Q7Cn0KCnZvaWQgaW5vcmRlcihzdHJ1Y3Qgbm9kZSAqcm9vdCkKewogICAgaWYocm9vdCE9TlVMTCkgLy8gY2hlY2tpbmcgaWYgdGhlIHJvb3QgaXMgbm90IG51bGwKICAgIHsKICAgICAgICBpbm9yZGVyKHJvb3QtPmxlZnRfY2hpbGQpOyAvLyB2aXNpdGluZyBsZWZ0IGNoaWxkCiAgICAgICAgcHJpbnRmKCIgJWQgIiwgcm9vdC0+ZGF0YSk7IC8vIHByaW50aW5nIGRhdGEgYXQgcm9vdAogICAgICAgIGlub3JkZXIocm9vdC0+cmlnaHRfY2hpbGQpOy8vIHZpc2l0aW5nIHJpZ2h0IGNoaWxkCiAgICB9Cn0KCmludCBtYWluKCkKewogICAgLyoKICAgICAgICAgICAgICAgICAgIDIwCiAgICAgICAgICAgICAgICAgLyAgICBcCiAgICAgICAgICAgICAgICAvICAgICAgXAogICAgICAgICAgICAgICA1ICAgICAgIDMwCiAgICAgICAgICAgICAvICAgXCAgICAgL1wKICAgICAgICAgICAgLyAgICAgXCAgIC8gIFwKICAgICAgICAgICAxICAgICAgMTUgMjUgIDQwCiAgICAgICAgICAgICAgICAvICAgICAgICAgIFwKICAgICAgICAgICAgICAgLyAgICAgICAgICAgIFwKICAgICAgICAgICAgICA5ICAgICAgICAgICAgIDQ1CiAgICAgICAgICAgIC8gICBcICAgICAgICAgIC8KICAgICAgICAgICAvICAgICBcICAgICAgICAvCiAgICAgICAgICA3ICAgICAgMTIgICAgICA0MgogICAgKi8KICAgIHN0cnVjdCBub2RlICpyb290OwogICAgcm9vdCA9IG5ld19ub2RlKDIwKTsKICAgIGluc2VydChyb290LDUpOwogICAgaW5zZXJ0KHJvb3QsMSk7CiAgICBpbnNlcnQocm9vdCwxNSk7CiAgICBpbnNlcnQocm9vdCw5KTsKICAgIGluc2VydChyb290LDcpOwogICAgaW5zZXJ0KHJvb3QsMTIpOwogICAgaW5zZXJ0KHJvb3QsMzApOwogICAgaW5zZXJ0KHJvb3QsMjUpOwogICAgaW5zZXJ0KHJvb3QsNDApOwogICAgaW5zZXJ0KHJvb3QsIDQ1KTsKICAgIGluc2VydChyb290LCA0Mik7CgogICAgaW5vcmRlcihyb290KTsKICAgIHByaW50ZigiXG4iKTsKCiAgICByb290ID0gZGVsZXRlKHJvb3QsIDEpOwogICAgLyoKICAgICAgICAgICAgICAgICAgIDIwCiAgICAgICAgICAgICAgICAgLyAgICBcCiAgICAgICAgICAgICAgICAvICAgICAgXAogICAgICAgICAgICAgICA1ICAgICAgIDMwCiAgICAgICAgICAgICAgICAgXCAgICAgL1wKICAgICAgICAgICAgICAgICAgXCAgIC8gIFwKICAgICAgICAgICAgICAgICAgMTUgMjUgICA0MAogICAgICAgICAgICAgICAgLyAgICAgICAgICAgXAogICAgICAgICAgICAgICAvICAgICAgICAgICAgIFwKICAgICAgICAgICAgICA5ICAgICAgICAgICAgICA0NQogICAgICAgICAgICAvICAgXCAgICAgICAgICAgLwogICAgICAgICAgIC8gICAgIFwgICAgICAgICAvCiAgICAgICAgICA3ICAgICAgMTIgICAgICAgNDIKICAgICovCgogICAgcm9vdCA9IGRlbGV0ZShyb290LCA0MCk7CiAgICAvKgogICAgICAgICAgICAgICAgICAgMjAKICAgICAgICAgICAgICAgICAvICAgIFwKICAgICAgICAgICAgICAgIC8gICAgICBcCiAgICAgICAgICAgICAgIDUgICAgICAgMzAKICAgICAgICAgICAgICAgICBcICAgICAvXAogICAgICAgICAgICAgICAgICBcICAgLyAgXAogICAgICAgICAgICAgICAgICAxNSAyNSAgNDUKICAgICAgICAgICAgICAgICAvICAgICAgIC8gCiAgICAgICAgICAgICAgICAvICAgICAgIC8gICAKICAgICAgICAgICAgICAgOSAgICAgICA0MiAgICAKICAgICAgICAgICAgIC8gICBcICAgICAgICAgIAogICAgICAgICAgICAvICAgICBcICAgICAgICAKICAgICAgICAgICA3ICAgICAgMTIgICAgICAKICAgICovCgogICAgcm9vdCA9IGRlbGV0ZShyb290LCA0NSk7CiAgICAvKgogICAgICAgICAgICAgICAgICAgMjAKICAgICAgICAgICAgICAgICAvICAgIFwKICAgICAgICAgICAgICAgIC8gICAgICBcCiAgICAgICAgICAgICAgIDUgICAgICAgMzAKICAgICAgICAgICAgICAgICBcICAgICAvXAogICAgICAgICAgICAgICAgICBcICAgLyAgXAogICAgICAgICAgICAgICAgICAxNSAyNSAgNDIKICAgICAgICAgICAgICAgICAvICAgICAgICAgIAogICAgICAgICAgICAgICAgLyAgICAgICAgICAgIAogICAgICAgICAgICAgICA5ICAgICAgICAgICAgCiAgICAgICAgICAgICAvICAgXCAgICAgICAgICAKICAgICAgICAgICAgLyAgICAgXCAgICAgICAgCiAgICAgICAgICAgNyAgICAgIDEyICAgICAgCiAgICAqLwogICAgcm9vdCA9IGRlbGV0ZShyb290LCA5KTsKICAgIGlub3JkZXIocm9vdCk7CiAgICAvKgogICAgICAgICAgICAgICAgICAgMjAKICAgICAgICAgICAgICAgICAvICAgIFwKICAgICAgICAgICAgICAgIC8gICAgICBcCiAgICAgICAgICAgICAgIDUgICAgICAgMzAKICAgICAgICAgICAgICAgICBcICAgICAvXAogICAgICAgICAgICAgICAgICBcICAgLyAgXAogICAgICAgICAgICAgICAgICAxNSAyNSAgNDIKICAgICAgICAgICAgICAgICAvICAgICAgICAgIAogICAgICAgICAgICAgICAgLyAgICAgICAgICAgIAogICAgICAgICAgICAgICAxMiAgICAgICAgICAgIAogICAgICAgICAgICAgLyAgICAgICAgICAgICAKICAgICAgICAgICAgLyAgICAgICAgICAgICAKICAgICAgICAgICA3ICAgICAgICAgICAgCiAgICAqLwogICAgcHJpbnRmKCJcbiIpOwoKICAgIHJldHVybiAwOwp9