Thread: problem inserting into recursive BST

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    5

    Question 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!!

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    5
    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..

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  5. #5
    Registered User
    Join Date
    Sep 2008
    Posts
    5
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive function problem
    By trnd in forum C Programming
    Replies: 5
    Last Post: 01-30-2009, 12:36 AM
  2. Replies: 15
    Last Post: 12-13-2008, 09:32 AM
  3. recursive function problem
    By jk81 in forum C Programming
    Replies: 2
    Last Post: 10-25-2002, 06:02 AM
  4. binary tree problem - help needed
    By sanju in forum C Programming
    Replies: 4
    Last Post: 10-16-2002, 05:18 AM
  5. Problem with a recursive function
    By fofone in forum C Programming
    Replies: 2
    Last Post: 03-07-2002, 08:21 AM