Segmentation Fault during Balancing of violated AVL tree

Question

I try to implement a program that illustrates the basic operation of an AVL tree. Previously I made that code as a Binary Search Tree and extended its operation to act as AVL. The issue comes every time the tree has to balance no matter what rotation. In all cases (LL LR RR RL) I get a segmentation fault. I can't find what I am doing wrong.

#include <stdio.h>
#include <stdlib.h>


//define the node for the BST
typedef struct node
{
    struct node * left;
    int data;
    struct node * right;
    int height;
}node;

typedef node * BST;

//function definitions 
void BST_INSERT(BST *tree,int data);
void BST_DESTROY(BST *tree);
BST NODE_CREATE(int data);
//AVL OPERATIONS
BST ROTATE_L(BST C);
BST ROTATE_R(BST C);
BST ROTATE_LR(BST C);
BST ROTATE_RL(BST C);
int max(int a,int b);
int height(BST C);



//main function
int main(void)
{
    BST t = NULL;
//case with seg fault 
   BST_INSERT(&t,10);
    BST_INSERT(&t,15);
    BST_INSERT(&t,20);
    BST_INSERT(&t,25);
//another case with seg fault 
    BST_INSERT(&t,0);
    BST_INSERT(&t,-5);
    BST_INSERT(&t,-10);
    BST_INSERT(&t,-15);
//non seg fault case 
 /* BST_INSERT(&t,10);
    BST_INSERT(&t,5);
    BST_INSERT(&t,15);
    BST_INSERT(&t,3);
    BST_INSERT(&t,6);
    BST_INSERT(&t,14);
    BST_INSERT(&t,16);

*/


    return 0;
}








//helper to create a new node before intgrating it to the tree
//its not nessecaty but is used in order to create some abstraction
//to the main function
BST NODE_CREATE(int data)
{
        BST new = (BST)malloc(sizeof(node));
        if(!new)
        {
            fprintf(stderr,"error allocating memory\n");
            return NULL;
        }
        new->data = data;
        new->right = NULL;

        new->left = NULL;
        return new;
}
//insert a node in the BST
//recursively find the proper position for the element to be inserted 
//left wise for the smallest elementsprintf("___UNDER CONSTRUCTION___");
//right wise for the highest elements return 0;
//take as base case null
//if bigger than current element move to the right child 
//if equal or smaller than the current parent move to the left child 
//if the node is null place the element there 
//works also for uninitialized tree
void BST_INSERT(BST *tree,int data)
{
    //base case 
    if(*tree == NULL)
    {
        *tree = NODE_CREATE(data);
        return;
    }
    else if(data <= (*tree)->data)
    {
        BST_INSERT(&(*tree)->left,data);
    }
    else
    {
        BST_INSERT(&(*tree)->right,data);
    }

    // Update the height of the current node
    (*tree)->height = max(height((*tree)->left), height((*tree)->right)) + 1;

    // Check balance factor and perform rotations if necessary
    int balance = height((*tree)->left) - height((*tree)->right);

    // Left-Left Case
    if (balance > 1 && data <= (*tree)->left->data) {
        *tree = ROTATE_R(*tree);
    }
    // Left-Right Case
    else if (balance > 1 && data > (*tree)->left->data) {
        *tree = ROTATE_LR(*tree);
    }
    // Right-Right Case
    else if (balance < -1 && data > (*tree)->right->data) {
        *tree = ROTATE_L(*tree);
    }
    // Right-Left Case
    else if (balance < -1 && data <= (*tree)->right->data) {
        *tree = ROTATE_RL(*tree);
    }
}

//recursive aproach to destroy the binary search tree
//traverse to the lowest nodes from left to right
//if we reach null node then we destroy the node
//following the order left-right-parent
void BST_DESTROY(BST *tree)
{
    //base case NULL node 
    if(*tree == NULL)
    {
        return;
    }
    BST_DESTROY(&(*tree)->left);
    BST_DESTROY(&(*tree)->right);
    printf("deleting : %i ",(*tree)->data);
    free(*tree);

}

//find the height of the nodes and the maximum of them

int max(int a,int b)
{
    //return the highest height
    return (a > b) ? a : b;
}
int height(BST C)
{
    //null node
    if(C == NULL)
    {
        return 0;
    }
    return C->height;
}


//perform LEFT rotation
BST ROTATE_L(BST C)
{
    BST L = C->left;
    C->left = L->right;
    L->right = C;
    C->height = max(height(C->left),height(C->right))+1;
    L->height = max(height(L->left),height(L->right))+1;
    return L;
}

//perform right rotation
BST ROTATE_R(BST C)
{
    BST R = C->right;
    C->right = R->left;
    R->left = C;
    C->height = max(height(C->left),height(C->right))+1;
    R->height = max(height(R->left),height(R->right))+1;
    return R;
}
//perform rl rotation
BST ROTATE_RL(BST C)
{
    C->right = ROTATE_R(C->right);
    return ROTATE_L(C);
}
//perform lr rotation
BST ROTATE_LR(BST C)
{
    C->left = ROTATE_L(C->left);
    return ROTATE_R(C);
}

I didn't send the whole code because as I said I already implemented the code for a BST tree so I'm pretty sure it's correct. My considerations are on the rotation functions.

The insertions I tried were: 1,2,3,4 4,3,2,1 10,5,20,25,0 and I also tried insertions where all the elements don't violate the rules of the AVL. To be more accurate the insertions: 10,5,15,4,6,14,16,20 didn't caused a segmentation fault because they didn't break the rule.

You will see in my code a function called BST_DESTROY. This is to destroy the tree before the program ends. Currently in my program above I don't use it but it's fully functional.

Answer 1

Check your rotation logic. In BALANCE_L, you are setting

BST L = C->left;

and using L without checking that it is non-NULL:

L->right = C;