//returns -1 on failure,
int BinTree::remove(dwelling & result) {
return del(root,result);
}
//we are going to delete a node with a goal of 'no child left behind'
int BinTree::del(node * curroot, dwelling &d) {
if (curroot == NULL) {
//empty tree D:
return -1;
} else if (strcmp(d.location,curroot->d.location) < 0) {
return del(curroot->left,d);
} else if (strcmp(d.location,curroot->d.location) > 0) {
return del(curroot->right,d);
} else {
//remove this node
if (curroot->right == NULL && curroot->left == NULL) {
//sucessor is null. no children
} else if (curroot->right != NULL && curroot->left == NULL) { //one child
curroot = curroot->right;
} else if (curroot->left == NULL && curroot->left != NULL) { //one child
curroot = curroot->left;
} else { //both children, we have to find a sucessor!
node * successor;
successor = curroot->right;
node * prev = curroot;
//now go left all the way
while (successor->left != NULL) {
prev = successor;
successor = successor->left;
}
prev->left = successor->right;
//copy sucessor's data into root
copyDwelling(successor->d,curroot->d);
delete successor;
}
return 1; //we removed the node
}
}