AVL tree rotation occurs even when the tree is balanced

Question

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

typedef struct node *treenode;

struct node
{
    int data;
    int height;
    treenode left;
    treenode right;
};

int height(treenode t)
{
    if(t == NULL)
        return -1;
    else 
        return t->height;
}


int max(int a, int b)
{
    return (a > b)? a : b;
}

treenode singlerotatewithleft(treenode t)
{
    treenode p;
    p = t->left;
    t->left = p->right;
    p->right = t;
    t->height = max(height(t->left), height(t->right));
    p->height = max(height(p->left), t->height);
    return p;
}
treenode singlerotatewithright(treenode t)
{
    treenode p;
    p = t->right;
    t->right = p->left;
    p->left = t;
    t->height = max(height(t->left), height(t->right));
    p->height = max(height(p->left), t->height);
    return p;
}
treenode doublerotatewithleft(treenode t)
{
    t->left = singlerotatewithright(t->left);
    return singlerotatewithleft(t);
}
treenode doublerotatewithright(treenode t)
{
    t->right = singlerotatewithleft(t->right);
    return singlerotatewithright(t);
}


treenode insert(treenode t, int x)
{


    if(t==NULL)
    {
        t = (struct node*)malloc(sizeof(struct node*));

        if(t == NULL)
        {
            printf("Out of space");
        }
        else
        {
            t->data = x;
            t->height = 0;
            t->left = t->right = NULL;
        }

    }
    if(x < t->data)
    {
        t->left = insert(t->left,x);

        if(height(t->left) - height(t->right) == 2)
        {
            if(x < t->left->data)
                t = singlerotatewithleft(t);
            else
                t = doublerotatewithleft(t);
        }
    }

    else if(x > t->data)
    {
        t->right = insert(t->right,x);

        if(height(t->right) - height(t->left) == 2)
        {
            if(x > t->right->data)
                t = singlerotatewithright(t);
            else
                t = doublerotatewithright(t);
        }
    }

    t->height = max(height(t->left), height(t->right)) + 1;
    return t;
}

void preorder(treenode t)
{
    if(t != NULL)
    {
        printf("%d  ",t->data);
        preorder(t->left);
        preorder(t->right);
    }
}


void main()
{
    int choice;
    treenode root;
    root = NULL;
    do
    {
        printf("\n1.Insert\n2.Preorder traversal\n3.Exit");
        printf("\nEnter choice: ");
        scanf("%d",&choice);

        int x;

        switch(choice)
        {
            case 1:
                printf("\nEnter element to insert: ");
                scanf("%d",&x);
                root = insert(root,x);
                break;
            case 2:
                printf("\nThe preorder traversal is: \n");
                preorder(root);
                break;
        }

    }while(choice != 3);
}

COULD YOU FIND THE ERROR IN THE CODE?OUTPUT-ERROR INSERTING 4

This code is supposed to insert integer elements in the AVL tree. While inserting 3 after 1 and 2, the preorder traversal shows the correct single rotation with right operation performed. But after inserting 4 the tree is balanced, but the preorder traversal shows that another single rotation with right operation is performed. How to fix it?

Answer 1

At least this problem:

Wong allocation

Code allocated the size of a pointer and not a struct.

//                                         v why * ?
t = (struct node*)malloc(sizeof(struct node*));

Instead allocate to the referenced object. Cast not needed.

t = malloc(sizeof t[0]);