#include <iostream>
using namespace std;
struct drzewoBST
{
    drzewoBST * up;
    drzewoBST * left;
    drzewoBST * right;
  int val;
};
void addBstNode(drzewoBST *&root, int x,drzewoBST * wezel2)
{
    if(root== nullptr)
    {
        auto *w=new drzewoBST();
        w->left= nullptr;
        w->right= nullptr;
        w->up=wezel2;
        w->val=x;

        root=w;

    } else
    {
        if(x>=root->val)
        {
            addBstNode(root->right,x,root);
        }else
            addBstNode(root->left,x,root);
    }
}
void addBstNode(drzewoBST *&root, int x)
{
    if(root== nullptr)
    {
        auto *w=new drzewoBST();
        w->left= nullptr;
        w->right= nullptr;
        w->val=x;

        root=w;

    } else
    {
        if(x>=root->val)
        {
            addBstNode(root->right,x,root);
        }else
            addBstNode(root->left,x,root);
    }
}


void addBstNodeWithRememberUp(drzewoBST *&root, int x)
{
    if(root== nullptr)
    {
        auto *w=new drzewoBST();
        w->left= nullptr;
        w->right= nullptr;
        w->val=x;

        root=w;

    } else
    if(x>=root->val&&root->right== nullptr)
    {
        auto *w=new drzewoBST();
        w->left= nullptr;
        w->right= nullptr;
        w->up=root;
        w->val=x;

        root->right=w;

    }
    else
        if(x<root->val&&root->left== nullptr)
        {
            auto *w=new drzewoBST();
            w->left= nullptr;
            w->right= nullptr;
            w->up=root;
            w->val=x;

            root->left=w;

        }
            else{
        if(x>=root->val)
        {
            addBstNodeWithRememberUp(root->right,x);
        }else
            addBstNodeWithRememberUp(root->left,x);
    }
}
drzewoBST* znajdzMin(drzewoBST *root)
{
    if(root!= nullptr)
    {
        if(root->left!= nullptr)
        znajdzMin(root->left);
        else  return root;

    }

}
drzewoBST* znajdzMax(drzewoBST *root)
{
    if(root!= nullptr)
    {
        if(root->right!= nullptr)
            znajdzMax(root->right);
        else  return root;

    }

}
//drzewoBST* zdnajdzMaxWPodGalezi(drzewoBST *root,int aktualneMaksimum)
//{
//    if(root!= nullptr)
//    {
//        if(root->val>aktualneMaksimum){
//            aktualneMaksimum=root->val;
//
//        }
//    }
//}

drzewoBST * nastepnik (drzewoBST *wezel)
{
    drzewoBST * r;
    if(wezel)
    {
        if(wezel->right) return znajdzMin(wezel->right);
        else {
            r= wezel->up;
            while(r && (wezel==r->right))
            {
                wezel=r;
                r=r->up;
            }
            return r;


        }
    }
    return nullptr;
}
drzewoBST * poprzednik (drzewoBST *wezel)
{
    drzewoBST *r;
    if(wezel)
    {
        if(wezel->left) return znajdzMin(wezel->left);
        else
        {
            r=wezel->up;
            while(r&&(wezel==r->left))
            {
                wezel=r;
                r=r->up;
            }
            return r;
        }

    }return nullptr;
}


drzewoBST* szukaj(drzewoBST *root,int wartoscSzukana)
{
    if(root!= nullptr)
    {
        if(root->val==wartoscSzukana)
        {
            return root;
        }
        if(wartoscSzukana>root->val)
        {
            szukaj(root->right,wartoscSzukana);
        }else szukaj(root->left,wartoscSzukana);

        return nullptr;
    }

}
//funkcja usuwająca liście tego drzewa
void usunTo(drzewoBST *&root)
{
    delete root;
    root= nullptr;
}

