Help Debugging my AVL tree program.

I almost feel bad posting such a horrible looking and long piece of code, but IF anybody feels like flexing their programming muscles a little and helping me out, I would really appreciate it. This is an assignment for a college course which is already late and not worth very many points, but I'd like to get it completely working anyway.

I posted an early version of part of this before because I was getting a segmentation fault, which I was able to fix thanks to the help of some members of the forum, so thanks to the people who helped in that thread.

I believe the second use of the insert function produces the seg fault, so the problem must be in that function, or in the getheight() or one of the rotate functions. I realize there are some trivial things wrong with my program that don't really cause a problem(some functions not used(I didn't include those definitions in this post) or no return values), and I'm not worried about those.

So I appreciate any response, even if it's just to say that it's to much of a mess and to start or over something.

Code:

---

#include <stdio.h>

        typedef struct node{
                struct node * left;
                struct node * right;
                int value;
        } NODE;

        typedef struct tree{
                NODE * root;
        } TREE;

/*Function declarations*/
        void insert(NODE * node, NODE * root);
        int getheight(NODE * node);
        NODE * find(int value, NODE * treeroot);
        NODE * findmin(NODE * root);
        NODE * findmax(NODE * root);
        void removenode(NODE * node, NODE * root);
        void traverse(NODE * treeroot);
        NODE * singleRotateWithRightChild(NODE * node);
        NODE * singleRotateWithLeftChild(NODE * node);
        NODE * doubleRotateWithRightChild(NODE * node);
        NODE * doubleRotateWithLeftChild(NODE * node);


int main(void){
        /*Create Avl Tree*/
        TREE tree;
        /*create nodes*/
        NODE rt = {NULL, NULL, 3};
        NODE nd1 = {NULL, NULL, 2};
        NODE nd2 = {NULL, NULL, 1};
        NODE nd3 = {NULL, NULL, 4};
        NODE nd4 = {NULL, NULL, 5};
        NODE nd5 = {NULL, NULL, 6};
        NODE nd6 = {NULL, NULL, 7};
        NODE nd7 = {NULL, NULL, 16};
        NODE nd8 = {NULL, NULL, 15};
        NODE nd9 = {NULL, NULL, 14};
        NODE nd10 = {NULL, NULL, 13};
        NODE nd11 = {NULL, NULL, 12};
        NODE nd12 = {NULL, NULL, 11};
        NODE nd13 = {NULL, NULL, 10};
        NODE nd14 = {NULL, NULL, 8};
        NODE nd15 = {NULL, NULL, 9};

        /*Mark the initial root of the AVL tree*/
        tree.root = &rt;
        tree.root->value = 3;
        /*put nodes in tree*/
        insert(&nd1, tree.root);
        insert(&nd2, tree.root);
        insert(&nd3, tree.root);
        insert(&nd4, tree.root);
        insert(&nd5, tree.root);
        insert(&nd6, tree.root);
        insert(&nd7, tree.root);
        insert(&nd8, tree.root);
        insert(&nd9, tree.root);
        insert(&nd10, tree.root);
        insert(&nd11, tree.root);
        insert(&nd12, tree.root);
        insert(&nd13, tree.root);
        insert(&nd14, tree.root);
        insert(&nd15, tree.root);

        /*print out tree values in-order*/
        traverse(tree.root);
       
        removenode(find(9, tree.root), tree.root);
        removenode(find(6, tree.root), tree.root);
        removenode(find(1, tree.root), tree.root);
        removenode(find(3, tree.root), tree.root);
        /*print out tree values in-order*/
        traverse(tree.root);
        return 0;
}


/**********INSERT************/
void insert(NODE * node, NODE * root){
        if ( node->value > root->value && root->right == NULL)
        {
                root->right = node;
        }
        else if( node->value > root->value && root->right != NULL)
        {
                insert(node, root->right);
                if(getheight(root->right) - getheight(root->left) == 2){
                        if(node->value > root->right->value){
                                singleRotateWithRightChild(root);
                        }
                        else
                                doubleRotateWithRightChild(root);
                }
        }else if ( node->value < root->value && root->left == NULL ){
                root->left = node;       
        }else if ( node->value < root->value && root->left != NULL ){
                insert(node, root->left);
                if (getheight(root->left) - getheight(root->right) == 2){
                if (node->value < root->left->value)
                        singleRotateWithLeftChild(root);
                else
                        doubleRotateWithLeftChild(root);
                }
        }
}


