#include <iostream>
#include <stack>

using namespace std;


template<typename T>
class Tree {
public:
    class node {
    public:
        node* left;
        node* right;
        node* parent;
        T key;
        node(node* parent, T key) {
            this->parent = parent;
            this->key = key;
            this->right = NULL;
            this->left = NULL;

        }
    };
public:
    node* root;

    Tree() {
        root = NULL;
    }

    void push(T key, node* parent) {
        if (parent->key < key) {
            if (parent->right == NULL) {
                parent->right = new node(parent, key);
            }
            else {
                push(key, parent->right);
            }
        }
        else {
            if (parent->left == NULL) {
                parent->left = new node(parent, key);
            }
            else {
                push(key, parent->left);
            }
        }
    }

    void push(T key) {
        if (root == NULL) {
            root = new node(NULL, key);
        }
        else {
            push(key, root);
        }
    }

    static node* findl(node* parent) {
        node* n = parent;

        while (n->left != NULL) {
            n = n->left;
        }

        return n;
    }

    static node* findr(node* parent) {
        node* n = parent;

        while (n->right != NULL) {
            n = n->right;
        }

        return n;
    }

     class iterator {
       public:
           node* current;
           stack<node*> s;

           iterator(node* n) {
               current = n;
           }

           void findn() {
               if (current->right != NULL) {
                   s.push(current);
                   current = Tree::findl(current->right);
               }
               else {
                   node* parent = current->parent;

                   if (!s.empty()) {

                       node* top = s.top();
                       while (top == parent) {
                           parent = top->parent;
                           s.pop();
                           if (s.empty())
                               break;
                           top = s.top();
                       }

                       current = parent;
                   }
               }
           }

           bool operator !=(iterator other) {
               return current != other.current;
           }
           iterator operator++() {
               findn();
               return *this;
           }

           iterator operator++(int) {
               findn();
               return *this;
           }

           T operator *() {
               return current->key;
           }
       };

       iterator begin() {
           return iterator(findl(root));
       }

       iterator end() {
           return iterator(NULL);
       }

    /*class reverse_iterator {
    public:
        node* current;
        stack<node*> s;

        reverse_iterator(node* n) {
            current = n;
        }

        void findn() {
            if (current->left != NULL) {
                s.push(current);
                current = Tree::findr(current->left);
            }
            else if (s.empty()) {
                current = current->parent;
            }
            else {
                node* parent = current->parent;

                if (!s.empty()) {
                    node* top = s.top();
                    while (top == parent) {
                        parent = top->parent;
                        s.pop();
                        if (s.empty())
                            break;
                        top = s.top();
                    }

                    current = parent;
                }
            }
        }

        bool operator !=(reverse_iterator other) {
            return current != other.current;
        }

        reverse_iterator operator++() {
            findn();
            return *this;
        }

        reverse_iterator operator++(int) {
            findn();
            return *this;
        }

        T operator *() {
            return current->key;
        }
    };

    reverse_iterator rbegin() {
        return reverse_iterator(findr(root));
    }

    reverse_iterator rend() {
        return reverse_iterator(NULL);
    }*/
};


int main()
{
    Tree <int> t;

    t.push(5);
    t.push(0);
    t.push(1);
    t.push(2);
    t.push(7);

    t.push(9);
    t.push(6);

    Tree <int> t1;
    t1.push(5);
    t1.push(0);
    t1.push(7);
    t1.push(4);
    t1.push(3);


    Tree <int> t2;
    cout<<"Первое множество"<<endl;
    for (Tree<int>::iterator i = t.begin(); i != t.end(); i++) {
        cout << "{" << *i << "} ";
    }
    for (Tree<int>::iterator i = t.begin(); i != t.end(); i++) {
        t2.push(*i);

    }

    cout<< endl << "Второе множество"<<endl;

    for(Tree<int>::iterator j = t1.begin(); j != t1.end();j++)
    {
        cout << "{" << *j << "} ";
    }
    for(Tree<int>::iterator j = t1.begin(); j != t1.end();j++)
    {
        t2.push(*j);
    }
    cout<< endl << "Итоговое множество"<<endl;
    for(Tree<int>::iterator y = t2.begin(); y != t2.end(); y++)
    {
        cout << "{" << *y << "} ";
    }
    /*cout << "\n------------------------" << endl;
    cout << "iterator: ";
    for (Tree<int>::iterator i = t.begin(); i != t.end(); i++) {
        cout << "{" << *i << "} ";
    }
    cout <<endl <<"reverse_iterator: ";
    for (Tree<int>::reverse_iterator i = t.rbegin(); i != t.rend(); i++) {
            cout << "{" << *i << "} ";
    }*/
    return 0;
}