#ifndef BINARYTREE_H_INCLUDED
#define BINARYTREE_H_INCLUDED

#include <algorithm>

template <class T>
class Visitor {

    public:
        Visitor() {
            myDone = false;
        }

        void done() {
            myDone = true;
        }

        bool isDone() {
            return myDone;
        }

        virtual void visit(T element) = 0;

    private:
        bool myDone;
};

template <class T>
class PrintVisitor : public Visitor<T> {
    public:
        void visit(T element) {
            printf("%d\n",element);
        }
};


template <class T>
class BinaryTree {
    public:
        T element;
        BinaryTree<T>  *left;
        BinaryTree<T>  *right;


        BinaryTree(T element,BinaryTree<T> *left,BinaryTree<T> *right) {
            this->element = element;
            this->left = left;
            this->right = right;
        }


        ~BinaryTree() {

        }

        bool isLeaf() {
            return left == NULL && right == NULL;
        }

        int numNodes() {
            int leftNumNode = (left == NULL)? 0 : left->numNodes();
            int rightNumNode = (right == NULL)? 0 : right->numNodes();
            return 1 + leftNumNode + rightNumNode;
        }

        int height() {
            int nullHeight = -1;
            int leftHeight = (left == NULL) ? nullHeight : left->height();
            int rightHeight = (right == NULL) ? nullHeight : right->height();
            return 1 + ( (leftHeight > rightHeight) ? leftHeight : rightHeight) ;
        }

        BinaryTree* copy() {
            BinaryTree *leftTree = (left == NULL) ? NULL : left->copy();
            BinaryTree *rightTree = (right == NULL) ? NULL : right->copy();
            return new BinaryTree(element, leftTree, rightTree);
        }

        void preOrder(Visitor<T> *v) {
            if (v->isDone()) return;

            v->visit(element);
            if (left != NULL) left->preOrder(v);
            if (right != NULL) right->preOrder(v);
        }

        void inOrder(Visitor<T> *v) {
            if (v->isDone()) return;

            if (left != NULL) left->inOrder(v);
            v->visit(element);
            if (right != NULL) right->inOrder(v);
        }

        void postOrder(Visitor<T> *v) {
            if (v->isDone()) return;

            if (left != NULL) left->postOrder(v);
            if (right != NULL) right->postOrder(v);
            v->visit(element);
        }

        void print(int level) {
            for (int i = 0;i < level;i++)
                printf("    ");
            printf("%d\n",element);
            if (left != NULL) left->print(level + 1);
            else {
                for (int i = 0;i < level + 1;i++)
                    printf("    ");
                printf("*\n",element);
            }
            if (right != NULL) right->print(level + 1);
            else {
                for (int i = 0;i < level + 1;i++)
                    printf("    ");
                printf("*\n",element);
            }
        }

};



#endif // BINARYTREE_H_INCLUDED