#ifndef BST_H
#define BST_H

struct BSTNode {
    BSTNode* _left,_right;
    int val;
    BST(int val){
        this->val=val;
        _left=_right=NULL;
    }
};
class BST
{
    public:
        BST();
        void insert(int val,BSTNode*);
        void find(int val,BSTNode*);
        void remove(int val,BSTNode*);

    protected:

    private:
        BSTNode* _head;
};

void BST::insert(int val, BSTNode* &node=_head){

    if(node==NULL){
        node=new BSTNode(val);
        return;
    }
    if(val>=node.val){
        insert(val,node->_right);
    }else{
        insert(val,node->_left);
    }
}

bool BST::find(int val, BSTNode* &node=_head){
    if(node==NULL){
        return false;
    }
    if(val>=node.val){
        return find(val,node->_right);
    }else{
        return find(val,node->_left);
    }


}
bool isleaf(BSTNode* node){
    return node->left==node->right && node->right==NULL;
}

void BST::remove(int val, BSTNode* &node= _head){

    if(node==NULL){
        return;
    }
    if(val==node->val){
        if(isleaf(node)){
            delete node;
            node=NULL;
            return;
        }


    }

    if(val>node->val){
        remove(val,node->_right);
    }else if(val<node->val){
        remove(val,node->_left);
    }



}
#endif // BST_H