removing node

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;
}

You can do it simply, you just need to actually use C syntax (just like you did above): free(right->key) and free(right). On the other hand, you can't do that until you do the strcpy over. Also, you need to unhook that bottom node from the end of the tree (say if you had to do the ->left bit three times, so that b->right->left->left->left is your new b, you will need to fix b->right->left->left so that it doesn't have a left child anymore (since you moved it). Usually that involves keeping another pointer around at the parent of the moved node, so that you can set parent->left=NULL.

Oh ok, yeh with another pointer to the parent i can see how it can be done, but for some reason i cant quite get it right. I get a segmentation error when i try to disconnect the successor node. Can anyone please explain why?

Code:

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;
         bst parent;
         while( right->left != NULL ){
            parent = right;
            right = right->left;
         }
         strcpy(b->key,right->key);
         /*parent->left = NULL; this line give me a segmentation fault*/
         free(right->key);
         free(right);
         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;
}

If you don't ever do the while loop, parent doesn't get set to anything meaningful. Since if right->left is null, we want parent = right, you should set it such when you declare it.

Also, something to consider: if I recall correctly, your keys are malloc'ed -- so you don't necessarily know that b->key has enough room to store right->key. You may want to free b->key and re-malloc with the right amount of room before you strcpy.