deleteNode.cpp

Node* deleteNode(int value,Node* node){
    if(node==NULL){
        return node;
    }else if(value< node->data){
        //value is less than node data
        node->left = deleteNode(value,node->left);
    }else if(value>node->data){
        //value is more than node data
        node->right = deleteNode(value,node->right);
    }else{
        //value is equal to node data
        if(node->left==NULL && node->right==NULL){
            //node is a leaf (case 1)
            delete node;
            node = NULL;
        }else if(node->left!=NULL && node->right==NULL){
            // node with only left child
            Node* temp = node;
            node = node->left;
            delete temp;
        }else if(node->left==NULL && node->right!=NULL){
            //node with only right child
            Node* temp = node;
            node = node->right;
            delete temp;
        }else{
            //node is a root
            Node* temp = minimum(node->right);
            node->data = temp->data;
            node->right = deleteNode(temp->data,node->right);
            //delete temp;
        }
    }
    return node;
}
Node* minimum(Node* node){
    Node* curr = node;
    while(curr->left!=NULL){
        curr=curr->left;
    }
    return curr;
}