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

This is a C++ Program to check if BST is AVL. An AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
A tree is AVL if and only if it is Binary Search Tree and is Balanced.

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.

```
#include <iostream>
```
```
#include <cstdlib>
```
```
using namespace std;
```
```
 
```
```
/* Class SBBSTNode */
```
```
 
```
```
class SBBSTNode
```
```
{
```
```
    public:
```
```
        int height, data;
```
```
        SBBSTNode *left, *right;
```
```
        /* Constructor */
```
```
        SBBSTNode()
```
```
        {
```
```
            left = NULL;
```
```
            right = NULL;
```
```
            data = 0;
```
```
            height = 0;
```
```
        }
```
```
 
```
```
        /* Constructor */
```
```
        SBBSTNode(int n)
```
```
        {
```
```
            left = NULL;
```
```
            right = NULL;
```
```
            data = n;
```
```
            height = 0;
```
```
        }
```
```
};
```
```
 
```
```
/*
```
```
 * Class SelfBalancingBinarySearchTree
```
```
 */
```
```
 
```
```
class SelfBalancingBinarySearchTree
```
```
{
```
```
    private:
```
```
        SBBSTNode *root;
```
```
    public:
```
```
        /* Constructor */
```
```
        SelfBalancingBinarySearchTree()
```
```
        {
```
```
            root = NULL;
```
```
        }
```
```
 
```

        /* Function to check if tree is empty */

```
        bool isEmpty()
```
```
        {
```
```
            return root == NULL;
```
```
        }
```
```
 
```

        /* Make the tree logically empty */

```
        void makeEmpty()
```
```
        {
```
```
            root = NULL;
```
```
        }
```
```
 
```
```
        /* Function to insert data */
```
```
        void insert(int data)
```
```
        {
```
```
            root = insert(data, root);
```
```
        }
```
```
 
```

        /* Function to get height of node */

```
        int height(SBBSTNode *t)
```
```
        {
```

            return t == NULL ? -1 : t->height;

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

        /* Function to max of left/right node */

```
        int max(int lhs, int rhs)
```
```
        {
```

            return lhs > rhs ? lhs : rhs;

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

        /* Function to insert data recursively */

        SBBSTNode *insert(int x, SBBSTNode *t)

```
        {
```
```
            if (t == NULL)
```
```
                t = new SBBSTNode(x);
```
```
            else if (x < t->data)
```
```
            {
```

                t->left = insert(x, t->left);

                if (height(t->left) - height(t->right) == 2)

                    if (x < t->left->data)

```
 
```

                        t = rotateWithLeftChild(t);

```
                    else
```

                        t = doubleWithLeftChild(t);

```
            }
```
```
            else if (x > t->data)
```
```
            {
```

                t->right = insert(x, t->right);

                if (height(t->right) - height(t->left) == 2)

                    if (x > t->right->data)

                        t = rotateWithRightChild(t);

```
                    else
```

                        t = doubleWithRightChild(t);

```
            }
```

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

```
            return t;
```
```
        }
```
```
 
```

        /* Rotate binary tree node with left child */

        SBBSTNode *rotateWithLeftChild(SBBSTNode* k2)

```
        {
```
```
            SBBSTNode *k1 = k2->left;
```
```
            k2->left = k1->right;
```
```
            k1->right = k2;
```

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

            k1->height = max(height(k1->left), k2->height) + 1;

```
            return k1;
```
```
        }
```
```
 
```

        /* Rotate binary tree node with right child */

        SBBSTNode *rotateWithRightChild(SBBSTNode *k1)

```
        {
```
```
            SBBSTNode *k2 = k1->right;
```
```
            k1->right = k2->left;
```
```
            k2->left = k1;
```

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

            k2->height = max(height(k2->right), k1->height) + 1;

```
            return k2;
```
```
        }
```
```
 
```
```
        /*
```

         * Double rotate binary tree node: first left child

         * with its right child; then node k3 with new left child

```
         */
```

        SBBSTNode *doubleWithLeftChild(SBBSTNode *k3)

```
        {
```

            k3->left = rotateWithRightChild(k3->left);

            return rotateWithLeftChild(k3);

```
        }
```
```
 
```
```
        /*
```

         * Double rotate binary tree node: first right child

         * with its left child; then node k1 with new right child

```
         */
```

        SBBSTNode *doubleWithRightChild(SBBSTNode *k1)

```
        {
```

            k1->right = rotateWithLeftChild(k1->right);

            return rotateWithRightChild(k1);

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

        /* Functions to count number of nodes */

```
        int countNodes()
```
```
        {
```
```
            return countNodes(root);
```
```
        }
```
```
 
```
```
        int countNodes(SBBSTNode *r)
```
```
        {
```
```
            if (r == NULL)
```
```
                return 0;
```
```
            else
```
```
            {
```
```
                int l = 1;
```

                l += countNodes(r->left);

                l += countNodes(r->right);

```
                return l;
```
```
            }
```
```
        }
```
```
 
```

        /* Functions to search for an element */

```
        bool search(int val)
```
```
        {
```
```
            return search(root, val);
```
```
        }
```
```
 
```

        bool search(SBBSTNode *r, int val)

```
        {
```
```
            bool found = false;
```

            while ((r != NULL) && !found)

