// Tema: Binarny vyhladavaci strom
// Autor: Pavol Marak

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <queue>
using namespace std;

// Binarny vyhladavaci strom je datova struktura
// umoznujuca rychle vyhladavanie uzlov.
//
// Vlastnost:
//  * pre lubovolny uzol U v strome plati:
//      a) uzly v lavom podstrome su mensie ako U
//      b) uzly v pravom podstrome su vacsie ako U
//  * vsetky uzly v strome su unikatne

// uzol binarneho vyhladavacieho stromu
struct Node {
    int value; // hodnota uzla
    Node *left; // smernik na laveho potomka
    Node *right; // smernik na praveho potomka
};

// strom
struct Tree {
    Node *root; // koren stromu
};

// rekurzivna funkcia na pridanie uzla do stromu
Node* addNodeRecursive(Node* root, const int value){
    if(root){
        if(value < root->value){
            root->left = addNodeRecursive(root->left,value);
        }
        else if(value > root->value){
            root->right = addNodeRecursive(root->right,value);
        }
        else{
            throw string{"uzol sa uz v strome nachadza"};
        }
        return root;
    }
    return new Node{value,nullptr,nullptr};
}

// funkcia na pridanie uzla do stromu
void addNode(Tree* tree, const int value){
    tree->root = addNodeRecursive(tree->root,value);
}

// funkcia, ktora vrati novy binarny vyhladavaci strom
// vytvoreny z hodnot inicializacneho zoznamu
Tree* createTree(const initializer_list<int>& i){
    Tree* tree{new Tree{nullptr}};
    // pridavanie do stromu
    cout << "Pridavanie uzlov do stromu:" << endl << endl;
    for(const int u: i){
        cout << "Uzol " << u << ": ";
        try {
            addNode(tree,u);
            cout << "bol pridany" << endl;
        } catch (const string& e) {
            cout << e << endl;
        }
    }
    return tree;
}

// funkcia na vyhladanie uzla v strome
// ak bol uzol najdeny, funkcia vrati jeho adresu
// ak uzol nebol najdeny, funkcia vrati 'nullptr'
Node* searchNode(Tree* tree, const int value){
    Node* tmp = tree->root;
    while(tmp){
        if(value < tmp->value){
            tmp = tmp->left; // vnorenie do laveho podstromu
        }
        else if(value > tmp->value){
            tmp = tmp->right; // vnorenie do praveho podstromu
        }
        else{
            // nasli sme hladany uzol
            return tmp;
        }
    }
    // nenasli sme hladany uzol
    return nullptr;
}

// funkcia na vyhladanie minimalneho uzla v
// binarnom vyhladavacom strome
Node* findMinNode(Node* node){
    Node* minNode{nullptr};
    while(node){
        minNode = node;
        node = node->left;
    }
    return minNode;
}

// Alternativa 1 - nerekurzivna verzia
// funkcia na vymazanie uzla s hodnotou 'value' zo stromu
// ak bol uzol vymazany, funkcia vrati 'true'
// ak nebol uzol vymazany, funkcia vrati 'false'
bool removeNode1(Tree* tree, int value){
    Node* child{nullptr}, *prev{nullptr};
    Node* tmp = tree->root;
    bool left_right{false}; // 0 - left, 1 - right
    while(tmp){
        // navigacna cast
        if(value < tmp->value){
            prev = tmp;
            left_right = 0;
            tmp = tmp->left;
        }
        else if(value > tmp->value){
            prev = tmp;
            left_right = 1;
            tmp = tmp->right;
        }
        // nasli sme uzol, ktory ideme vymazat
        else{
            // existuje len lavy potomok alebo ziadny potomok
            if(!tmp->right){
                child = tmp->left;
            }
            // existuje len pravy potomok alebo ziadny potomok
            else if(!tmp->left){
                child = tmp->right;
            }
            // existuju sucasne obidvaja potomkovia
            else{
                // musime najst najmensi uzol v pravom podstrome od uzla 'tmp'
                // tzv. inorder successor
                Node* tmp2 = findMinNode(tmp->right);
                // a skopirovat jeho hodnotu do 'tmp'
                tmp->value = tmp2->value;
                // potom vymazeme inorder successora v pravom podstrome
                prev = tmp;
                tmp = tmp->right;
                left_right = 1;
                value = tmp2->value;
                continue;
            }
            // vymazavacia cast
            delete tmp;
            // ak vymazavame koren stromu
            if(!prev){
                tree->root = child;
            }
            else{
                if(!left_right){
                    prev->left = child;
                }
                else{
                    prev->right = child;
                }
            }
            return true;
        }
    }
    // uzol s hodnotou 'value' sa v strome nenachadzal
    return false;
}

