#ifndef BST_H
#define BST_H
template <typename T>
class treeNode {
public:
    treeNode *left;
    treeNode *right;
    T key;
    treeNode(T key)
        : key(key)
        , left(nullptr)
        , right(nullptr) {
    }
};

template <typename T>
class BST {
public:
    BST() {
        root = nullptr;
        nodes = 0;
    }

    BST(BST const& rhs)
        : nodes(rhs.size()) {
        // not yet implemented
    }

    BST& operator = (BST rhs) {
        this->swap(rhs);
    }

    BST& operator = (BST&& rhs) {
        this->swap(rhs);
    }

    ~BST() {
        clear(root);
    }

    void swap(BST& other) {
        std::swap(root, other.root);
        std::swap(nodes, other.nodes);
    }

    void clear(treeNode<T>* node) {
        if(node) {
            if(node->left) clear(node->left);
            if(node->right) clear(node->right);
            delete node;
        }
    }

    bool isEmpty() const {
        return root == nullptr;
    }
    void inorder(treeNode<T>*);
    void traverseInorder();

    void preorder(treeNode<T>*);
    void traversePreorder();

    void postorder(treeNode<T>*);
    void traversePostorder();

    void insert(T const& );

    void remove(T const& );

    treeNode<T>* search(const T &);

    treeNode<T>* minHelper(treeNode<T>*);
    treeNode<T>* min();

    treeNode<T>* maxHelper(treeNode<T>*);
    treeNode<T>* max();

    size_t size() const;

    void sort();
    treeNode<T>* inOrderSuccessor(treeNode<T>*);
    bool isBST(treeNode<T>*) const;
    bool isBST() const;

private:
    treeNode<T> *root;
    size_t nodes;
};
#endif