#include <iostream>
#include <string>
#include <cassert>
#include <cstdlib>
#include <ctime>

using namespace std;

struct BST_Node {
    string key;
    // we'll ignore "stuff"
    string stuff;
    BST_Node* left;
    BST_Node* right;
};

typedef BST_Node* BST;

void BST_init (BST& root) {
    root = NULL;
}

bool BST_isEmpty(BST root) {
    return NULL == root;
}

bool BST_has(string key, BST curNode) {
    if (BST_isEmpty(curNode)) { // i.e., NULL == ROOT
        return false;
    } else if (key == curNode->key) {
        return true;
    } else if (key < curNode->key) {
        return BST_has (key,curNode->left);
    } else {
        return BST_has (key,curNode->right);
    }
}

BST BST_insert (string key, BST &curNode) {
    if (NULL == curNode) {
        curNode = new BST_Node;
        curNode->key = key;
        curNode->left = NULL;
        curNode->right = NULL;
    } else if (key == curNode->key) {
        cerr << "duplicate key: " << key << endl;
        assert(false);
    } else if (key < curNode->key) {
        curNode->left = BST_insert (key,curNode->left);
    } else {
        curNode->right = BST_insert(key,curNode->right);
    }
    return curNode;
}

void BST_print(BST curNode) {
    if (curNode != NULL) {
        BST_print (curNode->left);
        cout << curNode->key << endl;
        BST_print (curNode->right);
    }
}

string BST_lookup (const BST& root, string key) {
    if (BST_isEmpty(root)) {
        return ""; // or "ERROR", or ... umm ...
    } else if (key == root->key) {
        return root->stuff;
    } else if (key < root->key) {
        return BST_lookup (root->left, key);
    } else {
        return BST_lookup (root->right, key);
    }
}

void BST_delete(string key, BST& tree) {
    assert (!BST_isEmpty(tree));
    BST_Node *previousNode = tree;
    BST_Node *deleteNode = tree;

    while(deleteNode != NULL && key != deleteNode->key){
        if (key < deleteNode->key) {
            previousNode = deleteNode;
            deleteNode = deleteNode->left;
        } else {
            previousNode = deleteNode;
            deleteNode = deleteNode->right;
        }
    }
    if (NULL == deleteNode) {
        return;
    }
    if(deleteNode->left == NULL && deleteNode->right == NULL){
        //      cout << "Test: " << previousNode->left->key << deleteNode->key;
        if(tree->key == deleteNode->key){
            tree = NULL;
        }else if(previousNode->left != NULL && previousNode->left->key == deleteNode->key){
            previousNode->left=NULL;
        }else{
            previousNode->right=NULL;
        }
        delete deleteNode;
    }else if(deleteNode->left == NULL && deleteNode->right != NULL){
        if(tree->key == deleteNode->key){
            tree = deleteNode->right;
        }else if(previousNode->left != NULL && previousNode->left->key == deleteNode->key){
            previousNode->left = deleteNode->right;
        }else if(previousNode->right != NULL && previousNode->right->key == deleteNode->key){
            previousNode->right = deleteNode->right;
        }
        delete deleteNode;
    }else if(deleteNode->right == NULL && deleteNode->left != NULL){
        if(tree->key == deleteNode->key){
            tree = deleteNode->left;
        }else if(previousNode->right != NULL && previousNode->right->key == deleteNode->key){
            previousNode->right = deleteNode->left;
        }else if(previousNode->left != NULL && previousNode->left->key == deleteNode->key){
            previousNode->left = deleteNode->left;
        }
        delete deleteNode;
    }else{
        BST_Node *switchNode = deleteNode->left;
        BST_Node *previousSwitchNode = deleteNode;
        while(switchNode->right != NULL){
            previousSwitchNode = switchNode;
            switchNode = switchNode->right;
        }

        if(deleteNode->key == previousSwitchNode->key){
            //previousSwitchNode->left = switchNode->left;
            switchNode->right = deleteNode->right;
            if(tree->key == deleteNode->key){
                tree = switchNode;
                delete deleteNode;
            }else{
                if(previousNode->left == NULL || previousNode->left->key == deleteNode->key){
                    previousNode->left = switchNode;
                }else if(previousNode->right == NULL || previousNode->right->key == deleteNode->key){
                    previousNode->right = switchNode;
                }
                delete deleteNode;
            }
        }else{
            previousSwitchNode->right = switchNode->left;
            switchNode->left = deleteNode->left;
            switchNode->right = deleteNode->right;
            if(tree->key == deleteNode->key){
                tree = switchNode;
                delete deleteNode;
            }else{
                if(previousNode->left == NULL || previousNode->left->key == deleteNode->key){
                    previousNode->left = switchNode;
                }else if(previousNode->right == NULL || previousNode->right->key == deleteNode->key){
                    previousNode->right = switchNode;
                }
                delete deleteNode;
            }
        }
    }
}