CareerCup

root=deleteV(data,root);

///////////
Node* BSTree::deleteV(int data, Node* n){
if (n == NULL){
return NULL;
}
else if (n -> compare(data) > 0) {
n->setLeft(deleteV(data,n->getLeft()));
}
else if (n -> compare(data) < 0) {
n->setRight(deleteV(data,n->getRight()));
}
else {
Node* tmp=NULL;
if (n ->isLeftNull()){
tmp=n;
n=n->getRight();
delete tmp;

}
else if (n->isRightNull()){
tmp=n;
n=n->getLeft();
delete tmp;
}
else {


tmp=n->getLeft();
while(!tmp->isRightNull())
tmp=tmp->getRight();
n->setData(tmp->getData());
n->setLeft(deleteV(tmp->getData(),n->getLeft()));

}

}
return n;
}

clear solution

node *remove(node *root, node *z) {

    if(z == 0)
        return root;

    node *del = z->right;
    if(del != 0 && z->left != 0) {
        // here z has both children: find it's inorder successor
        while(del->left != 0)
            del = del->left;
        z->key = del->key; // rewrite it's key
    } else
        del = z;

    // del is a node to be removed (has at most 1 child)
    node *p = del->parent, *child = del->left;
    if(child == 0)
        child = del->right;

    if(child != 0)
        child->parent = p;
    
    if(p != 0) {
        if(del == p->left) 
            p->left = child;
        else 
            p->right = child;
    } else  
        root = child;

    delete del;
    return root;
}