Thread: 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.

Code:

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
    else
      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:

Code:

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?

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.

1. malloc failing and returning null; but, it should have issues sooner.
2. tree->root being NULL

Tim S.

Thanks guys. The error was fixed by changing the bugged line to

Code:

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.