#include "pch.h"
#include <iostream>
#include <string>
 
using namespace std;
 
struct Item
{
    int key;
    Item * left;
    Item * right;
    Item() : key(0), left(nullptr), right(nullptr) {}
};
 
Item* search (Item* p, int k)
{   
    while (p != nullptr && p->key != k)
    {
        if (p->key < k)
            p = p->right;
        else /* if (p->key > k) */
            p = p->left;
    }
    return p;
}
 
Item* find(Item* p, int k)
{
    if (p == nullptr || p->key == k)
        return p;
    else if (k < p->key)
        return find (p->left, k);
    else /* if (p->key < k)*/
        return find (p->right, k);
}
 
void insert(Item *&p, int k)
{
    if (p == nullptr)
    {
        p = new Item;
        p->key = k;
        p->left = nullptr;
        p->right = nullptr;
    }
    else if (p->key == k)
    {
    }
    else if (k < p->key)
        insert(p->left, k);
    else // (k > p->key)
        insert(p->right, k);
}
 
Item * unlink(Item * &t)
{
    if (t->right != nullptr) 
        return unlink(t->right);
    else  
    {
        Item * zatim = t;
        t = t->left;
        return zatim;
    }
}
 
Item * remove(Item *&p, int k)
{
    if (p == nullptr) return nullptr;
    else if (p->key > k) return remove(p->left, k); 
    else if (p->key < k) return remove(p->right, k);
    else
    {
        Item* zatim= p;
        if (p->left == nullptr) p = p->right;
        else if (p->right == nullptr) p = p->left;
        else
        {
            Item*t= unlink(p ->left);
            t->left = p->left;
            t->right = p->right;
            p = t;
        }
        zatim->left = nullptr;
        zatim->right = nullptr;
        return zatim;
    }
}
 
void enter(Item * * p, int k)
{
    if (*p == nullptr)
    {
        *p = new Item;
        (*p)->key = k;
        (*p)->left = nullptr;
        (**p).right = nullptr;
    }
    else if ((*p)->key == k)
    {
    }
    else if (k < (*p)->key)
        enter (&((*p)->left), k);
    else // (k > (*p)->key)
        enter (&((*p)->right), k);
}
 
void enter2 (Item * * p, int k)
{
    bool cont = true;
    while (cont)
    {
        if (*p == nullptr)
        {
            *p = new Item;
            (*p)->key = k;
            (*p)->left = nullptr;
            (**p).right = nullptr;
            cont = false;
        }
        else if ((*p)->key == k)
        {
            cont = false;
        }
        else if (k < (*p)->key)
            p = &(*p)->left;
        else
            p = &(*p)->right;
    }
}
 
void print(Item *p)
{
    if (p != nullptr)
    {
        print(p->left);
        cout << p->key << " ";
        print(p->right);
    }
}
void print2(Item *p)
{
    if (p != nullptr)
    {
        print2(p->left);
        print2(p->right);
        cout << p->key << " ";
    }
}
 
 
void clean(Item *p)
{
    if (p != nullptr)
    {
        clean(p->left);
        clean(p->right);
        delete p;
    }
}
 
 
void print2 (Item *p)
{
    if (p != nullptr)
    {
        cout << p->key;
        if (p->left != nullptr || p->right != nullptr)
        {
            cout << "( ";
            print2(p->left);
            cout << " , ";
            print2(p->right);
            cout << " )";
        }
    }
}
 
Item * root = nullptr;
 
int main()
{
    insert(root, 10);
    insert(root, 11);
    insert(root, 4);
    insert(root, 22);
    enter2 (&root, 7);
    enter (&root, 2);
    Item * u = remove(root, 7);
    remove(root, 10);
    Item * t = search(root, 7);
    if (t != nullptr) cout << "Nasel jsem" << endl;
 
    print(root);
    print2(root);
 
    cout << "O.K." << endl; 
}