#include <iostream>
#include <cstdlib>

using namespace std;

class BST{
private:
    struct node{
        int index;

        node *left;
        node *right;

    };
    node *root;
    void AddLeafPrivate(int index, node *curr);
    void printInOrderPrivate(node *curr);
    node *returnNodePrivate(int index, node*curr);
    int getLowestPrivate(node *curr);
    void deleteNodePrivate(int index,node *parent);
    void deleteRoot();
    void deleteMatch(node *parent, node *match, bool left);

public:

    BST();
    node *createLeaf(int index);
    void AddLeaf(int index);
    void printInOrder();
    node *returnNode(int index);
    void printChild(int index);
    int getRoot();
    int getLowest();
    void deleteNode(int index);
    //void deleteRoot();
};

BST::BST(){
    root = NULL;
}
//TWORZENIE
BST::node *BST::createLeaf(int index){
    node *temp = new node;
    temp->index = index;

    temp->left = NULL;
    temp->right = NULL;

    return temp;
}
//DODAWANIE
void BST::AddLeaf(int index){
    AddLeafPrivate(index, root);
}
void BST::AddLeafPrivate(int index, node *curr){
    //Puste drzewo
    if(root == NULL){
        root = createLeaf(index);
    }
    //< root
    else if(index < curr->index){
        if(curr->left != NULL){
            AddLeafPrivate(index, curr->left);
        }
        else{
            curr->left = createLeaf(index);
        }
    }
    //> root
    else if(index > curr->index){
        if(curr->right != NULL){
            AddLeafPrivate(index, curr->right);
        }
        else{
            curr->right = createLeaf(index);
        }
    }
    else{
        cout << "Klucz o wartosci: " << index << " juz istnieje" << endl;
    }
}

void BST::printInOrder(){
    printInOrderPrivate(root);
}
void BST::printInOrderPrivate(node *curr){
    if(root != NULL){
        if(curr->left !=NULL){
            printInOrderPrivate(curr->left);

        }
        cout << curr->index << " ";
        if(curr->right != NULL){
            printInOrderPrivate(curr->right);
        }
    }
    else{
        cout << "Drzewo jest puste" << endl;
    }
}

BST::node* BST::returnNode(int index){
    return returnNodePrivate(index, root);
}

BST::node* BST::returnNodePrivate(int index, node *curr){
    if(curr != NULL){
        if(curr->index == index){
            return curr;
        }
        else{
            if(index < curr->index){
                return returnNodePrivate(index, curr->left);
            }
            else{
                return returnNodePrivate(index, curr->right);
            }
        }
    }
    else{
        return NULL;
    }
}
int BST::getRoot(){
    if(root != NULL){
        return root->index;
    }
    else{
        return -2000000;
    }
}
void BST::printChild(int index){
    node *curr = returnNode(index);

    if(curr != NULL){
        cout <<"Wartosc wezla rodzica = " <<curr->index << endl;

        if(curr->left == NULL){
            cout << "Lewy potomek nie istnieje" << endl;
        }
        else{
            cout << "Lewy potomek ma wartosc klucza = " << curr->left->index << endl;
        }

        if(curr->right == NULL){
            cout << "Prawy potomek nie istnieje" << endl;
        }
        else{
            cout << "Prawy potomek ma wartosc klucza = " << curr->right->index << endl;
        }

    }
    else{
        cout << "Wezel z kluczem " << index << " nie istnieje" << endl;
    }
}

int BST::getLowest(){
    return getLowestPrivate(root);
}
int BST::getLowestPrivate(node *curr){
    if(root == NULL){
        cout << "Drzewo jest puste" << endl;
        return -2000000;
    }
    else{
        if(curr->left != NULL){
            return getLowestPrivate(curr->left);
        }
        else{
            return curr->index;
        }
    }
}

void BST::deleteNode(int index){
    deleteNodePrivate(index, root);
}

