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.

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.

`/* program to check if a tree is height-balanced or not */`

`#include<stdio.h>`

`#include<stdlib.h>`

`#define bool int`

`/* A binary tree node has data, pointer to left child`

`and a pointer to right child */`

struct node {

int data;

struct node* left;

struct node* right;

};

`/* Returns the height of a binary tree */`

int height(struct node* node);

/* Returns true if binary tree with root as root is height-balanced */bool isBalanced(

struct node *root) {

int lh; /* for height of left subtree */

int rh; /* for height of right subtree */

`/* If tree is empty then return true */`

if (root == NULL)

return 1;

`/* Get the height of left and right sub trees */`

lh = height(root->left);

rh = height(root->right);

if (abs(lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right))

return 1;

`/* If we reach here then tree is not height-balanced */`

return 0;

`}`

`/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */`

`/* returns maximum of two integers */`

int max(int a, int b) {

return (a >= b) ? a : b;

`}`

`/* The function Compute the "height" of a tree. Height is the`

`number of nodes along the longest path from the root node`

`down to the farthest leaf node.*/`

int height(struct node* node) {

`/* base case tree is empty */`

if (node == NULL)

return 0;

`/* If tree is not empty then height = 1 + max of left`

`height and right heights */`

return 1 + max(height(node->left), height(node->right));

`}`

`/* Helper function that allocates a new node with the`

`given data and NULL left and right pointers. */`

struct node* newNode(int data) {

struct node* node = (struct node*) malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return (node);

`}`

int main() {

struct node *root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

root->left->left->left = newNode(8);

if (isBalanced(root))

printf("Tree is AVL");

`else`

printf("Tree is not AVL");

getchar();

return 0;

`}`

Output:

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

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

advertisement

advertisement

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

**Next Steps:**

- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**

- Buy Data Structure Books
- Buy Programming Books
- Practice Computer Science MCQs
- Apply for Information Technology Internship
- Practice Design & Analysis of Algorithms MCQ