// rekurzivna funkcia na vymazanie uzla s hodnotou 'value' zo stromu
Node* removeNode2Recursive(Node* root, const int value){
    if(!root){
        return root;
    }
    if(value < root->value){
        root->left = removeNode2Recursive(root->left,value);
    }
    else if(value > root->value){
        root->right = removeNode2Recursive(root->right,value);
    }
    // nasli sme uzol, ktory sa vymaze
    else{
        // 'root' ma len laveho potomka
        if(!root->right){
            Node* tmp = root->left;
            delete root;
            return tmp;
        }
        // 'root' ma len praveho potomka
        else if(!root->left){
            Node* tmp = root->right;
            delete root;
            return tmp;
        }
        // 'root' ma obidvoch potomkov
        else{
            // najdeme najmensi uzol v pravom podstrome 'root'
            Node* smallestNode = findMinNode(root->right);
            // skopirujem jeho hodnotu do 'root'
            root->value = smallestNode->value;
            // vymazeme ho
            root->right = removeNode2Recursive(root->right,smallestNode->value);
        }
    }
    return root;
}

// Alternativa 2 - tato funkcia vyuziva rekurzivnu funkciu
// na vymazanie uzla
// funkcia na vymazanie uzla s hodnotou 'value' zo stromu
void removeNode2(Tree* tree, int value){
    tree->root = removeNode2Recursive(tree->root,value);
}

// rekurzivna funkcia na vymazanie vsetkych uzlov v strome
// pozn. treba prejst stromom v style postorder
void removeTreeRecursive(Node* root){
    if(root){
        removeTreeRecursive(root->left);
        removeTreeRecursive(root->right);
        delete root;
    }
}

// funkcia na vymazanie vsetkych uzlov v strome aj samotneho stromu
void removeTree(Tree** tree){
    removeTreeRecursive((*tree)->root);
    delete *tree;
    *tree = nullptr;
}

// rekurzivna funkcia na prechod stromom v style preorder
void preorderRecursive(Node* root){
    if(root){
        cout << root->value << " ";
        preorderRecursive(root->left);
        preorderRecursive(root->right);
    }
}

// funkcia na prechod stromom v style preorder
void preorder(Tree* tree){
    preorderRecursive(tree->root);
}

// rekurzivna funkcia na prechod stromom v style inorder
void inorderRecursive(Node* root){
    if(root){
        inorderRecursive(root->left);
        cout << root->value << " ";
        inorderRecursive(root->right);
    }
}

// funkcia na prechod stromom v style inorder
void inorder(Tree* tree){
    inorderRecursive(tree->root);
}

// rekurzivna funkcia na prechod stromom v style postorder
void postorderRecursive(Node* root){
    if(root){
        postorderRecursive(root->left);
        postorderRecursive(root->right);
        cout << root->value << " ";
    }
}

// funkcia na prechod stromom v style postorder
void postorder(Tree* tree){
    postorderRecursive(tree->root);
}

// funkcia na prechod stromom v style levelorder
void levelorder(Tree* tree){
    if(tree->root){
        Node* tmp = tree->root;
        queue<Node*> q;
        q.push(tmp);
        while(!q.empty()){
            cout << q.front()->value << " ";
            if(q.front()->left){
                q.push(q.front()->left);
            }
            if(q.front()->right){
                q.push(q.front()->right);
            }
            q.pop();
        }
    }
}

