#include <iostream>
#include <cstdlib>
#include <ctime>

#include <string>
#include <cstring>

using namespace std;

class Tree;

class TreeNode
{
    int x;
    char z[10];

    TreeNode* left;
    TreeNode* right;

public:
    TreeNode(int);

    void display();
    friend class Tree;
};

class Tree
{
    TreeNode* root;
    int size;

public:
    Tree();
    ~Tree();

    void addNode(int);
    void fillsGoodInCorporation(int);

    TreeNode* search(int);

    TreeNode* findSuccessor(TreeNode*);
    TreeNode* findParent(TreeNode*);

    void deleteNode(int);

    void preOrder(TreeNode*);
    void inOrder(TreeNode*);
    void postOrder(TreeNode*);

    void clear();
};

TreeNode::TreeNode(int x)
{
    this->x = x;
    strcpy(this->z, to_string(x).c_str());

    this->left = NULL;
    this->right = NULL;
}

void TreeNode::display()
{
    cout << x << " " << z << endl;
}

Tree::Tree()
{
    this->root = NULL;
    this->size = 0;
}

Tree::~Tree()
{
    clear();
}

void Tree::addNode(int x)
{
    if (root == NULL) {
        root = new TreeNode(x);
        size++;

        return;
    }

    TreeNode* newNode = new TreeNode(x);
    TreeNode* temp = root;

    while (temp) {
        if (temp->x == x) {
            delete newNode;
            return;
        }

        if (x < temp->x) {
            if (temp->left == NULL) {
                temp->left = newNode;
                break;
            }

            temp = temp->left;
        } else {
            if (temp->right == NULL) {
                temp->right = newNode;
                break;
            }

            temp = temp->right;
        }
    }

    size++;
}

void Tree::fillsGoodInCorporation(int X)
{
    for (int i = 0; i < X; i++) {
        addNode(-10000 + rand() % 20001);
    }
}

TreeNode* Tree::search(int x)
{
    if (size == 0) {
        cout << "Tree's empty!" << endl << endl;
        return NULL;
    }

    TreeNode* temp = root;
    while (temp) {
        if (temp->x == x) {
            return temp;
        }

        if (x < temp->x) {
            temp = temp->left;
        } else {
            temp = temp->right;
        }
    }

    cout << "Not found bitch!" << endl << endl;
    return NULL;
}

TreeNode* Tree::findParent(TreeNode* node)
{
    TreeNode* temp = root;
    while (temp) {
        if (temp->left == node || temp->right == node) {
            break;
        }

        if (node->x < temp->x) {
            temp = temp->left;
        } else {
            temp = temp->right;
        }
    }

    return temp;
}

TreeNode* Tree::findSuccessor(TreeNode* node)
{
    TreeNode* temp = node->right;

    if (temp == NULL) {
        return NULL;
    }

    while (temp->left) {
        temp = temp->left;
    }

    return temp;
}

void Tree::deleteNode(int x)
{
    if (size == 0) {
        cout << "Tree's empty!";
        return;
    }

    if (size == 1 && root->x == x) {
        delete root;

        root = NULL;
        size--;

        return;
    }

    TreeNode* parent = NULL;
    TreeNode* toDelete = root;

    while (toDelete) {
        if (toDelete->x == x) {
            break;
        }

        parent = toDelete;
        if (x < toDelete->x) {
            toDelete = toDelete->left;
        } else {
            toDelete = toDelete->right;
        }
    }

    if (toDelete == NULL) {
        cout << "Not found!" << endl << endl;
        return;
    }

    if (root->x == x) {

    }

    if (toDelete->left == NULL && toDelete->right == NULL) {
        if (parent->left == toDelete) {
            parent->left = NULL;
        } else {
            parent->right = NULL;
        }
    } else if (toDelete->left == NULL) {
        if (parent->left == toDelete) {
            parent->left = toDelete->right;
        } else {
            parent->right = toDelete->right);
        }
    } else if (toDelete->right == NULL) {
        if (parent->left == toDelete) {
            parent->left = toDelete->left;
        } else {
            parent->right = toDelete->left;
        }
    } else {
        TreeNode* successor = findSuccessor(toDelete);
        TreeNode* successorParent = findParent(successor);
        TreeNode* successorChild = successor->right;

        if (parent->left == toDelete) {
            parent->left = successor;
        } else {
            parent->right = successor;
        }

        successor->left = toDelete->left;
        successor->right = toDelete->right;

        successorParent->left = successorChild;
    }

    delete toDelete;
    size--;
}

void Tree::preOrder(TreeNode* node) {
    int counter = 0;
    if (node) {
        node->display();
        counter++;

        preOrder(node->left);
        preOrder(node->right);
    }

    cout << endl << "Total nodes: " << counter << endl << endl;
}

void Tree::inOrder(TreeNode* node) {
    int counter = 0;
    if (node) {
        inOrder(node->left);
        node->display();
        counter++;
        inOrder(node->right);
    }

    cout << endl << "Total nodes: " << counter << endl << endl;
}

void Tree::postOrder(TreeNode* node) {
    int counter = 0;
    if (node) {
        postOrder(node->left);
        postOrder(node->right);
        node->display();
        counter++;
    }

    cout << endl << "Total nodes: " << counter << endl << endl;
}

int main()
{
    srand((unsigned) time(NULL));
    cout << rand() << endl;
}