#include <algorithm>
#include <iostream>
#include <list>
#include <functional>


template <typename T> class Node
{
public:
    Node() : isEmpty(true), left(0), right(0) {}

    void insert(const T & val)
    {
        if (isEmpty) {
            value = val;
            isEmpty = false;
        } else if (value > val) {
            if (!left)
                left = new Node<T>;
            left->insert(val);
        } else {
            if (!right)
                right = new Node<T>;
            right->insert(val);
        }
    }

    std::list<T> items() const
    {
        std::list<T> r;

        if (left) {
            std::list<T> t = left->items();
            r.insert(r.end(), t.begin(), t.end());
        }

        if (!isEmpty) {
            r.push_back(value);
        }

        if (right) {
            std::list<T> t = right->items();
            r.insert(r.end(), t.begin(), t.end());
        }

        return r;
    }

private:
    T value;
    bool isEmpty;
    Node<T> *left, *right;
};


template <typename T=int> class Tree
{
public:
    Tree() : root(0) {}

    Tree & operator << (const T & value)
    {
        if (!root) root = new Node<T>;

        root->insert(value);

        return *this;
    }

    std::list<T> items() const
    {
        if (root)
            return root->items();
          else
            return std::list<T>();
    }

private:
    Node<T>* root;
};


template <typename T> class Print : public std::unary_function<T, void>
{
public:
    Print(std::ostream * o) : os(o) {}
    void operator () (const T & value) { (*os) << value << ", "; }

private:
    std::ostream * os;
};


template <typename T> std::ostream & operator << (std::ostream & os, const Tree<T> & tree)
{
    std::list<T> items = tree.items();

    std::for_each(items.begin(), items.end(), Print<T>(&os));

    return os;
}


int main(int, char**)
{
    Tree<> a;
    Tree<std::string> b;

    a << 123 << 222 << 456 << 22;
    b << "mano" << "batai" << "buvo" << "du";

    std::cout << a << std::endl << b << std::endl;
}