AVL Tree Insertion Causes Seg Fault

Question

I've been trying to implement the rotation functions in my AVL program and I continue to get a seg fault when the Right Rotate function is called. I performed a Valgrind test and there are 3 errors that I get:

==23399== 1 errors in context 1 of 3:
==23399== Invalid read of size 4
==23399==    at 0x8048C3A: insert (avltree.c:190)
==23399==    by 0x80488B6: main (avltree.c:85)
==23399==  Address 0x3 is not stack'd, malloc'd or (recently) free'd
==23399== 
==23399== 
==23399== 1 errors in context 2 of 3:
==23399== Use of uninitialised value of size 4
==23399==    at 0x8048C3A: insert (avltree.c:190)
==23399==    by 0x80488B6: main (avltree.c:85)
==23399==  Uninitialised value was created by a stack allocation
==23399==    at 0x8048723: main (avltree.c:42)
==23399== 
==23399== 
==23399== 1 errors in context 3 of 3:
==23399== Conditional jump or move depends on uninitialised value(s)
==23399==    at 0x8048C03: insert (avltree.c:182)
==23399==    by 0x80488B6: main (avltree.c:85)
==23399==  Uninitialised value was created by a stack allocation
==23399==    at 0x8048723: main (avltree.c:42)

It mentions in two of the errors that there is an uninitialized value. I think it has something to do with me swapping values of the left and right sub-trees, but I cannot seem to pinpoint exactly where things are going wrong.

Here is my Right Rotate function:

void rightRotate(node * y)
{
    /* Assign values */
    node *x = y->left;
    node *subTree = x->right;

    /* Perform rotation */
    x->right = y; /* x is now root */
    y->left = subTree;

    /* Update heights */
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
}

And the way it's all inserted is with the Insertion function:

void insert(node ** tree, node * item)
{
    int balanceNum;

    /* If no root, item is root */
    if(!(*tree)) {
        *tree = item;
        printf("Root: \n"); /*Every node seems to get printed here */
        (*tree)->height = 0;
        return;
    }

    if(strcmp(item->key,(*tree)->key) < 0) {
        insert(&(*tree)->left, item);
    }
    else if(strcmp(item->key,(*tree)->key) > 0) {
        insert(&(*tree)->right, item);
    }
    else if(strcmp(item->key,(*tree)->key) == 0) {
        (*tree)->frequency++;
    }

    /* Update height of ancestor node */
    (*tree)->height = max(height((*tree)->left), height((*tree)->right)) + 1;
    printf("%s Height: %d\n", (*tree)->key, (*tree)->height);

    balanceNum = balance(*tree);

    if(balanceNum > 1 && strcmp(item->key,(*tree)->left->key) < 0) {
        printf("Right Rotate! Balance: %d with %s\n", balanceNum, item->key);
        rightRotate(*tree);
    }
}

I removed the rest of my rotate functions for the sake of this specific situation. Could someone point out where I may have gone wrong with my rotate function?

Thank you so much for any suggestions or tips.

EDIT: I updated my valgrind postings to include the line numbers of my code.

Answer 1

This is because every time you insert a function, the following codes are executed:

   if(!(*tree)) {
        *tree = item;
        printf("Root: \n"); /*Every node seems to get printed here */
        (*tree)->height = 0;
        return;
    }

The reason is that insert() is called recursively.

if(strcmp(item->key,(*tree)->key) < 0) {
    insert(&(*tree)->left, item);
}
else if(strcmp(item->key,(*tree)->key) > 0) {
    insert(&(*tree)->right, item);
}
else if(strcmp(item->key,(*tree)->key) == 0) {
    (*tree)->frequency++;
}

&(*tree)->left can be NULL. Supposing only a root is in the tree currently, its left and right are NULL pointers. An insertion seems to will bypass the if(!(*tree)). However it will call either insert(&(*tree)->left, item) or insert(&(*tree)->right, item), both of them have a NULL pointer as its first parameter.