Thread: Can't firgure out why im getting a segmentation fualt

I am getting a Segmentation Fault when im trying to pass the tree and its root so that the tree can be traversed. The code for an In-Order traversal was given to me and it works. Here is what how i print the tree with an In-Order Traversal:
I call

Code:

RBTreePrint(tree);

from my main program. In a separate file i have the functions:

Code:

/***********************************************************************/
/*  FUNCTION:  RBTreePrint */
/**/
/*    INPUTS:  tree is the tree to print */
/**/
/*    OUTPUT:  none */
/**/
/*    EFFECT:  This function recursively prints the nodes of the tree */
/*             inorder using the PrintKey and PrintInfo functions. */
/**/
/*    Modifies Input: none */
/**/
/***********************************************************************/

void RBTreePrint(rb_red_blk_tree* tree) {
  InorderTreePrint(tree,tree->root->left);
}

/***********************************************************************/
/*  FUNCTION:  InorderTreePrint */
/**/
/*    INPUTS:  tree is the tree to print and x is the current inorder node */
/**/
/*    OUTPUT:  none  */
/**/
/*    EFFECTS:  This function recursively prints the nodes of the tree */
/*              inorder using the PrintKey and PrintInfo functions. */
/**/
/*    Modifies Input: none */
/**/
/*    Note:    This function should only be called from RBTreePrint */
/***********************************************************************/

void InorderTreePrint(rb_red_blk_tree* tree, rb_red_blk_node* x) {
  rb_red_blk_node* nil=tree->nil;
  rb_red_blk_node* root=tree->root;
  if (x != tree->nil) {
    InorderTreePrint(tree,x->left);
    printf("info=");
    tree->PrintInfo(x->info);
    printf("  key="); 
    tree->PrintKey(x->key);
    printf("  l->key=");
    if( x->left == nil) printf("NULL"); else tree->PrintKey(x->left->key);
    printf("  r->key=");
    if( x->right == nil) printf("NULL"); else tree->PrintKey(x->right->key);
    printf("  p->key=");
    if( x->parent == root) printf("NULL"); else tree->PrintKey(x->parent->key);
    printf("  red=%i\n",x->red);
    InorderTreePrint(tree,x->right);
  }
}

With that working, I tried to write a Pre-Order traversal function. My function call is:

Code:

preOrder(tree, root);

And this is where i get the Segmentation Fualt.
Here is the preOrder function

Code:

void preOrder(rb_red_blk_tree* tree, rb_red_blk_node* x)
{
	if(x != tree->nil)
	{
		printNode(tree, x);
		preOrder(tree, x->left);
		preOrder(tree, x->right);
	}
}

Here are the structs for the tree and nodes of the tree.

Code:

typedef struct rb_red_blk_node {
  void* key;
  void* info;
  int red; /* if red=0 then the node is black */
  struct rb_red_blk_node* left;
  struct rb_red_blk_node* right;
  struct rb_red_blk_node* parent;
} rb_red_blk_node;


/* Compare(a,b) should return 1 if *a > *b, -1 if *a < *b, and 0 otherwise */
/* Destroy(a) takes a pointer to whatever key might be and frees it accordingly */
typedef struct rb_red_blk_tree {
  int (*Compare)(const void* a, const void* b); 
  void (*DestroyKey)(void* a);
  void (*DestroyInfo)(void* a);
  void (*PrintKey)(const void* a);
  void (*PrintInfo)(void* a);
  /*  A sentinel is used for root and for nil.  These sentinels are */
  /*  created when RBTreeCreate is caled.  root->left should always */
  /*  point to the node which is the root of the tree.  nil points to a */
  /*  node which should always be black but has aribtrary children and */
  /*  parent and no key or info.  The point of using these sentinels is so */
  /*  that the root and nil nodes do not require special cases in the code */
  rb_red_blk_node* root;             
  rb_red_blk_node* nil;              
} rb_red_blk_tree;

Any help would be appreciated.

You should probably build your tree correctly, as you are either not building a tree or walking off the end of your tree.

I'm using the same tree that was printed with the supplied code.

I also narrowed down where the issue is using print statements. I go to my function to print the nodes

Code:

void printNode(rb_red_blk_tree* tree, rb_red_blk_node* node)
{
	//rb_red_blk_node* nil=tree->nil;
	//rb_red_blk_node* root=tree->root;
	printf("info=");
	tree->PrintInfo(node->info);
	fflush(stdout);
	printf("  key=");
	tree->PrintKey(node->key);
	fflush(stdout);
	printf("  l->key=");
	if( node->left == NULL) printf("NULL"); else tree->PrintKey(node->left->key);
	fflush(stdout);
	printf("  r->key=");
	if( node->right == NULL) printf("NULL"); else tree->PrintKey(node->right->key);
	fflush(stdout);
	printf("  p->key=");
	if( node->parent == tree->root) printf("NULL"); else tree->PrintKey(node->parent->key);
	fflush(stdout);
	printf("  red=%i\n",node->red);
}

and the PrintKey function is a pointer in the tree struct and it points to

Code:

void IntPrint(const void* a) {
	printf("%i",*(int*) a);
}

The print statement is where I get the segmentation fualt.

Now is a really good time to learn how to use your debugger, because if you compile this in debug mode and run it in the debugger, it will stop where the segfault is occurring and you can check out the situation.

I figured it out, I mis-understood how the provided code for the tree works. It seems that the "root" node is not actually the root and I have to pass the tree->root->left node. I assumed this was how the author wrote the In Order traversal because that is the first step, traverse the left child node. Using the debugger help me figure it out.

Thanks for all your help.

Using the debugger help me figure it out.

Excellent. You're well on your way to becoming a software engineer! I can't recommend using the debugger enough. You will learn all sorts of new things by stepping through code in the debugger.