int main() {
BinarySearchTree<int> me;
me.insert (20);
me.insert (30);
me.insert (-2);
me.insert (10);
me.insert (7);
me.insert (35);
me.insert (24);
me.printTree();
me.findMin();
me.findMax();
me.contains(35);
me.contains(36);
me.remove(-2);
me.printTree();
me.makeEmpty();
me.isEmpty();
me.printTree();
return 0;

using namespace std;

template <typename E>
class BinarySearchTree {
public:
/**
 * Default constructor
 */
BinarySearchTree() {
}

/**
 * Destructor
 */
~BinarySearchTree() {
    purge(root);
}

int findMin(){
    return findMin(root) -> data;
}

int findMax(){
    return findMax(root) -> data;
}

bool contains(const E & x) const{
    if(contains(x, root))
        cout << "True" << endl;
    else
        cout << "False" <<endl;
}

bool isEmpty(){
    if(isEmpty(root))
        cout << "True" << endl;
    else
        cout << "False" <<endl;
}

void makeEmpty(){
    makeEmpty(root);
}

void remove(const E & x){
    remove(x, root);
}

void insert (E item) {
    insert (item, root);
}

void printTree(ostream& out = cout) const {
    print (out, root);
    cout << endl;
}

private:
struct Node {
    E data;
    shared_ptr<Node> left, right;
};

shared_ptr<Node> root;

void print (ostream& out, shared_ptr<Node> ptr) const {
    /* in order traversal */
    if (ptr != nullptr) {
        print (out, ptr->left);
        out << ptr->data << " ";
        print (out, ptr->right);
    }
}

void insert (E item, shared_ptr<Node>& ptr) const {
    if (ptr == nullptr) {
        ptr = make_shared<Node>();
        ptr->data = item;
    } else if (item < ptr->data) {
        insert(item, ptr->left);
    } else if (item > ptr->data) {
        insert(item, ptr->right);
    } else {
        // attempt to insert a duplicate item
    }
}

void purge (shared_ptr<Node> ptr) {
    if (ptr != nullptr) {
        purge (ptr->left);
        purge (ptr->right);
        ptr.reset();
    }
}

bool contains(const E & x, shared_ptr<Node> t) const{
    if(t == nullptr){
        return false;
    }
    else if( x < t-> data){
        return contains(x, t->left);
    }
    else if(t-> data < x){
        return contains(x, t->right);
    }
    else{
        return true;
    }
}

shared_ptr<Node>  findMin(shared_ptr<Node> t) const{
    if (t != nullptr){
        while(t-> left != nullptr){
            t = t->left;
        }
    }
    cout << t->data << endl;
    return t;
}

shared_ptr<Node> findMax(shared_ptr<Node> t) const{
    if (t != nullptr){
        while(t-> right != nullptr){
            t = t->right;
        }
    }
    cout << t->data << endl;
    return t;
}

void remove(const E & x, shared_ptr<Node> t){
    if(t == nullptr){
        return;
    }
    if (x > t-> data){
        remove(x, t-> left);
    }
    else if(t->data > x){
        remove(x, t-> right);
    }
    else if( t-> left != nullptr && t->right != nullptr){
        t-> data = findMin(t-> right) -> data;
        remove(t->data, t-> right);
    }
    else {
      t.reset();
    }
}

void makeEmpty(shared_ptr<Node> t){
    if ( t != nullptr ){
        makeEmpty(t -> left);
        makeEmpty(t-> right);
        t.reset();
    }
}

bool isEmpty(shared_ptr<Node> t) const{
    if( t = nullptr){
        return true;
    }
    else
        return false;
}



};