// rekurzivna funkcia na zistenie hlbky uzla s hodnotou 'value'
// poznamka: koren ma hlbku 0
int depthNodeRecursive(Node* root, const int value){
    if(root){
        if(value < root->value){
            return 1+depthNodeRecursive(root->left,value);
        }
        else if(value > root->value){
            return 1+depthNodeRecursive(root->right,value);
        }
        else{
            return 0;
        }
    }
    throw string{
        "Uzol s hodnotou " + to_string(value) + " sa v strome nenachadza"
    };
}

// funkcia na zistenie hlbky uzla s hodnotou 'value'
// poznamka: koren ma hlbku 0
int depthNode(Tree* tree, const int value){
    return depthNodeRecursive(tree->root,value);
}

// rekurzivna funkcia na zistenie hlbky stromu
int depthTreeRecursive(Node* root){
    if(root){
        int leftDepth = 1+depthTreeRecursive(root->left);
        int rightDepth = 1+depthTreeRecursive(root->right);
        if(leftDepth>rightDepth){
            return leftDepth;
        }
        return rightDepth;
    }
    return -1;
}

// funkcia na zistenie hlbky stromu
// poznamka: koren ma hlbku 0
int depthTree(Tree* tree){
    return depthTreeRecursive(tree->root);
}

// testovacia funkcia pre binarny vyhladavaci strom
void test_tree(){
    // vytvorenie binarneho vyhladavacieho stromu z dodanych hodnot
    Tree* tree = createTree({8,3,1,6,4,7,10,14,13,13});

    cout << endl;

    // vyhladavanie v strome
    cout << "Vyhladavanie uzlov v strome:" << endl << endl;
    Node* result_search{nullptr};
    for(const int i: {8,6,13,100}){
        result_search = searchNode(tree,i);
        cout << "Uzol " << i << " " << (result_search?"":"ne") << "bol najdeny" << endl;
    }
    cout << endl;

    // odstranenie uzla (alterantiva 1)
    cout << "Vymazavanie uzlov zo stromu:" << endl << endl;
    bool result_remove_node;
    for(const int i: {4,10,8,999}){
        result_remove_node = removeNode1(tree,i);
        cout << "Uzol " << i << " " << (result_remove_node?"":"ne") << "bol vymazany" << endl;
    }
    cout << endl;

    // odstranenie uzla (alternativa 2)
    //    cout << "Vymazavanie uzlov zo stromu:" << endl << endl;
    //    for(const int i: {1,7,-2,999}){
    //        removeNode2(tree,i);
    //    }
    //    cout << endl;

    // vymazanie celeho stromu
    removeTree(&tree);
    cout << "Strom bol vymazany" << endl << endl;

    // vytvorime strom odznova
    tree = createTree({8,3,1,6,4,7,10,14,13});
    cout << endl;

    // preorder prechod stromom
    cout << "Prechod stromom preorder:" << endl;
    preorder(tree);
    cout << endl << endl;

    // inorder prechod stromom
    cout << "Prechod stromom inorder:" << endl;
    inorder(tree);
    cout << endl << endl;

    // postorder prechod stromom
    cout << "Prechod stromom postorder:" << endl;
    postorder(tree);
    cout << endl << endl;

    // level order
    cout << "Prechod stromom levelorder:" << endl;
    levelorder(tree);
    cout << endl << endl;

    // hlbka uzla
    cout << "Hlbka uzla:" << endl << endl;
    for(const int i: {8,3,6,4,-1}){
        try {
            cout << "Uzol " << i <<" ma hlbku: " << depthNode(tree, i) << endl;
        } catch (const string& e) {
            cout << e << endl;
        }
    }
    cout << endl;

    // hlbka stromu - hlbka najvzdialenejsieho listu
    cout << "Hlbka stromu:" << endl;
    cout << depthTree(tree);
    cout << endl << endl;
}

int main() {
    cout << endl << "[ Binarny vyhladavaci strom ]" << endl;
    cout << "...................................................." << endl << endl;
    test_tree();
    return 0;
}