C code to implement AVL Tree

AVL tree(Adelson-Velskii and Ladis'tree, named after their inventors) is also called balanced binary tree. Property of AVL tree: the hieght of the two child subtree of any node differ by at most one.If they differ by more than one, re-balancing is done to restore this property.

/* C program to implement AVL Tree */

#include<stdio.h>
#include<malloc.h>

typedef enum { FALSE ,TRUE } bool;
struct node
{
    int info;
    int balance;
    struct node *lchild;
    struct node *rchild;
};

struct node *insert (int , struct node *, int *);
struct node* search(struct node *,int);

main()
{
    bool ht_inc;
    int info ;
    int choice;
    struct node *root = (struct node *)malloc(sizeof(struct node));
    root = NULL;

    while(1)
    {
        printf("1.Insert\n");
        printf("2.Display\n");
        printf("3.Quit\n");
        printf("Enter your choice : ");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1:
            printf("Enter the value to be inserted : ");
            scanf("%d", &info);
            if( search(root,info) == NULL )
                root = insert(info, root, &ht_inc);
            else
                printf("Duplicate value ignored\n");
            break;
        case 2:
            if(root==NULL)
            {
                printf("Tree is empty\n");
                continue;
            }
            printf("Tree is :\n");
            display(root, 1);
            printf("\n\n");
            printf("Inorder Traversal is: ");
            inorder(root);
            printf("\n");
            break;
        case 3:
            exit(1);
        default:
            printf("Wrong choice\n");
        }/*End of switch*/
    }/*End of while*/
}/*End of main()*/

struct node* search(struct node *ptr,int info)
{
    if(ptr!=NULL)
        if(info < ptr->info)
            ptr=search(ptr->lchild,info);
        else if( info > ptr->info)
            ptr=search(ptr->rchild,info);
    return(ptr);
}/*End of search()*/

struct node *insert (int info, struct node *pptr, int *ht_inc)
{
    struct node *aptr;
    struct node *bptr;

    if(pptr==NULL)
    {
        pptr = (struct node *) malloc(sizeof(struct node));
        pptr->info = info;
        pptr->lchild = NULL;
        pptr->rchild = NULL;
        pptr->balance = 0;
        *ht_inc = TRUE;
        return (pptr);
    }

    if(info < pptr->info)
    {
        pptr->lchild = insert(info, pptr->lchild, ht_inc);
        if(*ht_inc==TRUE)
        {
            switch(pptr->balance)
            {
            case -1: /* Right heavy */
                pptr->balance = 0;
                *ht_inc = FALSE;
                break;
            case 0: /* Balanced */
                pptr->balance = 1;
                break;
            case 1: /* Left heavy */
                aptr = pptr->lchild;
                if(aptr->balance == 1)
                {
                    printf("Left to Left Rotation\n");
                    pptr->lchild= aptr->rchild;
                    aptr->rchild = pptr;
                    pptr->balance = 0;
                    aptr->balance=0;
                    pptr = aptr;
                }
                else
                {
                    printf("Left to right rotation\n");
                    bptr = aptr->rchild;
                    aptr->rchild = bptr->lchild;
                    bptr->lchild = aptr;
                    pptr->lchild = bptr->rchild;
                    bptr->rchild = pptr;

                    if(bptr->balance == 1 )
                        pptr->balance = -1;
                    else
                        pptr->balance = 0;
                    if(bptr->balance == -1)
                        aptr->balance = 1;
                    else
                        aptr->balance = 0;
                    bptr->balance=0;
                    pptr=bptr;
                }
                *ht_inc = FALSE;
            }/*End of switch */
        }/*End of if */
    }/*End of if*/

    if(info > pptr->info)
    {
        pptr->rchild = insert(info, pptr->rchild, ht_inc);
        if(*ht_inc==TRUE)
        {
            switch(pptr->balance)
            {
            case 1: /* Left heavy */
                pptr->balance = 0;
                *ht_inc = FALSE;
                break;
            case 0: /* Balanced */
                pptr->balance = -1;
                break;
            case -1: /* Right heavy */
                aptr = pptr->rchild;
                if(aptr->balance == -1)
                {
                    printf("Right to Right Rotation\n");
                    pptr->rchild= aptr->lchild;
                    aptr->lchild = pptr;
                    pptr->balance = 0;
                    aptr->balance=0;
                    pptr = aptr;
                }
                else
                {
                    printf("Right to Left Rotation\n");
                    bptr = aptr->lchild;
                    aptr->lchild = bptr->rchild;
                    bptr->rchild = aptr;
                    pptr->rchild = bptr->lchild;
                    bptr->lchild = pptr;

                    if(bptr->balance == -1)
                        pptr->balance = 1;
                    else
                        pptr->balance = 0;
                    if(bptr->balance == 1)
                        aptr->balance = -1;
                    else
                        aptr->balance = 0;
                    bptr->balance=0;
                    pptr = bptr;
                }/*End of else*/
                *ht_inc = FALSE;
            }/*End of switch */
        }/*End of if*/
    }/*End of if*/

    return(pptr);
}/*End of insert()*/

display(struct node *ptr,int level)
{
    int i;
    if ( ptr!=NULL )
    {
        display(ptr->rchild, level+1);
        printf("\n");
        for (i = 0; i < level; i++)
            printf("    ");
        printf("%d", ptr->info);
        display(ptr->lchild, level+1);
    }/*End of if*/
}/*End of display()*/

inorder(struct node *ptr)
{
    if(ptr!=NULL)
    {
        inorder(ptr->lchild);
        printf("%d ",ptr->info);
        inorder(ptr->rchild);
    }
}/*End of inorder()*/

/* Output of AVL Tree Program */