// Lab3.cpp : Ten plik zawiera funkcję „main”. W nim rozpoczyna się i kończy wykonywanie programu.
//

#include "pch.h"
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
#include  <stdlib.h>
#include  <stdio.h>
#include  <string.h>
#include <fstream>
#include "time.h"

using namespace std;

class BST
{
    struct node
    {
        int data;
        node* left;
        node* right;
        char tab[10];
    };

    node* root;

    node* makeEmpty(node* t)
    {
        if (t == NULL)
            return NULL;
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        return NULL;
    }

    node* insert(int x, node* t)
    {
        if (t == NULL)
        {
            t = new node;
            t->data = x;
            t->left = t->right = NULL;
        }
        else if (x < t->data)
            t->left = insert(x, t->left);
        else if (x > t->data)
            t->right = insert(x, t->right);
        return t;
    }

    node* findMin(node* t)
    {
        if (t == NULL)
            return NULL;
        else if (t->left == NULL)
            return t;
        else
            return findMin(t->left);
    }

    node* findMax(node* t)
    {
        if (t == NULL)
            return NULL;
        else if (t->right == NULL)
            return t;
        else
            return findMax(t->right);
    }

    node* remove(int x, node* t)
    {
        node* temp;
        if (t == NULL)
            return NULL;
        else if (x < t->data)
            t->left = remove(x, t->left);
        else if (x > t->data)
            t->right = remove(x, t->right);
        else if (t->left && t->right)
        {
            temp = findMin(t->right);
            t->data = temp->data;
            t->right = remove(t->data, t->right);
        }
        else
        {
            temp = t;
            if (t->left == NULL)
                t = t->right;
            else if (t->right == NULL)
                t = t->left;
            delete temp;
        }

        return t;
    }

    void inorder(node* t)
    {
        if (t == NULL)
            return;
        inorder(t->left);
        cout << t->data << " " << endl;;
        inorder(t->right);


    }

    node* find(node* t, int x)
    {
        if (t == NULL)
            return NULL;
        else if (x < t->data)
            return find(t->left, x);
        else if (x > t->data)
            return find(t->right, x);
        else
            return t;
    }
    void Preorder(node* t)
    {
        if (t == NULL)
            return;


        cout << t->data << " " << endl ;
        Preorder(t->left);
        Preorder(t->right);
    }

public:
    BST()
    {
        root = NULL;
    }

    ~BST()
    {
        root = makeEmpty(root);
    }

    void insert(int x)
    {
        root = insert(x, root);
    }

    void remove(int x)
    {
        if (root = NULL) {
            cout << "Nie da się" << endl;
        }
        else {
            root = remove(x, root);
        }
    }

    void displayI()
    {
        inorder(root);
        cout << endl;
    }
    void displayP()
    {
        Preorder(root);
        cout << endl;
    }

    void search(int x)
    {
        root = find(root, x);

    }
};

int main()
{
    clock_t begin, end;
    double time_spent;
    begin = clock();
    int X, k1, k2, k3, k4, k5;
    ifstream fin("inlab03.txt", ios::in | ios::out);
    fin >> X >> k1 >> k2 >> k3 >> k4 >> k5;




    BST t;
    t.remove(k1);
    t.insert(k1);
    int i = 0;
    for (int i = 0; i < X; i++) {
        srand(time(NULL));
        int j = 0;
        while (j < X) {

            int y = rand() % 20001 - 9999;
            t.insert(y);

            j++;
        }
    }

    cout << "-=======1========-" << endl;
    t.displayI();
    cout << "-=======2========-" << endl;
    t.displayP();

    t.insert(k2);
    cout << "-=======3========-" << endl;
    t.displayI();

    t.insert(k3);

    t.insert(k4);

    t.remove(k1);
    cout << "-=======4========-" << endl;
    t.displayP();

    //t.search(k1);


    t.remove(k2);
    cout << "-=======5========-" << endl;
    t.displayI();

    t.remove(k3);

    t.remove(k4);

    end = clock();
    time_spent = (double)(end-begin) / CLOCKS_PER_SEC;
    cout << time_spent << endl;

}