i am having a little trouble removing a node with two children from a binary search tree. my algorithms kinda working in that i find a bottom left successor and swap they keys with the node im deleting but then i cant figure out how to delete this successor using my recursive implementation. I have done it before using java, but it was quite a different implementation and i can quite figure this one out.
Code:
struct bstnode{
char *key;
bst left;
bst right;
};
bst bst_remove(bst b, char *s){
if( b == NULL ){
return b;
} if( strcmp(b->key, s) == 0 ){
if( b->left == NULL && b->right == NULL ){
free(b->key);
free(b);
return NULL;
} else if( b->left == NULL || b->right == NULL ){
if( b->left != NULL ){
free(b->key);
return b->left;
}else if( b->right != NULL ){
free(b->key);
return b->right;
}
} else{
bst right = b->right;
while( right->left != NULL ){
right = right->left;
}
/* Need code in here to delete successor!?
why cant i simply do it like this:
&right = NULL; */
strcpy(b->key,right->key);
return b;
}
} else if( strcmp( b->key, s ) < 0 ){
b->right = bst_remove(b->right,s);
} else if( strcmp( b->key, s ) > 0 ){
b->left = bst_remove(b->left,s);
}
return b;
}