```
            {
```
```
                int rval = r->data;
```
```
                if (val < rval)
```
```
                    r = r->left;
```
```
                else if (val > rval)
```
```
                    r = r->right;
```
```
                else
```
```
                {
```
```
                    found = true;
```
```
                    break;
```
```
                }
```
```
                found = search(r, val);
```
```
            }
```
```
            return found;
```
```
        }
```
```
 
```

        /* Function for inorder traversal */

```
        void inorder()
```
```
        {
```
```
            inorder(root);
```
```
        }
```
```
 
```
```
        void inorder(SBBSTNode *r)
```
```
        {
```
```
            if (r != NULL)
```
```
            {
```
```
                inorder(r->left);
```

                cout << r->data << "  ";

```
                inorder(r->right);
```
```
            }
```
```
        }
```
```
 
```

        /* Function for preorder traversal */

```
        void preorder()
```
```
        {
```
```
            preorder(root);
```
```
        }
```
```
        void preorder(SBBSTNode *r)
```
```
        {
```
```
            if (r != NULL)
```
```
            {
```

                cout << r->data << "  ";

```
                preorder(r->left);
```
```
                preorder(r->right);
```
```
            }
```
```
        }
```
```
 
```

        /* Function for postorder traversal */

```
        void postorder()
```
```
        {
```
```
            postorder(root);
```
```
        }
```
```
        void postorder(SBBSTNode *r)
```
```
        {
```
```
            if (r != NULL)
```
```
            {
```
```
                postorder(r->left);
```
```
                postorder(r->right);
```

                cout << r->data << "  ";

```
            }
```
```
        }
```
```
};
```
```
 
```
```
int main()
```
```
{
```

    SelfBalancingBinarySearchTree sbbst;

    cout << "SelfBalancingBinarySearchTree Test\n";

```
    int val;
```
```
    char ch;
```
```
    /*  Perform tree operations  */
```
```
    do
```
```
    {
```

        cout << "\nSelfBalancingBinarySearchTree Operations\n";

```
        cout << "1. Insert " << endl;
```

        cout << "2. Count nodes" << endl;

```
        cout << "3. Search" << endl;
```

        cout << "4. Check empty" << endl;

        cout << "5. Make empty" << endl;

```
        int choice;
```
```
        cout << "Enter your Choice: ";
```
```
        cin >> choice;
```
```
        switch (choice)
```
```
        {
```
```
            case 1:
```

                cout << "Enter integer element to insert: ";

```
 
```
```
                cin >> val;
```
```
                sbbst.insert(val);
```
```
                break;
```
```
            case 2:
```

                cout << "Nodes = " << sbbst.countNodes() << endl;

```
                break;
```
```
            case 3:
```

                cout << "Enter integer element to search: ";

```
                cin >> val;
```
```
 
```
```
                if (sbbst.search(val))
```

                    cout << val << " found in the tree" << endl;

```
                else
```

                    cout << val << " not found" << endl;

```
                break;
```
```
            case 4:
```

                cout << "Empty status = ";

```
                if (sbbst.isEmpty())
```

                    cout << "Tree is empty" << endl;

```
                else
```

                    cout << "Tree is non - empty" << endl;

```
                break;
```
```
            case 5:
```

                cout << "\nTree cleared\n";

```
                sbbst.makeEmpty();
```
```
                break;
```
```
            default:
```

                cout << "Wrong Entry \n ";

```
                break;
```
```
        }
```
```
 
```
```
        /*  Display tree*/
```
```
        cout << "\nPost order : ";
```
```
        sbbst.postorder();
```
```
        cout << "\nPre order : ";
```
```
        sbbst.preorder();
```
```
        cout << "\nIn order : ";
```
```
        sbbst.inorder();
```

        cout << "\nDo you want to continue (Type y or n): ";

```
        cin >> ch;
```
```
    }
```
```
    while (ch == 'Y' || ch == 'y');
```
```
    return 0;
```
```
}
```

Output:

$ g++ CheckAVL.cpp
$ a.out
 
SelfBalancingBinarySearchTree Test
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 5
 
Post order : 5
Pre order : 5
In order : 5
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 8
 
Post order : 8  5
Pre order : 5  8
In order : 5  8
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 24
 
Post order : 5  24  8
Pre order : 8  5  24
In order : 5  8  24
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 6
 
Post order : 6  5  24  8
Pre order : 8  5  6  24
In order : 5  6  8  24
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 10
 
Post order : 6  5  10  24  8
Pre order : 8  5  6  24  10
In order : 5  6  8  10  24
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 2
Nodes = 5
 
Post order : 6  5  10  24  8
Pre order : 8  5  6  24  10
In order : 5  6  8  10  24
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 3
Enter integer element to search: 6
6 found in the tree
 
Post order : 6  5  10  24  8
Pre order : 8  5  6  24  10
In order : 5  6  8  10  24
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 5
 
Tree cleared
 
Post order :
Pre order :
In order :
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 4
Empty status = Tree is empty
 
Post order :
Pre order :
In order :
Do you want to continue (Type y or n): n
------------------
(program exited with code: 0)
Press return to continue

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 Remove All nodes which don’t lie in Any Path with Sum >= K

» Next - C++ Program to Perform Left and Right Rotation on AVL Tree

Related Posts:

Recommended Articles: