#include "pch.h"
#include <iostream>
using namespace std;
 
struct Item
{
    int key;
    Item * left;
    Item * right;
    Item () : key (0), left (nullptr), right (nullptr) { }
};
 
Item * root = nullptr;
 
Item * search(Item* p, int k) {
 
        while (p != nullptr && p->key != k) {
            if (k < p->key)
                p = p->left;
            else
                p = p->right;
        }
        return p;
}
 
Item* find(Item* p, int k)
{
    if (p == NULL || p->key == k)
    {
        return p;
    }
    else
    {
        if (k > p->key)
        {
            return find(p->right, k);
        }
        else
        {
            return find(p->left, k);
        }
    }
}
 
void insert(Item* & p, int k)
{
    if (p == NULL)
    {
        p = new Item;
        p->key = k;
        p->left = NULL;
        p->right = NULL;
    }
    else if (p->key == k)
    {
    }
    else if (k > p->key)
    {
        insert (p->right, k);
    }
    else
    {
        insert (p->left, k);
    }
}
 
Item* findUnlink(Item *&t) {
    if (t->right != NULL) { return findUnlink(t->right); }
    else { Item* temp = t; t = t->left; return temp; }
}
 
Item* remove(Item* & p, int k) {
    if (p == NULL) { return NULL; }
    else if (k < p->key) return remove(p->left, k);
    else if (k > p->key) return remove(p->right, k);
    else {
        Item* temp = p;
        if (p->left == NULL) { p = p->right;  }
        else if (p->right == NULL) { p = p->left;}
        else {
            Item *t = findUnlink(p->left);
            t->left = p->left;
            t->right = p->right;
            p = t;
        }
        temp->left = NULL;
        temp->right = NULL;
        return temp;
    }
}
void enter (Item * * p, int k)
{
    if (*p == NULL)
    {
        *p = new Item;
        (*p)->key = k;
        (*p)->left = NULL;
        (*p)->right = NULL;
    }
    else if ((*p)->key == k)
    {
 
    }
    else if (k > (*p)->key)
    {
        enter (&((*p)->right), k);
    }
    else
    {
        enter(&((*p)->left), k);
    }
}
 
void ent(Item * * p, int k)
{
    bool cont = true;
    while (cont)
    {
        if (*p == NULL)
        {
            *p = new Item;
            (*p)->key = k;
            (*p)->left = NULL;
            (*p)->right = NULL;
            cont = false;
        }
        else if ((*p)->key == k) cont = false;
        else if (k > (*p)->key)  p = &((*p)->right);
        else p = &((*p)->left);
    }
}
void print(Item* p)
{
    if (p != NULL)
    {
        print(p->left);
        cout << p->key << " ";
        print(p->right);
    }
}
 
void print2 (Item* p)
{
    if (p != NULL)
    {
        cout << p->key << " ";
        // cout << "(";
        print2(p->left);
        // cout << ",";
        print2(p->right);
        // cout << ")";
    }
}
 
void print3(Item* p)
{
    if (p != NULL)
    {
        print3(p->left);
        print3(p->right);
        cout << p->key << " ";
    }
}
 
void clean(Item* p)
{
    if (p != NULL)
    {
        clean(p->left);
        clean(p->right);
        delete p;
    }
}
 
int main()
{
    insert (root, 10);
    insert (root, 5);
    insert (root, 1);
    ent (&root, 20);
    enter(&root, 7);
    remove(root, 5);
 
    Item* t = search(root, 7);
    if (t != nullptr) cout << "Nasel jsem " << endl;
 
    cout << endl << "----" << endl;
    print(root);
    cout << endl << "----" << endl;
    print2(root);
    cout << endl << "----" << endl;
    print3(root);
    cout << endl << "----" << endl;
    clean(root);
 
    cout << "O.K." << endl;
}