#include "iostream"
using namespace std;
struct Node{
    int value;

    Node* left;
    Node* right;

    Node(int num):value(num), left(NULL), right(NULL) {}
};

Node* Add(int num, Node* root){
    if(root == NULL){
        root = new Node(num);
    }
    if(num < root->value){
        root->left = Add(num, root->left);
    }
    if(num > root->value) {
        root->right = Add(num, root->right);
    }
    return root;
}

Node* search(int num, Node* root){
    if(num == root->value){
        return root;
    }
    if(num < root->value){
        return search(num, root->left);
    }
    if(num > root->value) {
        return search(num, root->right);
    }
    return NULL;
}

Node* del(int num, Node* root){
    if(num == root->value){
        if(root->left == NULL && root->right == NULL){
            delete(root);
            return NULL;
        }
        if(root->left == NULL){
            Node* tmp = root->right;
            delete(root);
            root = tmp;
            return root;
        }
        if(root->right == NULL){
            Node* tmp = root->left;
            delete(root);
            root = tmp;
            return root;
        }
        Node* tmp  = root->right;
        while(tmp->left != NULL){
            tmp = tmp->left;
        }
        tmp->left = root->left;
        tmp = root->right;
        delete(root);
        root = tmp;
        return root;
    }
    if(num < root->value){
        root->left = del(num, root->left);
    }
    if(num > root->value) {
        root->right= del(num, root->right);
    }
}

int main(){
    Node* root = NULL;
    root = Add(10,root);
    root = Add(5,root);
    root = Add(2,root);
    root = Add(20,root);
    root = Add(30,root);
    root = Add(15,root);
    Node* tmp = search(15, root);
    root = del(10,root);

    return 0;
}