#ifndef BSTREE_H_INCLUDED
#define BSTREE_H_INCLUDED

template <class T>
class BSTree : public Set<T>
{
public:
    BSTree()
    {
        mySize = 0;
        root = NULL;
    }

    virtual ~BSTree()
    {
    }

    virtual void add(T element)
    {
        if (root == NULL) {
            root = new BinaryTree<T>(element,NULL,NULL);
        } else  {
            add(root,element);
        }
        mySize++;
    }


    virtual bool contains(T element)
    {
        return contains(root,element);
    }

    virtual void remove(T element)
    {
        remove(root,element);
        mySize--;
    }

    int size()
    {
        return mySize;
    }

    bool isEmpty()
    {
        return mySize == 0;
    }

    T* getMin() {
        if (isEmpty()) {
            return NULL;
        } else {
            BinaryTree<T> *p = root;
            while (p->left != NULL) p = p->left;
        }
    }

    T* getMax() {
        if (isEmpty()) {
            return NULL;
        } else {
            BinaryTree<T> *p = root;
            while (p->right != NULL) p = p->right;
        }
    }

    void print() {
        if (root != NULL) root->print(0);
    }

private:
    void add(BinaryTree<T> *node,T element)
    {
        if (node->element > element)
        {
            if (node->left == NULL) node->left = new BinaryTree<T>(element,NULL,NULL);
            else add(node->left,element);
        }
        else if (node->element < element)
        {
            if (node->right == NULL) node->right = new BinaryTree<T>(element,NULL,NULL);
            else add(node->right,element);
        }
        else
        {
            //duplicate item
        }
    }


    bool contains(BinaryTree<T> *node,T element)
    {
        if (node->element > element)
        {
            return (node->left == NULL) ? false : contains(node->left,element);
        }
        else if (node->element < element)
        {
            return (node->right == NULL) ? false : contains(node->right,element);
        }
        else
        {
            return true;
        }
    }

    BinaryTree<T>* remove(BinaryTree<T> *node,T element)
    {
        if (node == NULL) return node;
        if (element < node->element) {
            node->left = remove(node->left, element);
        } else if (element > node->element) {
            node->right = remove(node->right, element);
        } else {
            if (node->left == NULL || node->right == NULL)
            {
                node = (node->left == NULL ? node->right : node->left);
                --mySize;
            }
            else
            {
                BinaryTree<T> *m = node->right;
                while (m->left != NULL) m = m->left;
                node->element = m->element;
                node->right = remove(node->right, m->element);
            }
        }
        return node;
    }

    BinaryTree<T> *root;
    int mySize;


};

#endif