#include <iostream>
#include <sstream>
#include <conio.h>
#include <vector.h>

using namespace std;

class Node{
        public:
        int key;
        char *key_char;
        Node *left;
        Node *right;
        Node(int key){
                key_char=new char[10];
                this->key=key;
                this->left=NULL;
                this->right=NULL;
                stringstream tmp;
                tmp<<key;
                tmp>>this->key_char;
        }
        ~Node(){
                delete [] this->key_char;
        }
};

class Tree_BST{
        public:
        Node *root;
        Tree_BST(){
                this->root=NULL;
        }

        bool Insert(int key){
                if(!this->root){        //Drzewo puste
                        this->root=new Node(key);
                        return true;
                }
                else{                   //Drzewo nipuste
                        Node *it=this->root;
                        while(true){
                                if(key < it->key)
                                        if(it->left)
                                                it=it->left;    //Juz istnieje it->left, idziemy w lewo
                                        else{
                                                it->left=new Node(key); //Dodanie Node z key jako it->left
                                                return true;
                                        }
                                else if(key > it->key)
                                        if(it->right)
                                                it=it->right;   //Juz istnieje it->right, idziemy w prawo
                                        else{
                                                it->right=new Node(key);        //Dodanie Node z key jako it->right
                                                return true;
                                        }
                                else
                                        return false;   //Klucz key juz istnieje
                        }
                }
        }

        void Insert_multiple(int n){
                for(int i=0;i<n;i++)
                        this->Insert( rand()%90001 + 9999 );
        }

        void DFS_preorder(){
                int n=0;
                this->DFS_preorder_rec(this->root,&n);
                cout<<"\nPrzeszukano "<<n<<" elementow.";
                return;
        }

        void DFS_inorder(){
                int n=0;
                this->DFS_inorder_rec(this->root,&n);
                cout<<"\nPrzeszukano "<<n<<" elementow.";
                return;
        }

        void DFS_postorder(){
                int n=0;
                this->DFS_postorder_rec(this->root,&n);
                cout<<"\nPrzeszukano "<<n<<" elementow.";
                return;
        }

        vector < Node* > Find(Node *it,int key){
                vector < Node* > stack;
                if(!this->root)
                        return stack;
                if(this->root->key==key)
                        return stack;
                while(true){
                        if (! stack.size() ){   //Prawda <=> it jest korzeniem
                                stack.push_back(it);
                        }
                }
                return stack;
        }

        bool Delete(int key){

        }

        ~Tree_BST(){
                this->Delete_whole();
        }

        void Delete_whole(){
                this->Delete_whole_rec(this->root);
                this->root=NULL;
        }

        private:
        void Delete_whole_rec(Node *it){
                if(it){
                        if(it->left)
                                Delete_whole_rec(it->left);
                        if(it->right)
                                Delete_whole_rec(it->right);
                        delete it;
                }
                return;
        }

        void DFS_preorder_rec(Node *it,int *n){
                if(it){
                        *n+=1;
                        cout<<endl<<it->key;
                        if(it->left)
                                DFS_preorder_rec(it->left,n);
                        if(it->right){
                                DFS_preorder_rec(it->right,n);
                        }
                }
                return;
        }

        void DFS_inorder_rec(Node *it,int *n){
                if(it){
                        if(it->left)
                                DFS_inorder_rec(it->left,n);
                        *n+=1;
                        cout<<endl<<it->key;
                        if(it->right)
                                DFS_inorder_rec(it->right,n);
                }
        }

        void DFS_postorder_rec(Node *it,int *n){
                if(it){
                        if(it->left)
                                DFS_inorder_rec(it->left,n);
                        if(it->right)
                                DFS_inorder_rec(it->right,n);
                        *n+=1;
                        cout<<endl<<it->key;
                }
        }
};

int main(){
        Tree_BST *Tree=new Tree_BST();

        Tree->Insert(3);
        Tree->Insert(5);
        Tree->Insert(-10);
        Tree->Insert(17);

        Tree->Delete_whole();

        Tree->Insert(1);
        Tree->Insert(0);
        Tree->Insert(2);
        Tree->Insert(-1);

        Tree->DFS_inorder();

        getche();
        return 0;
}