problem inserting into recursive BST

hey guys,
Im new to C and having a bit of problems inserting into a recursively defined BST. it seems to work ok inserting 3 or 4 items but any more than that and it starts to make duplicates and do wierd things, i have a feeling it could be a very simple obvious mistake but I just cannot find it. I have included the insertion code and how the tree is defined below:

Code:

---

struct bstnode{
  char *key;
  bst left;
  bst right;
};

bst bst_insert(bst b, char *s){
  if( b == NULL ){
      bst result = emalloc(sizeof * result);
      result->key = emalloc((strlen(s) + 1) * sizeof s[0]);
      strcpy(result->key, s);
      return result;
  } else{
      if( strcmp(b->key, s) == 0 ){
        return b;
      } else if( strcmp(b->key, s) < 0){
        b->right = bst_insert(b->right, s);
      } else if( strcmp(b->key, s) > 0){
        b->left = bst_insert(b->left, s);
      }
  }
}

---

Thanks in advance for the help!!

b->right = bst_insert(b->right, s) will kill the right-hand side of the tree, if it already existed -- probably, since it's not clear what bst_insert will return when we get to that part of the code.

how else can it be done?
in the main method insert is simply called as b = bst_insert(b, "foo");
if i do it like that inside the insert method the tree could never grow bigger than one node, so surely i have to use b->left = bst_insert(b->left, "string"). i really cant get my head around it? this recursive business takes some time to get used to... please let me know if you need more information..

Between my mentioning it, and all those lines that your compiler spits out that say: warning: end of non-void function reached (or something similar), you should figure out that the function ALWAYS needs to return something. When you go into b->right = bst_instert(b->right, s), the funciton still needs to return something. If you don't want the rest of the tree to go away, you need to add the line "return b;" so that the correct element gets passed back up the chain.

Thanks for the help, the new code seems to work.

Code:

---

bst bst_insert(bst b, char *s){
  if( b == NULL ){
      bst result = emalloc(sizeof * result);
      result->key = emalloc((strlen(s) + 1) * sizeof s[0]);
      strcpy(result->key, s);
      return result;
  } else{
      if( strcmp(b->key, s) == 0 ){
        return b;
      } else if( strcmp(b->key, s) < 0){
        b->right = bst_insert(b->right, s);
      } else if( strcmp(b->key, s) > 0){
        b->left = bst_insert(b->left, s);
      }
  }
  return b;
}

---