C Program to check if a Binary tree is AVL Tree or Not

Check Binary tree is AVL Tree or Not

Write a C Program to check if a Binary tree is AVL Tree or Not. Here’s simple Program to check if a Binary tree is AVL Tree or Not in C Programming Language.

AVL Tree

AVL tree is a self balanced binary search tree. That means, an AVL tree is also a binary search tree but it is a balanced tree. A binary tree is said to be balanced, if the difference between the heights of left and right subtrees of every node in the tree is either -1, 0 or +1.

In other words, a binary tree is said to be balanced if for every node, height of its children differ by at most one. In an AVL tree, every node maintains a extra information known as balance factor.

Balance factor of a node is the difference between the heights of left and right subtrees of that node. The balance factor of a node is calculated either height of left subtree – height of right subtree (OR) height of right subtree – height of left subtree.

Balance factor = heightOfLeftSubtree – heightOfRightSubtree

Also Read : : C Program to implement AVL Tree and its operations

Below is the source code for C Program to check if a Binary tree is AVL Tree or Not which is successfully compiled and run on Windows System to produce desired output as shown below :

SOURCE CODE : :

/*  C Program to check if a Binary tree is AVL Tree or Not  */

#include<stdio.h>
#include<stdlib.h>
#define MAX 50

struct node
{
        struct node *lchild;
        int info;
        struct node *rchild;
};

struct node *insert(struct node *ptr, int ikey);
int height(struct node *ptr);
int isAVL(struct node *ptr);
struct node *insert(struct node *ptr, int ikey );
int main( )
{
        struct node *root=NULL,*copy_root=NULL, *root1=NULL;
        root = insert(root, 6);
        root = insert(root, 3);
        root = insert(root, 8);
        root = insert(root, 7);
        root = insert(root, 1);
        root = insert(root, 4);
        root = insert(root, 9);
        root = insert(root, 10);
        root = insert(root, 11);
        if( isAVL(root) )
                printf("AVL\n");
        else
                printf("Not AVL\n");
}/*End of main( )*/

int isAVL(struct node *ptr)
{
        int h_l, h_r, diff;
        if(ptr == NULL)
                return 1;
        h_l = height(ptr->lchild);
        h_r = height(ptr->rchild);
        diff = h_l>h_r ? h_l-h_r : h_r-h_l;
        if( diff<=1 &&  isAVL(ptr->lchild) && isAVL(ptr->rchild) )
                return 1;
        return 0;
}

int height(struct node *ptr)
{
        int h_left, h_right;

        if (ptr == NULL) /*Base Case*/
                return 0;

        h_left =  height(ptr->lchild);
        h_right = height(ptr->rchild);

        if (h_left > h_right)
                return 1 + h_left;
        else
                return 1 + h_right;
}/*End of height()*/


struct node *insert(struct node *ptr, int ikey )
{
        if(ptr==NULL)
        {
                ptr = (struct node *) malloc(sizeof(struct node));
                ptr->info = ikey;
                ptr->lchild = NULL;
                ptr->rchild = NULL;
        }
        else if(ikey < ptr->info) /*Insertion in left subtree*/
                ptr->lchild = insert(ptr->lchild, ikey);
        else if(ikey > ptr->info) /*Insertion in right subtree */
                ptr->rchild = insert(ptr->rchild, ikey);
        else
                printf("Duplicate key\n");
        return(ptr);
}/*End of insert( )*/

OUTPUT : :

/* C Program to check if a Binary tree is AVL Tree or Not */

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 1

Enter the key to be inserted : 6

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 1

Enter the key to be inserted : 4

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 1

Enter the key to be inserted : 5

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 1

Enter the key to be inserted : 3

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 1

Enter the key to be inserted : 7

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 1

Enter the key to be inserted : 8

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 2


        8
    7
6
        5
    4
        3

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 3

The Given Binary Tree is AVL Tree.

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 1

Enter the key to be inserted : 2

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 1

Enter the key to be inserted : 1

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 2


        8
    7
6
        5
    4
        3
            2
                1

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 3

The Given Tree is Not AVL Tree

1.Insert Tree
2.Display Tree
3.Check AVL tree
4.Quit

Enter your choice : 4

Process returned 1

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.

Thanks for reading the post…

You may Also Read : :

2.7 3 votes

Article Rating