Balanced Binary Tree in C

This is a C Program to creat a balanced binary search tree. AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

Here is source code of the C Program to Create a Balanced Binary Tree of the Incoming Data. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<stdio.h>
```
```
#include<stdlib.h>
```
```
 
```
```
// An AVL tree node
```
```
struct node {
```
```
    int key;
```
```
    struct node *left;
```
```
    struct node *right;
```
```
    int height;
```
```
};
```
```
 
```

// A utility function to get maximum of two integers

```
int max(int a, int b);
```
```
 
```

// A utility function to get height of the tree

```
int height(struct node *N) {
```
```
    if (N == NULL)
```
```
        return 0;
```
```
    return N->height;
```
```
}
```
```
 
```

// A utility function to get maximum of two integers

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

/* Helper function that allocates a new node with the given key and

```
 NULL left and right pointers. */
```
```
struct node* newNode(int key) {
```

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

```
    node->key = key;
```
```
    node->left = NULL;
```
```
    node->right = NULL;
```

    node->height = 1; // new node is initially added at leaf

```
    return (node);
```
```
}
```
```
 
```

// A utility function to right rotate subtree rooted with y

```
// See the diagram given above.
```

struct node *rightRotate(struct node *y) {

```
    struct node *x = y->left;
```
```
    struct node *T2 = x->right;
```
```
 
```
```
    // Perform rotation
```
```
    x->right = y;
```
```
    y->left = T2;
```
```
 
```
```
    // Update heights
```

    y->height = max(height(y->left), height(y->right)) + 1;

    x->height = max(height(x->left), height(x->right)) + 1;

```
 
```
```
    // Return new root
```
```
    return x;
```
```
}
```
```
 
```

// A utility function to left rotate subtree rooted with x

```
// See the diagram given above.
```

struct node *leftRotate(struct node *x) {

```
    struct node *y = x->right;
```
```
    struct node *T2 = y->left;
```
```
 
```
```
    // Perform rotation
```
```
    y->left = x;
```
```
    x->right = T2;
```
```
 
```
```
    //  Update heights
```

    x->height = max(height(x->left), height(x->right)) + 1;

    y->height = max(height(y->left), height(y->right)) + 1;

```
 
```
```
    // Return new root
```
```
    return y;
```
```
}
```
```
 
```
```
// Get Balance factor of node N
```
```
int getBalance(struct node *N) {
```
```
    if (N == NULL)
```
```
        return 0;
```

    return height(N->left) - height(N->right);

```
}
```
```
 
```

struct node* insert(struct node* node, int key) {

    /* 1.  Perform the normal BST rotation */

```
    if (node == NULL)
```
```
        return (newNode(key));
```
```
 
```
```
    if (key < node->key)
```

        node->left = insert(node->left, key);

```
    else
```

        node->right = insert(node->right, key);

```
 
```

    /* 2. Update height of this ancestor node */

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

```
 
```

    /* 3. Get the balance factor of this ancestor node to check whether

```
     this node became unbalanced */
```
```
    int balance = getBalance(node);
```
```
 
```

    // If this node becomes unbalanced, then there are 4 cases

```
 
```
```
    // Left Left Case
```

    if (balance > 1 && key < node->left->key)

```
        return rightRotate(node);
```
```
 
```
```
    // Right Right Case
```

    if (balance < -1 && key > node->right->key)

```
        return leftRotate(node);
```
```
 
```
```
    // Left Right Case
```

    if (balance > 1 && key > node->left->key) {

        node->left = leftRotate(node->left);

```
        return rightRotate(node);
```
```
    }
```
```
 
```
```
    // Right Left Case
```

    if (balance < -1 && key < node->right->key) {

        node->right = rightRotate(node->right);

```
        return leftRotate(node);
```
```
    }
```
```
 
```

    /* return the (unchanged) node pointer */

```
    return node;
```
```
}
```
```
 
```

// A utility function to print preorder traversal of the tree.

// The function also prints height of every node

```
void preOrder(struct node *root) {
```
```
    if (root != NULL) {
```
```
        printf("%d ", root->key);
```
```
        preOrder(root->left);
```
```
        preOrder(root->right);
```
```
    }
```
```
}
```
```
 
```

/* Drier program to test above function*/

```
int main() {
```
```
    struct node *root = NULL;
```
```
 
```

    /* Constructing tree given in the above figure */

```
    root = insert(root, 10);
```
```
    root = insert(root, 20);
```
```
    root = insert(root, 30);
```
```
    root = insert(root, 40);
```
```
    root = insert(root, 50);
```
```
    root = insert(root, 25);
```
```
 
```

    /* The constructed AVL Tree would be

```
      30
```
```
     /  \
```
```
   20   40
```
```
  /  \     \
```
```
10  25    50
```
```
     */
```
```
 
```

    printf("Pre order traversal of the constructed Balanced Binary tree is \n");

```
    preOrder(root);
```
```
 
```
```
    return 0;
```
```
}
```

Output:

$ gcc BalancedBinaryTree.c
$ ./a.out
 
Pre order traversal of the constructed Balanced Binary tree is 
30 20 10 25 40 50

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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

« Prev - C Program to Check Whether a Given Points are Colinear or Not

» Next - C Program to Check if a Graph is Strongly Connected or Not

Related Posts:

Recommended Articles: