C Program to Check if a Binary Tree is an AVL Tree or Not

This is a C Program to check whether the given tree is AVL or not. A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of “much farther” and different amounts of work to keep them balanced.
Consider a height-balancing scheme where following conditions should be checked to determine if a binary tree is balanced.
An empty tree is height-balanced. A non-empty binary tree T is balanced if:
1) Left subtree of T is balanced
2) Right subtree of T is balanced
3) The difference between heights of left subtree and right subtree is not more than 1.

Here is source code of the C Program to Check if a Given Binary Tree is an AVL Tree or Not. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* program to check if a tree is height-balanced or not */
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #define bool int
  5.  
  6. /* A binary tree node has data, pointer to left child
  7.  and a pointer to right child */
  8. struct node {
  9.     int data;
  10.     struct node* left;
  11.     struct node* right;
  12. };
  13.  
  14. /* Returns the height of a binary tree */
  15. int height(struct node* node);
  16.  
  17. /* Returns true if binary tree with root as root is height-balanced */bool isBalanced(
  18.         struct node *root) {
  19.     int lh; /* for height of left subtree */
  20.     int rh; /* for height of right subtree */
  21.  
  22.     /* If tree is empty then return true */
  23.     if (root == NULL)
  24.         return 1;
  25.  
  26.     /* Get the height of left and right sub trees */
  27.     lh = height(root->left);
  28.     rh = height(root->right);
  29.  
  30.     if (abs(lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right))
  31.         return 1;
  32.  
  33.     /* If we reach here then tree is not height-balanced */
  34.     return 0;
  35. }
  36.  
  37. /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
  38.  
  39. /* returns maximum of two integers */
  40. int max(int a, int b) {
  41.     return (a >= b) ? a : b;
  42. }
  43.  
  44. /*  The function Compute the "height" of a tree. Height is the
  45.  number of nodes along the longest path from the root node
  46.  down to the farthest leaf node.*/
  47. int height(struct node* node) {
  48.     /* base case tree is empty */
  49.     if (node == NULL)
  50.         return 0;
  51.  
  52.     /* If tree is not empty then height = 1 + max of left
  53.      height and right heights */
  54.     return 1 + max(height(node->left), height(node->right));
  55. }
  56.  
  57. /* Helper function that allocates a new node with the
  58.  given data and NULL left and right pointers. */
  59. struct node* newNode(int data) {
  60.     struct node* node = (struct node*) malloc(sizeof(struct node));
  61.     node->data = data;
  62.     node->left = NULL;
  63.     node->right = NULL;
  64.  
  65.     return (node);
  66. }
  67.  
  68. int main() {
  69.     struct node *root = newNode(1);
  70.     root->left = newNode(2);
  71.     root->right = newNode(3);
  72.     root->left->left = newNode(4);
  73.     root->left->right = newNode(5);
  74.     root->left->left->left = newNode(8);
  75.  
  76.     if (isBalanced(root))
  77.         printf("Tree is AVL");
  78.     else
  79.         printf("Tree is not AVL");
  80.  
  81.     getchar();
  82.     return 0;
  83. }

Output:

$ gcc CheckAVL.c
$ ./a.out
 
Tree is not AVL

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.