#include <iostream>
#include <stack>
#include <ctime>

using namespace std;

class Node{
public:
    Node(int);
    int key;
    Node* leftChild;
    Node* rightChild;
    char charArray[10];
};

Node::Node(int k){
    this->key = k;
    this->rightChild = nullptr;
    this->leftChild = nullptr;
    string keyString = to_string(k);
    int keyLength = keyString.length();
    for (int i=0;i<keyLength;i++){
        this->charArray[i] = keyString[i];
    }
}

class BinarySearchTree{
    int countScanPreorder(Node*);
    int countScanInorder(Node*);
    int countScanPostorder(Node*);

public:
    Node* root;
    BinarySearchTree();
    bool InsertNode(int);
    void InsertNodesBulk(int);
    Node* FindNode(int);
    bool RemoveNode(int);
    void scanPreorder(Node*);
    void scanInorder(Node*);
    void scanPostorder(Node*);
};

int BinarySearchTree::countScanPreorder(Node* current) {
    int counter = 1;
    if(current== nullptr){
        return 0;
    }
    if(current!= nullptr){
        cout << current->key << " ";
        counter += countScanPreorder(current->leftChild);
        counter += countScanPreorder(current->rightChild);

    }
    return counter;
}

void BinarySearchTree::scanPreorder(Node* current){
    int c = countScanPreorder(current);
    cout << c;
}

int BinarySearchTree::countScanInorder(Node* current) {
    int counter = 1;
    if(current== nullptr){
        return 0;
    }
    if(current!= nullptr){
        cout << current->key << " ";
        counter += countScanInorder(current->leftChild);
        counter += countScanInorder(current->rightChild);

    }
    return counter;
}


void BinarySearchTree::scanInorder(Node* current){
    int c = countScanInorder(current);
    cout << c;
};

int BinarySearchTree::countScanPostorder(Node* current) {
    int counter = 1;
    if(current== nullptr){
        return 0;
    }
    if(current!= nullptr){
        cout << current->key << " ";
        counter += countScanPostorder(current->leftChild);
        counter += countScanPostorder(current->rightChild);
    }
    return counter;
}
void BinarySearchTree::scanPostorder(Node* current){
    int c = countScanPostorder(current);
    cout << c;
}

bool BinarySearchTree::RemoveNode(int k){
    Node* current = this->root;
    if(current == nullptr){
        return false;
    }
    stack<Node*> nodesStack;

    nodesStack.push(current);
    while((current!=nullptr && current->key!=k)){
        if(current->key < k){
                current = current->rightChild;
                }
            else{
                current = current->leftChild;
        }
        nodesStack.push(current);
    }

    if(current == nullptr){
        return false;
    }
    current = nodesStack.top();

    //wezel jest lisciem
    if(current->leftChild == nullptr && current->rightChild == nullptr){
        nodesStack.pop();
        Node* parent = nodesStack.top();
        if(parent->leftChild == current){
            parent->leftChild = nullptr;
        }else{
            parent->rightChild = nullptr;
        }
        delete current;
    }
    //wezel ma dwoch potomkow
    else if(current->leftChild != nullptr && current->rightChild != nullptr){
        Node* nodeToRemove = current;
        current = current->rightChild;
        nodesStack.push(current);
        while(current->leftChild != nullptr){
            current = current->leftChild;
            nodesStack.push(current);
        }
        Node* successor = nodesStack.top();
        nodesStack.pop();
        if(successor->rightChild != nullptr){
            nodesStack.top()->leftChild = successor->rightChild;
        }else{
            nodesStack.top()->leftChild == nullptr;
        }
        successor->leftChild = nodeToRemove->leftChild;
        successor->rightChild = nodeToRemove->rightChild;
        if(nodeToRemove == root){
            root = successor;
        }
        else{
            while(nodesStack.top() != nodeToRemove && !nodesStack.empty()){
                nodesStack.pop();
            }
            nodesStack.pop();
            if(nodesStack.top()->leftChild == nodeToRemove){
                nodesStack.top()->leftChild = successor;
            }else{
                nodesStack.top()->rightChild = successor;
            }
        }
        delete nodeToRemove;
    }
    //wezel ma lewego potomka
    else if(current->leftChild != nullptr && current->rightChild == nullptr){
        nodesStack.pop();
        if(nodesStack.top()->leftChild == current) {
            nodesStack.top()->leftChild = current->leftChild;
        }else{
            nodesStack.top()->rightChild=current->leftChild;
        }

    }
    else if(current->rightChild!=nullptr && current->leftChild == nullptr){
        nodesStack.pop();
        if(nodesStack.top()->leftChild == current){
            nodesStack.top()->leftChild = current->rightChild;
        }else{
            nodesStack.top()->rightChild = current->rightChild;
        }
    }
    return true;
}
//zwraca wskaznik na wezel o podanym kluczu. Zwraca wskaznik na nullptr jesli nie znaleziono klucza.
Node* BinarySearchTree::FindNode(int k){
    Node* current = this->root;
    while((current!=nullptr && current->key!=k))
        if(current->key < k)
                current = current->rightChild;
            else
                current = current->leftChild;

    return current;
}

BinarySearchTree::BinarySearchTree(){
    this->root = nullptr;
}
//zwraca true jesli udalo sie wprowadzic wezel do BST
bool BinarySearchTree::InsertNode(int k){

    if (this->root == nullptr){
        this->root = new Node(k);
    }
    Node* current = this->root;
    Node* parent = nullptr;
    while(current!=nullptr){
        if(current->key == k)
            return false;

        parent = current;
        if(current->key < k){
            current = current->rightChild;
        }
        else{
            current = current->leftChild;}
    }

    if(parent->key >k){
            parent->leftChild = new Node(k);
    }else{
    parent->rightChild = new Node(k);
        }
        return true;
    }


void BinarySearchTree::InsertNodesBulk(int n){
    int currentInserted = 0;
    while(currentInserted <n){
        if(InsertNode(((rand()%20001)-10000))==true){
            currentInserted++;
        }
    }
}

int main()
{
    clock_t begin, end;
    double time_spent;
    FILE* fp = fopen("inlab03.txt", "r");
    int N;
    int k1;
    int k2;
    int k3;
    int k4;
    if (fp == NULL)
        return -1;
    fscanf (fp, "%d %d %d %d %d", &N ,&k1, &k2, &k3, &k4);
    fclose(fp);
    begin = clock();

    BinarySearchTree* bst = new BinarySearchTree();
    bst->RemoveNode(k1);
    bst->InsertNode(k1);
    bst->InsertNodesBulk(N);
    bst->scanInorder(bst->root);
    bst->scanPostorder(bst->root);
    bst->InsertNode(k2);
    bst->scanInorder(bst->root);
    bst->InsertNode(k3);
    bst->InsertNode(k4);
    bst->RemoveNode(k1);
    bst->scanPreorder(bst->root);
    bst->FindNode(k1);
    bst->RemoveNode(k2);
    bst->scanInorder(bst->root);
    bst->RemoveNode(k3);
    bst->RemoveNode(k4);

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    cout << endl << to_string(time_spent);
    return 0;
}