void BST::deleteNodePrivate(int index, node *parent){
    if(root != NULL){
        if(root->index == index){
            deleteRoot();
        }
        else{
            if(index < parent->index && parent->left != NULL){
                if(parent->left->index == index){
                    deleteMatch(parent, parent->left, true);
                }
                else{
                    deleteNodePrivate(index, parent->left);
                }
            }
            else if(index > parent->index && parent->right != NULL){
                if(parent->right->index == index){
                    deleteMatch(parent, parent->left, true);
                }
                else{
                    deleteNodePrivate(index, parent->right);
                }
            }
            else{
                cout << "Szukany wezel nie istnieje" << endl;
            }
        }
    }
    else{
        cout << "Drzewo jest puste" << endl;
    }
}

void BST::deleteRoot(){
    if(root != NULL){
        node *curr = root;
        int rootIndex = root->index;
        int lowestSub;

        //0 potomkow
        if(root->left == NULL && root->right == NULL){
            root = NULL;
            delete curr;
        }
        //1 potomek
        else if(root -> left == NULL && root->right != NULL){
            root = root->right;
            curr->right = NULL;

            delete curr;
            cout << "Korzen z kluczem: " << rootIndex << " zostal usuniety" << endl;
            cout << "Nowym korzeniem jest wezel z wartoscia: " << root->index <<endl;

        }
        else if(root -> left != NULL && root->right == NULL){
            root = root->left;
            curr->left = NULL;

            delete curr;
            cout << "Korzen z kluczem: " << rootIndex << " zostal usuniety" << endl;
            cout << "Nowym korzeniem jest wezel z wartoscia: " << root->index <<endl;

        }
        //2 potomkow - bierzemy najmniejszy wezel z prawego poddrzewa
        else{
            lowestSub = getLowestPrivate(root->right);
            deleteNodePrivate(lowestSub, root);
            root->index = lowestSub;

            cout << "Korzen z kluczem" << rootIndex << " zostal usuniety" << endl;
            cout << "Zostal zastapiony wezlem z kluczem: " << root->index << endl;
        }

    }
    else{
        cout << "Root nie istnieje" << endl;
    }
}

void BST::deleteMatch(node *parent, node *match, bool left){
    if(root != NULL){
        node *curr;
        //int matchIndex = match->index;
        int lowestSub;

        //0 potomkow
        if(match->left == NULL && match->right == NULL){
            curr = match;
            left == true ? parent->left = NULL : parent->right = NULL;
            delete curr;
            cout << "usunieto" << endl;
        }
        //1 potomek
        else if(match->left == NULL && match->right != NULL){
                if(left == true){
                    parent->left = match->right;
                    match->right = NULL;
                    curr = match;
                    delete curr;
                    cout << "usunieto" << endl;
                }
                else{
                    parent->right = match->right;
                    match->right = NULL;
                    curr = match;
                    delete curr;
                    cout << "usunieto" << endl;
                }
            }
        else if(match->left != NULL && match->right == NULL){
                if(left == true){
                    parent->left = match->left;
                    match->left = NULL;
                    curr = match;
                    delete curr;
                    cout << "usunieto" << endl;
                }
                else{
                    parent->right = match->left;
                    match->left = NULL;
                    curr = match;
                    delete curr;
                    cout << "usunieto" << endl;
                }
            }
        //2 potomkow
        else{
            lowestSub = getLowestPrivate(match->right);
            deleteNodePrivate(lowestSub, match);
            match->index = lowestSub;
        }
    }
    else{
        cout << "Drzewo jest juz puste" << endl;
    }
}
int main()
{
    int TreeKeys[13] = {3,6,34,123,5,33,11,2,78,7,9,10,99};
    BST bstTree;
    int input = 0;

    cout << "Wyswietlanie inOrder puste: " << endl;
    bstTree.printInOrder();

    for(int i = 0; i < 13; i++){
        bstTree.AddLeaf(TreeKeys[i]);
    }
    cout << "Wyswietlanie inOrder z liczbami: " << endl;
    bstTree.printInOrder();

    cout << endl;

    bstTree.printChild(bstTree.getRoot());
    cout << "Najmniejsza wartosc w drzewie to = " << bstTree.getLowest() << endl << endl;

    while(input != -1){
        cout << "Usun wybrana wartosc: ";
        cin >> input;
        {
            if(input != -1){
                cout << endl;
                bstTree.deleteNode(input);
                bstTree.printInOrder();
                cout << endl;
            }
        }
    }

    return 0;
}