#include <iostream>
#include <memory>
#include <queue>

template<class T>class Node {
private:
    T data = 0;
    std::shared_ptr<Node<T>> left_ptr = nullptr;
    std::shared_ptr<Node<T>> right_ptr = nullptr;

public:
    Node(T data = 0, std::shared_ptr<Node<T>> left_ptr = nullptr, std::shared_ptr<Node<T>> right_ptr = nullptr)
        : data(data), left_ptr(left_ptr), right_ptr(right_ptr)
    {
        // std::cout << "created " << data << "\n";
    }

    ~Node() {
        // std::cout << "deleted " << data << "\n";
    }

    T getData() {
        return data;
    }

    std::shared_ptr<Node<T>>& getLeftNode() {
        return left_ptr;
    }

    std::shared_ptr<Node<T>>& getRightNode() {
        return right_ptr;
    }
};

template<class T>class Tree {
private:
    std::shared_ptr<Node<T>> root = nullptr;

public:
    Tree()
        : root(nullptr)
    { /* empty */ }

    ~Tree() {
        trim(root);
    }

    void addNode(T value) {
        addNode(root, value);
    }

    class Iterator {
    private:
        std::queue<std::shared_ptr<Node<T>>> q;

    public:
        Iterator(std::shared_ptr<Node<T>> node) {
            q.push(node);
        }

        void getNext() {
            if(!q.empty()) {
                std::shared_ptr<Node<T>> node = q.front();
                q.pop();

                if(node->getLeftNode()) {
                    q.push(node->getLeftNode());
                }

                if(node->getRightNode()) {
                    q.push(node->getRightNode());
                }
            }
        }

        bool hasMore() {
            return !q.empty();
        }

        T getData() {
            return q.front()->getData();
        }
    };

    Iterator begin() {
        return Iterator(root);
    }

private:
    void addNode(std::shared_ptr<Node<T>>& node, T value) {
        if(!node) {
            node = std::shared_ptr<Node<T>>(new Node<T>(value));
        } else {
            if(value < node->getData()) {
                addNode(node->getLeftNode(), value);
            } else if(value > node->getData()) {
                addNode(node->getRightNode(), value);
            } else {
                std::cout << "This tree does not admit duplicates\n";
            }
        }
    }

    void trim(std::shared_ptr<Node<T>> node) {
        if(node) {
            trim(node->getLeftNode());
            trim(node->getRightNode());
        }
    }
};

int main() {
    Tree<int> tree;

    tree.addNode(5);
    tree.addNode(3);
    tree.addNode(7);
    tree.addNode(2);
    tree.addNode(4);
    tree.addNode(6);
    tree.addNode(8);

    Tree<int>::Iterator it = tree.begin();

    while(it.hasMore()) {
        std::cout << it.getData() << "->";
        it.getNext();
    }

    std::cout << "\n";


    return 0;
}