void usunLiscie (drzewoBST *&root) // gdzieś się wykrzacza funkcja przy wypisywaniu
{
    if(root!= nullptr)
    {
        if(root->left== nullptr&&root->right== nullptr)//gdy nie ma możliwości zejścia w dół
        {
            usunTo(root);
        }else
        {
            if(root->left!= nullptr)
            {
                usunLiscie(root->left);
            }
            if(root->right!= nullptr)
            {
                usunLiscie(root->right);
            }
        }

    }
}

//inorder ( wyświetlanie )
void inorder(drzewoBST *&root)
{
    if(root!= nullptr)
    {
        inorder(root->left);
        cout<<root->val<<" ";
        inorder(root->right);
    }else
    return;
}
int main() {
  drzewoBST * drzewo=nullptr;
    addBstNode(drzewo,12);
    addBstNode(drzewo,16);
    addBstNode(drzewo,25);
    addBstNode(drzewo,14);
    addBstNode(drzewo,3);
    addBstNode(drzewo,8);
    addBstNode(drzewo,22);
    addBstNode(drzewo,16);
    addBstNode(drzewo,10);
    addBstNode(drzewo,27);
    drzewoBST * drzewo2=nullptr;
    addBstNode(drzewo2,12);
    addBstNode(drzewo2,6);
    addBstNode(drzewo2,-5);
    addBstNode(drzewo2,11);
    addBstNode(drzewo2,3);
    addBstNode(drzewo2,8);
    addBstNode(drzewo2,22);
    addBstNode(drzewo2,16);
    addBstNode(drzewo2,10);
    addBstNode(drzewo2,27);



    inorder(drzewo);
    cout<<endl;
    usunLiscie(drzewo);
    inorder(drzewo);
    cout<<endl;
    usunLiscie(drzewo2);
    inorder(drzewo2);
    cout<<endl;
    drzewoBST * nowe=nullptr;
    addBstNodeWithRememberUp(nowe,12);
    addBstNodeWithRememberUp(nowe,16);
    addBstNodeWithRememberUp(nowe,25);
    addBstNodeWithRememberUp(nowe,14);
    addBstNodeWithRememberUp(nowe,3);
    addBstNodeWithRememberUp(nowe,8);
    addBstNodeWithRememberUp(nowe,22);
    addBstNodeWithRememberUp(nowe,16);
    addBstNodeWithRememberUp(nowe,10);
    addBstNodeWithRememberUp(nowe,27);
    inorder(nowe);
    cout<<endl<<znajdzMin(nowe)->val<<endl<<znajdzMax(nowe)->val<<endl;
/// TESTOWANIE POPRZEDNIKA I NASTĘPNIKA
    drzewoBST *drzewoBst= nullptr;
    addBstNodeWithRememberUp(drzewoBst,15);
    addBstNodeWithRememberUp(drzewoBst,6);
    addBstNodeWithRememberUp(drzewoBst,22);
    addBstNodeWithRememberUp(drzewoBst,-5);
    addBstNodeWithRememberUp(drzewoBst,14);
    addBstNodeWithRememberUp(drzewoBst,8);
    addBstNodeWithRememberUp(drzewoBst,12);
    addBstNodeWithRememberUp(drzewoBst,13);
    addBstNodeWithRememberUp(drzewoBst,18);
    addBstNodeWithRememberUp(drzewoBst,27);
    addBstNodeWithRememberUp(drzewoBst,17);
    inorder(drzewoBst);
    cout<<endl;
    cout<<drzewoBst->left->right->left->right->right->val<<endl;
    cout<<poprzednik(drzewoBst->left->right->left->right->right)->val<<endl;//ok
    cout<<drzewoBst->right->left->left->val<<endl;
    cout<<poprzednik(drzewoBst->right->left->left)->val<<endl;//ok
    cout<<poprzednik(drzewoBst)->val<<endl;
    cout<<nastepnik(drzewoBst)->val<<endl;
    cout<<nastepnik(drzewoBst->right->right);
    return 0;
}