#include <iostream>

struct tnode {
    int value;
    tnode* left;
    tnode* right;
    tnode() {
        left == NULL;
        right == NULL;
    }
};

tnode* search_bst(tnode* rootTree, int searcher) {
    if (rootTree == NULL) {
        return NULL;
    } else if (rootTree->value > searcher) {
        search_bst(rootTree->left, searcher);
    } else if (rootTree->value < searcher) {
        search_bst(rootTree->right, searcher);
    } else if (rootTree->value == searcher) {
        return rootTree;
    }
}

void insertNode(tnode*& rootTree, tnode* newNode) {
    if (rootTree == NULL) {
        rootTree = newNode;
    } else if (rootTree->value > newNode->value) {
        insertNode(rootTree->left, newNode);
    } else {
        insertNode(rootTree->right, newNode);
    }
}

void deleteNode(tnode*& rootTree, int key) {
    // поиск удаленный узел
    tnode* delNode = rootTree;
    while (delNode->value != key) {
        if (delNode->value < key) {
            delNode = delNode->left;
        } else if (delNode->value > key) {
            delNode = delNode->right;
        }
    }

    std::cout<<delNode->value;
    
    // В случае, у удаленного узла иммет только одна потомка
    if (delNode->left == NULL) {
        delNode = delNode->right;
    } else if (delNode->right == NULL) {
        delNode = delNode->left;
    } else {
       
        tnode* leftOfDelNode = delNode->left;

        // поиск the most right node of left tree, which root now is deleted node
        while(leftOfDelNode->right != NULL) {
            leftOfDelNode = leftOfDelNode->right;
        }

        delNode->value = leftOfDelNode->value;
        deleteNode(rootTree, leftOfDelNode->value);        
    }
}

void visitTree(tnode* rootTree) {
    if(rootTree == NULL) {
        std::cout<<"NIL"<<std::endl;
    } else {
        std::cout<<rootTree->value<<" ";
        visitTree(rootTree->left);
        visitTree(rootTree->right);
    }
}

int main() {
    tnode* rootTree;
    tnode* right;
    tnode* left;
    right = new tnode;
    right->value = 12;
    left = new tnode;
    left->value = 8;
    rootTree = new tnode;
    rootTree->value = 10;
    insertNode(rootTree, right);
    insertNode(rootTree, left);
    tnode* temp = search_bst(rootTree, 8);
    std::cout<<temp->value;
    deleteNode(rootTree, 8);
    visitTree(rootTree);

    delete right;
    delete left;
    delete rootTree;
    
    return 0;
}