/**********GETHEIGHT************/
int getheight(NODE * node){
        if ( node->left == NULL && node->right == NULL){
                return 0;
}
        if (node->left == NULL && node->right != NULL){
                return (getheight(node->right) + 1);
}
        if (node->right == NULL && node->left != NULL){
                return (getheight(node->left) + 1);
}
        if (getheight(node->left) > getheight(node->right)){
                return getheight(node->left) + 1;
}
        if (getheight(node->right) < getheight(node->left)){
                return getheight(node->right) + 1;
}
return 123;
}


/*********REMOVE************/
void removenode(NODE * node, NODE * root){
        if (node->value == root->right->value && root->right->right == NULL && root->right->left == NULL){
root->right = NULL;
return;
}
        if (node->value == root->left->value && root->left->left == NULL && root->left->right == NULL){
root->left = NULL;
return;
}
        if (node->value == root->right->value){
                /*REMOVENODE RIGHT*/

                NODE * ptr = root->right->right;
                NODE * ptr2 = root->right->left;
                findmax(root->right->left)->right = ptr;//segfault here?
                root->right = ptr2;
        }
        else if(node->value == root->left->value){
                /*REMOVENODE LEFT*/
               
                NODE * ptr = root->left->right;
                NODE * ptr2 = root->left->left;
                findmin(root->left->right)->left = ptr2;
                root->left = ptr;
        }
        else if (node->value > root->value )
        {
                removenode( node, root->right );
        }
        else if (node->value < root->value)
        {
                removenode( node, root->left);
        }
}


/*********TRAVERSE*********/
void traverse(NODE * treeroot){

        if (treeroot->left != NULL){
                traverse(treeroot->left);
        }
       
        printf("%d ", treeroot->value);

        if (treeroot->right != NULL){
                traverse(treeroot->right);
        }

}


/**********SINGLEROTATERIGHT**********/
NODE * singleRotateWithRightChild(NODE * node){
if (node->right == NULL){return node;}
NODE * n2 = node->right;
if (node->right->left != NULL)
{
        node->right = node->right->left;
        node->right->left = node;
        node = n2;
}
else if (node->right->left == NULL){
printf("Error\n");
}

return node;
}


/***********SINGLEROTATELEFT********/
NODE * singleRotateWithLeftChild(NODE * node){
if ( node->left == NULL) {return node;}
NODE * n1 = node->left;
if (node->left->right != NULL){
        node->left = n1;
        node->left->right = node;
        node = n1;
}
else if (node->left->right == NULL) {
printf("Error\n");
}
}


/*********DOUBLEROTATERIGHT***********/
NODE * doubleRotateWithRightChild(NODE * node){
NODE * ptr = node->right;
singleRotateWithLeftChild(ptr);
singleRotateWithRightChild(node);
}


/**********DOUBLEROTATELEFT***********/
NODE * doubleRotateWithLeftChild(NODE * node){
NODE * ptr = node->left;
singleRotateWithRightChild(ptr);
singleRotateWithLeftChild(node);
}
/*end of program*/

---

if (getheight(root->left) - getheight(root->right)

root->right will be null after inserting only one node to left, so you can pass null pointer to the getheight. Which will crash on it.

Also check - what will happen if new value matches one of the present values in the tree

This is where I'd start:
Make every function that takes a pointer work when the passed-in pointer is NULL. This simple change and possible mindshift will actually make your code a LOT clearer and shorter.
Your traverse function then becomes:

Code:

---

void traverse(NODE * treeroot) {
        if (treeroot != NULL) {
                traverse(treeroot->left);
                printf("%d ", treeroot->value);
                traverse(treeroot->right);
        }

}

---

Note that this simple example barely does this idea justice, in showing how much better it becomes.
Try it with your getheight function and you should get it down to only 3 lines in the function body! It currently has six NULL checks, but this change will bring it down to just one.
Once you've done that to all of your code, it should be so much shorter and easier to understand and manage that you may even be able to spot the error on your own.

Note that the return 123; might seem like you're just shutting up the compiler (in a humourous way), but have you considered that it can actually reach that line of code?!