Thread: Strange Error (Learning Bstrees)

  1. #1
    Registered User
    Join Date
    Nov 2010

    Question Strange Error (Learning Bstrees)

    Hey, I'm trying to write a program using binary search trees. Everything seems to work up to a certain point, which (as far as I know) shouldn't produce an error. It segmentation faults while it's executing the code below.

    static BstreeNode* tree_insert_helper(Bstree *tree, BstreeNode *current_node, int key, void *value) {
      if (current_node == NULL) {  // create a new leaf node
        current_node = (BstreeNode *)malloc(sizeof(BstreeNode));
        current_node->left_child = NULL;
        current_node->right_child = NULL;
        current_node->key = key;
        current_node->value = value;
        printf("Beginning linking the root node\n");
        printf("%d\n", current_node->key);
        // If making the root node
        if(tree->root->key == current_node->key) //!!! Has some problem with accessing tree's fields! This is where it seg faults.
            printf("Linking the root node\n");
            current_node->next = tree->sentinelNode;
            current_node->prev = tree->sentinelNode;
            tree->sentinelNode->next = current_node;
            tree->sentinelNode->prev = current_node;
      else {
        int compare_result = key - current_node->key;
        if (compare_result < 0)
          current_node->left_child = tree_insert_helper(tree, current_node->left_child, key, value);
          if(key == current_node->left_child->key)
            current_node->left_child->next = current_node;
            current_node->left_child->prev = current_node->prev;
            current_node->prev = current_node->left_child;
            current_node->left_child->prev->next = current_node->left_child;
        else if (compare_result > 0)
          current_node->right_child = tree_insert_helper(tree, current_node->right_child, key, value);
          if(key == current_node->right_child->key)
            current_node->right_child->prev = current_node;
            current_node->right_child->next = current_node->next;
            current_node->next = current_node->right_child;
            current_node->right_child->next->prev = current_node->right_child;
        // else set key to new value
          current_node->value = value;
      return current_node;
    void bstree_insert(void *binary_tree, int key, void *value) {
      Bstree *tree = (Bstree *)binary_tree;
      tree->root = tree_insert_helper(tree, tree->root, key, value);
    Not all of this code was written by me. I just had to modify it.

    The definitions of Bstree and BstreeNode are as follows:
    typedef struct bstreenode {
        int key;
        void *value;
        struct bstreenode *left_child;
        struct bstreenode *right_child;
        struct bstreenode *next;
        struct bstreenode *prev;
    } BstreeNode;
    typedef struct {
        BstreeNode *root;
        BstreeNode *sentinelNode;
    } Bstree;

    What could be causing a seg fault in this code?

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    London, United Kingdom
    Hard to say, have you tried using a debugger?
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Yeah, but I'm not too good at using gdb yet. I managed to use it to trace the error back to that point, but can't get much more out of it. I'll go try again.

    Edit: It's giving me different information this time. Still says that's the problem area, but says that tree->root's address is 0x0. According to the call, though, wouldn't current_node be the same as tree->root on the first run-through?
    Last edited by MSZShadow; 11-16-2010 at 11:13 AM.

  4. #4
    Registered User
    Join Date
    Oct 2008
    The thing about btrees, linked lists and similar data structures is that all references should be to valid memory locations else sigsegv.
    That said, it looks like you're accessing the member tree->root->key though the parent i.e. tree->root doesn't exist yet.
    This is just based on skimming the code so I may very well be wrong but that code snippet sure looks suspicious.

  5. #5
    Registered User
    Join Date
    May 2009
    1. malloc failing and returning null; but, it should have issues sooner.
    2. tree->root being NULL

    Tim S.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Thanks guys. The error was fixed by changing the bugged line to
    if(tree->root == NULL)
    After that, there were a small number of logic errors in my main program, which I fixed. Now it's working fine.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with a strange for-loop problem
    By jasperleeabc in forum C++ Programming
    Replies: 4
    Last Post: 05-29-2009, 08:47 AM
  2. Strange results using dnsapi and windns
    By Niara in forum Networking/Device Communication
    Replies: 3
    Last Post: 08-13-2005, 10:21 AM
  3. strange strange functions
    By threahdead in forum C Programming
    Replies: 4
    Last Post: 10-13-2002, 05:31 PM
  4. strange edffect of "fputs"
    By Abdi in forum C Programming
    Replies: 1
    Last Post: 05-04-2002, 09:41 AM
  5. bcc32 compiling error (really strange!!)
    By jester in forum C++ Programming
    Replies: 14
    Last Post: 01-26-2002, 04:00 PM

Tags for this Thread