#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* left,*right;
};
struct Node* newNode(int data){
Node *root = (struct Node*)malloc(sizeof(struct Node*));
root->data=data;
root->left=NULL;
root->right=NULL;
return root;
}
struct Node* insert(Node *root,int data){
if(root==NULL){
return newNode(data);
}
if(root->data<data){
root->right = insert(root->right,data);
}
else if (root->data>data){
root->left = insert(root->left,data);
}
return root;
}
void inorder(Node *root){
if(root==NULL)
return ;
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
Node* search(Node* root, int data){
if(root==NULL)
return NULL;
if(root->data<data){
return search(root->right,data);
}else if(root->data>data){
return search(root->left,data);
}else{
return root;
}
}
Node* delNode(Node* root,int data){
if(root==NULL)
return NULL;
if(root->data>data){
root->left = delNode(root->left,data);
}else if(root->data<data){
root->right = delNode(root->right,data);
}else{
if(root->left==NULL){
Node* temp = root->right;
free(root);
return temp;
}
else if(root->right==NULL){
Node* temp = root->left;
free(root);
return temp;
}else{
Node* temp= root->right;
while(temp->left!=NULL){
temp=temp->left;
}
root->data = temp->data;
root->right = delNode(root->right,temp->data);
}
}
return root;
}
int main(){
Node *root=NULL;
root = insert(root,10);
root = insert(root,5);
root = insert(root,6);
root = insert(root,20);
root = insert(root,19);
cout<<search(root,19)->data;
root = delNode(root,19);
inorder(root);
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgTm9kZSB7CglpbnQgZGF0YTsKCU5vZGUqIGxlZnQsKnJpZ2h0Owp9OwoKc3RydWN0IE5vZGUqIG5ld05vZGUoaW50IGRhdGEpewoJTm9kZSAqcm9vdCA9IChzdHJ1Y3QgTm9kZSopbWFsbG9jKHNpemVvZihzdHJ1Y3QgTm9kZSopKTsKCXJvb3QtPmRhdGE9ZGF0YTsKCXJvb3QtPmxlZnQ9TlVMTDsKCXJvb3QtPnJpZ2h0PU5VTEw7CglyZXR1cm4gcm9vdDsKfQoKc3RydWN0IE5vZGUqIGluc2VydChOb2RlICpyb290LGludCBkYXRhKXsKCWlmKHJvb3Q9PU5VTEwpewoJCXJldHVybiBuZXdOb2RlKGRhdGEpOwoJfQoJaWYocm9vdC0+ZGF0YTxkYXRhKXsKCQlyb290LT5yaWdodCA9IGluc2VydChyb290LT5yaWdodCxkYXRhKTsKCX0KCWVsc2UgaWYgKHJvb3QtPmRhdGE+ZGF0YSl7CgkJcm9vdC0+bGVmdCA9IGluc2VydChyb290LT5sZWZ0LGRhdGEpOwoJfQoJcmV0dXJuIHJvb3Q7Cn0KCnZvaWQgaW5vcmRlcihOb2RlICpyb290KXsKCWlmKHJvb3Q9PU5VTEwpCgkJcmV0dXJuIDsKCWlub3JkZXIocm9vdC0+bGVmdCk7Cgljb3V0PDxyb290LT5kYXRhPDwiICI7Cglpbm9yZGVyKHJvb3QtPnJpZ2h0KTsKfQpOb2RlKiBzZWFyY2goTm9kZSogcm9vdCwgaW50IGRhdGEpewoJaWYocm9vdD09TlVMTCkKCQlyZXR1cm4gTlVMTDsKCWlmKHJvb3QtPmRhdGE8ZGF0YSl7CgkJcmV0dXJuIHNlYXJjaChyb290LT5yaWdodCxkYXRhKTsKCX1lbHNlIGlmKHJvb3QtPmRhdGE+ZGF0YSl7CgkJcmV0dXJuIHNlYXJjaChyb290LT5sZWZ0LGRhdGEpOwoJfWVsc2V7CgkJcmV0dXJuIHJvb3Q7Cgl9Cn0KTm9kZSogZGVsTm9kZShOb2RlKiByb290LGludCBkYXRhKXsKCWlmKHJvb3Q9PU5VTEwpCgkJcmV0dXJuIE5VTEw7CglpZihyb290LT5kYXRhPmRhdGEpewoJCXJvb3QtPmxlZnQgPSBkZWxOb2RlKHJvb3QtPmxlZnQsZGF0YSk7Cgl9ZWxzZSBpZihyb290LT5kYXRhPGRhdGEpewoJCXJvb3QtPnJpZ2h0ID0gZGVsTm9kZShyb290LT5yaWdodCxkYXRhKTsKCX1lbHNlewoJCWlmKHJvb3QtPmxlZnQ9PU5VTEwpewoJCQlOb2RlKiB0ZW1wID0gcm9vdC0+cmlnaHQ7CgkJCWZyZWUocm9vdCk7CgkJCXJldHVybiB0ZW1wOwoJCX0KCQllbHNlIGlmKHJvb3QtPnJpZ2h0PT1OVUxMKXsKCQkJTm9kZSogdGVtcCA9IHJvb3QtPmxlZnQ7CgkJCWZyZWUocm9vdCk7CgkJCXJldHVybiB0ZW1wOwoJCX1lbHNlewoJCQlOb2RlKiB0ZW1wPSByb290LT5yaWdodDsKCQkJd2hpbGUodGVtcC0+bGVmdCE9TlVMTCl7CgkJCQl0ZW1wPXRlbXAtPmxlZnQ7CgkJCX0KCQkJcm9vdC0+ZGF0YSA9IHRlbXAtPmRhdGE7CgkJCXJvb3QtPnJpZ2h0ID0gZGVsTm9kZShyb290LT5yaWdodCx0ZW1wLT5kYXRhKTsgCgkJfQoJfQoJcmV0dXJuIHJvb3Q7Cn0KaW50IG1haW4oKXsKCU5vZGUgKnJvb3Q9TlVMTDsKCQoJcm9vdCA9IGluc2VydChyb290LDEwKTsKCXJvb3QgPSBpbnNlcnQocm9vdCw1KTsKCXJvb3QgPSBpbnNlcnQocm9vdCw2KTsKCXJvb3QgPSBpbnNlcnQocm9vdCwyMCk7Cglyb290ID0gaW5zZXJ0KHJvb3QsMTkpOwoJY291dDw8c2VhcmNoKHJvb3QsMTkpLT5kYXRhOwoJcm9vdCA9IGRlbE5vZGUocm9vdCwxOSk7Cglpbm9yZGVyKHJvb3QpOwoJCn0=