UNIT-4

NON LINEAR DATA STRUCTURES

TREES –BT, BST & AVL
In linear data structure data is organized in sequential order and in non-linear data structure data
is organized in random order. Tree is a very popular non-linear data structure used in wide range
of applications. A tree data structure can be defined as follows...

Trees Basic Concepts:

A tree is a non-empty set one element of which is designated the root of the tree while the remaining
elements are partitioned into non-empty sets each of which is a sub-tree of the root.

Tree is a non-linear data structure which organizes data in hierarchical structure and this is a recursive
definition.

Tree data structure is a collection of data(Node)which is organized in hierarchical structure

recursively

A treeT is a set of nodes storing elements such that the nodes have a parent-child relationship
that satisfies the following
• If T is not empty, That is special tree called the root that has no parent.
• Each node v of Tdifferent than the root has a unique parent node w; node with parent w is a
child of w.

Tree nodes have many useful properties:

 The depth of a node is the length of the path(or the number of edges)from the root to that
node.
 The height of a node is the longest path from that node to its leafs. The height of a tree is
the height of the root. A leaf node has no children -- its only path is up to its parent.
 In a tree data structure,if we have N number of nodes then we can have a
maximum of N-1 number of links.

1
 Terminology of Tree: In a tree data structure, we use the following terminology...

1. Root
In a tree data structure, the first node is called as Root Node. Every tree must have root [Link]
can say that root node is the origin of tree data structure. In any tree, there must be only one root
node. We never have multiple root nodes in a tree.

2. Edge
In a tree data structure, the connecting link between any two nodes is called as EDGE. In a tree
with 'N' number of nodes there will be a maximum of 'N-1' number of edges.

3. Parent
In a tree data structure, the node which is predecessor of any node is called as PARENT NODE. In
simple words, the node which has branch from it to any other node is called as parent node. Parent
node can also be defined as "The node which has child / children".

2
4. Child
In a tree data structure, the node which is descendant of any node is called as CHILD Node. In
simple words, the node which has a link from its parent node is called as child node. In a tree,
any parent node can have any number of child nodes. In a tree, all the nodes except root are child
nodes.

5. Siblings
In a tree data structure, nodes which belong to same Parent are called as SIBLINGS. In simple
words, the nodes with same parent are called as Sibling nodes.

3
6. Leaf
In a tree data structure, the node which does not have a child is called as LEAF Node. In simple
words, a leaf is a node with no child.
In a tree data structure, the leaf nodes are also called as External Nodes. External node is also a
node with no child. In a tree, leaf node is also called as 'Terminal' node.

7. Internal Nodes
In a tree data structure, the node which has at least one child is called as INTERNAL Node. In
simple words, an internal node is a node with at least one child.
In a tree data structure, nodes other than leaf nodes are called as Internal Nodes.
The root node is also said to be Internal Node if the tree has more than one node. Internal
nodes are also called as 'Non-Terminal' nodes.

8. Degree
In a tree data structure, the total number of children of a node is called as DEGREE of that
Node. In simple words, the Degree of a node is total number of children it has. The highest
degree of a node among all the nodes in a tree is called as 'Degree of Tree'

4
9. Level
In a tree data structure, the root node is said to be at Level 0 and the children of root node are at
Level 1 and the children of the nodes which are at Level 1 will be at Level 2 and so on... In
simple words, in a tree each step from top to bottom is called as a Level and the Level count
starts with '0' and incremented by one at each level (Step).

10. Height
In a tree data structure, the total number of edges from leaf node to a particular node in the
longest path is called as HEIGHT of that Node. In a tree, height of the root node is said to be
height of the tree. In a tree, height of all leaf nodes is '0'.

5
11. Depth
In a tree data structure, the total number of edges from root node to a particular node is called as
DEPTH of that Node. In a tree, the total number of edges from root node to a leaf node in the
longest path is said to be Depth of the tree. In simple words, the highest depth of any leaf node
in a tree is said to be depth of that tree. In a tree, depth of the root node is '0'.

12. Path
In a tree data structure, the sequence of Nodes and Edges from one node to another node is called
as PATH between that two Nodes. Length of a Path is total number of nodes in that path. In
below example the path A - B - E - J has length 4.

13. SubTree
In a tree data structure, each child from a node forms a subtree recursively. Every child node will
form a subtree on its parent node.

6
14. Forest-A forest is a set of disjoint trees

Ancestor and Descendent: If there is a path from node A to node B, then A is called an
ancestor of B and B is called a descendent of A.

 Binary Tree Data structure

• Binary tree is a special type of tree data structure in which every node can have a
maximum of 2 children. One is known as left child and the other is known as right child.
• In a binary tree, every node can have either 0 children or 1child or 2 children but not
more than 2 children.

• Example

The maximum number of nodes at any level is 2n.

7
Properties of Binary Trees:

Some of the important properties of a binary tree are as follows:

1. If h =height of a binary tree, then

a. Maximum number of leafs =2h

b. Maximum number of nodes =2h+1-1

2. If a binary tree contains m nodes at level l, it contains at most2mnodes at level l +1.

3. Since a binary tree can contain at most one node at level 0(the root),it can contain at most2 l
node at level l.

4. The total number of edges in a full binary tree with n node is n-1.

There are different types of binary trees and they are...

[Link] Binary Tree: A binary tree is unlabeled if its nodes are not assigned any label.

Example: Consider we want to draw all the binary trees possible with 3 unlabeled nodes. Using the above
formula, we have-
Number of binary trees possible with 3 unlabeled nodes
=2x3C3/ (3+1)
=6C3/ 4
=5

8
 Thus,
 With 3 unlabeled nodes,5 unlabeled binary trees are possible.
 These unlabeled binary trees are as follows-

[Link] Binary Tree: A binary tree is labeled if all its nodes are assigned a label.

Example: Consider we want to draw all the binary trees possible with 3 labeled nodes. Using the above
formula, we have-
Number of binary trees possible with 3 labeled nodes
={ 2x3C3/ (3 +1) }x 3!
={ 6C3/4 } x 6
=5 x 6
=30
Thus,
 With 3 labeled nodes, 30 labeled binary trees are possible.
9
 Each unlabeled structure gives rise to 3!=6 different labeled structures.

[Link] of Binary Trees-

Binary trees can be of the following types-

1. Rooted Binary Tree-

A rooted binary tree is a binary tree that satisfies the following 2 properties-
 It has a root node.
 Each node has at most2 children.

10
 2. Full/Strictly Binary Tree-

 A binary tree in which every node has either 0 or 2 children is called as a Full binary tree.
 Full binary tree is also called as Strictly binary tree or Proper Binary Tree or 2-Tree

Here,
 First binary tree is not a full binary tree.
 This is because node C has only 1 child.

3. Complete/Perfect Binary Tree-

A complete binary tree is a binary tree that satisfies the following 2 properties-
 Every internal node has exactly 2 children.
 All the leaf nodes are at the same level.
Complete binary tree is also called as Perfect binary tree.

11
 Here,
 First binary tree is not a complete binary tree.
 This is because all the leaf nodes are not at the same level.

4. Almost Complete Binary Tree-

An almost complete binary tree is a binary tree that satisfies the following2 properties-
 All the levels are completely filled except possibly the last level.
 The last level must be strictly filled from left to right.

Here,
 First binary tree is not an almost complete binary tree.
 This is because the last level is not filled from left to right.

5. Skewed Binary Tree-

A skewed binary tree is a binary tree that satisfies the following 2 properties-
 All the nodes except one node has one and only one child.
 The remaining node has no child.
OR
A skewed binary tree is a binary tree of n nodes such that its depth is (n-1).

Binary Tree Traversals

When we wanted to display a binary tree, we need to follow some order in which all the nodes of
that binary tree must be displayed. In any binary tree, displaying order of nodes depends on the
traversal method.
Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.

Tree Traversal refers to the process of visiting each node in a tree data structure exactly

12
 once.

Various tree traversal techniques are-

[Link] First Traversal: Following three traversal techniques fall under Depth First Traversal-
1. Pre-Order Traversal
2. In-Order Traversal
3. Post-Order Traversal

1. Pre-order Traversal-
Algorithm-
1. Visit the root
2. Traverse the left subtree i.e. call Pre-order (left sub tree)
3. Traverse the right subtree i.e. call Pre-order (right subtree)
Root→Left→Right
Consider the following example-

13
Preorder Traversal Shortcut
Traverse the entire tree starting from the root node keeping yourself to the left.

Applications-
 Pre-order traversal is used to get prefix expression of an expression tree.
 Pre-order traversal is used to create a copy of the tree.

2. In-order Traversal-
Algorithm-
1. Traverse the left subtree i.e. call In-order(left subtree)
2. Visit the root
3. Traverse the right subtree [Link] In-order (right subtree)
Left→Root→Right

Example- Consider the following example-

14
In-order Traversal Shortcut
Keep a plane mirror horizontally at the bottom of the tree and take the projection of all the nodes.

Application-
 In-order traversal is used to get infix expression of an expression tree.

3. Post-order Traversal-
Algorithm
1. Traverse the left sub tree i.e. call Post- order(left sub tree)
2. Traverse the right subtree i.e. call Post order (right subtree)
3. Visit the root
Left→Right→Roo

Example-

15
Consider the following example-

Post-order Traversal Shortcut

Pluck all the left most leaf nodes one by one.

Applications-
 Post order traversal is used to get postfix expression of an expression tree.
 Post-order traversal is used to delete the tree.
 This is because it deletes the children first and then it deletes the parent.

[Link] First Traversal:

 Breadth First Traversal of a tree prints all the nodes of a tree level by level.
 Breadth First Traversal is also called as Level Order Traversal.
Example-

Application-
16
 Level order traversal is used to print the data in the same order as stored in the array
representation of a complete binary tree.
Consider the following binary tree...

In-Order Traversal for above example of binary tree is

I -D -J-B-F-A-G -K-C-H
Pre-Order Traversal for above example binary tree is

A-B-D -I -J-F-C-G -K-H

Post-Order Traversal for above example binary tree is
I -J-D -F-B-K-G -H-C–A

Building Binary Tree from Traversal Pairs:

Some times it is required to construct a binary tree if its traversals are known. From
a single traversal it is not possible to construct unique binary tree. However any of
the two traversals are given then the corresponding tree can be drawn uniquely:
• In order and pre order
• In order and post order
• In order and level order

The basic principle for formulation is as follows:

If the preorder traversal is given, then the first node is the root node. If the post
order traversal is given then the last node is the root node. Once the root node is
identified, all the nodes in the left sub-trees and right sub-trees of the root node can
be identified using inorder.

Same technique can be applied repeatedly to form sub-trees. It can be noted that,
for the purpose mentioned, two traversal are essential out of which one should be
inorder traversal and another preorder or postorder; alternatively, given preorder
and postorder traversals, binary tree cannot be obtained uniquely.

Example1:

Construct a binary tree from a given preorder and inorder sequence:

Preorder: A B D G C E H I F Inorder: D G B A H E I C F

17
18
Example2:
Let us consider the below traversals:
Inorder sequence: D B E A F C
Preorder sequence: ABDEC F

19
Example3:
Construct a binary tree from a given postorder and inorder sequence:

Inorder: DGBAHEICF Postorder: GDBHIEFCA

20
Example 4:

Construct a binary tree from a given preorder and inorder sequence:

Inorder: n1 n2 n3 n4 n5 n6 n7 n8 n9 Preorder:n6 n2 n1 n4 n3 n5 n9

21
n7 n8

Example 5: Construct a binary tree from a given postorder and inorder sequence:
Inorder: n1 n2 n3 n4 n5 n6 n7 n8 n9
Postorder:n1 n3 n5 n4 n2 n8 n7 n9 n6 Solution:

The inorder and preorder traversal of a binary tree are dbeafcgandabdecfg, respectively. The
postorder traversal of the binary tree is:

(A) d ebf gc a

The post-order traversal of a binary search tree is given by 2,7,6,10,9,8,15,17,20,19, 16,

22
12. Then the pre-order traversal of this tree is:

Explanation: Since given tree is binary search tree, so inorder traversal will be always sorted order, i.e.,
2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20.
Now we can draw that binary search tree using given postorder and inorder traversal. Final tree will be:

12,8,6, 2,7, 9,10, 16,15,19,17, 20

23
 Tree Representations
A tree data structure can be represented in two methods. Those methods are as follows...

1. Array(Sequential)
2. Linked list Representation

1. Array(Sequential)representation of Binary Tree

Case1: index starting with 0

A B C D E F G H I
0 1 2 3 4 5 6 7 8

Let us consider that we have a tree T. let our tree T is a binary tree that us complete binary tree.
Then there is an efficient way of representing T in the memory called the sequential
representation or array representation of T. This representation uses only a linear array TREE as
follows:

If The root is stored in ‘i’th index

Left child would be stored at index(2*i)+1

Right child be stored at index (2*i)+2

Finding root/parent of corresponding node at floor((i-1)/2)

Example ‘D’ parent (3-1)/2=1,7,8

24
 Case 2: starting ‘i’ index is 1

A B C D E F G H I
1 2 3 4 5 6 7 8 9

If The root is stored in ‘i’th index

Left child would be stored at index(2*i)

Right child be stored at index (2*i)+1

Finding root/parent of corresponding node at floor((i)/2)

Example find G parent 7/2=3.5=3

2. Left Child-Right Sibling Representation

In this representation, we use list with one type of node which consists of three fields namely
Data field, Left child reference field and Right sibling reference field. Data field stores the actual
value of a node, left reference field stores the address of the left child and right reference field
stores the address of the right sibling node. Graphical representation of that node is as follows...

In this representation, every node's data field stores the actual value of that node. If that node has
left child, then left reference field stores the address of that left child node otherwise stores

NULL. If that node has right sibling, then right reference field stores the address of right sibling
node otherwise stores NULL.

25
A binary tree has the following time complexities...

Search Operation - O(n)

Insertion Operation-O(1)
DeletionOperation-O(n)

 BINARY SEARCH TREE

To enhance the performance of binary tree, we use special type of binary tree known as Binary
Search Tree. Binary search tree mainly focuses on the search operation in binary tree. Binary
search tree can be defined as follows...

Binary Search Tree is a binary tree in which every node contains only smaller values in its left
subtree and only larger values in its right subtree. (or)

A Binary search tree follows some order to arrange the elements. In a Binary search tree, the value of
left node must be smaller than the parent node, and the value of right node must be greater than the
parent node. This rule is applied recursively to the left and right subtrees of the root. Let's understand
the concept of Binary search tree with an example.

Creating a Binary Search Tree:

Now, let's see the creation of binary search tree using an example data
elements are 45, 15, 79, 90, 10, 55, 12, 20, 50

o First, we have to insert 45 into the tree as the root of the tree.
o Then, read the next element; if it is smaller than the root node, insert it as the
root of the left subtree, and move to the next element.
o Otherwise, if the element is larger than the root node, then insert it as the root
of the right subtree.

Now, let's see the process of creating the Binary search tree using the given
data element. The process of creating the BST is shown below –

26
Step 1 - Insert 45.

Step 2 - Insert 15.

As 15 is smaller than 45, so insert it as the root node of the left subtree.

Step 3 - Insert 79.

As 79 is greater than 45, so insert it as the root node of the right subtree.

Step 4 - Insert 90.

90 is greater than 45 and 79, so it will be inserted as the right subtree of 79.

Step 5 - Insert 10.

10 is smaller than 45 and 15, so it will be inserted as a left subtree of 15.

27
Step 6 - Insert 55.

55 is larger than 45 and smaller than 79, so it will be inserted as the left
subtree of 79.

Step 7 - Insert 12.

12 is smaller than 45 and 15 but greater than 10, so it will be inserted as the
right subtree of 10.

Step 8 - Insert 20.

20 is smaller than 45 but greater than 15, so it will be inserted as the right
subtree of 15.

Step 9 - Insert 50.

28
 50 is greater than 45 but smaller than 79 and 55. So, it will be inserted as a
left subtree of 55.

Now, the creation of binary search tree is completed. After that, let's move
towards the operations that can be performed on Binary search tree.

Operations on a Binary Search Tree

The following operations are performed on a binary search tree...

1. Search
2. Insertion
3. Deletion

Search Operation in BST

In a binary search tree, the search operation is performed with O(log n) time complexity. The
search operation is performed as follows...

 Step1-Read the search element from the user.

 Step2 -Compare the search element with the value of root node in the tree.
 Step3-If both are matched, then display "Given node is found!!!"and terminate the
function
 Step 4 -If both are not matched, then check whether search element is smaller or larger
than that node value.
 Step5- If search element is smaller, then continue the search process in left subtree.
 Step6- If search element is larger, then continue the search process in right subtree.
 Step7-Repeat the same until we find the exact element or until the search element is
compared with the leaf node
 Step 8 -If we reach to the node having the value equal to the search value then display
"Element is found" and terminate the function.
 Step 9 -If we reach to the leaf node and if it is also not matched with the search element,
then display "Element is not found" and terminate the function.

Insertion Operation in BST

In a binary search tree, the insertion operation is performed with O(log n)time complexity. In
binary search tree, new node is always inserted as a leaf node. The insertion operation is
performed as follows...
29
  Step1-Create a new Node with given value and set its left and right to NULL.
 Step2-Check whether tree is Empty.
 Step3- If the tree is Empty, then set root to newNode.
 Step4-If the tree is Not Empty, then check whether the value of new Node is smaller or
larger than the node (here it is root node).
 Step5-If newNode is smaller than orequal to the node then move to its left child. If
newNode is larger than the node then move to its right child.
 Step6-Repeat the above steps until we reach to the leaf node (i.e., reaches to NULL).
 Step7-After reaching the leaf node, insert the newNode as leftchild if the newNode is
smaller or equal to that leaf node or else insert it as right child.

Deletion Operation in BST

In a binary search tree, the deletion operation is performed with O(log n) time complexity. Deleting a
node from Binary search tree includes following three cases...
Case1:Deletinga Leaf node(A node with no children)
Case 2: Deleting a node with one child
Case3: Deleting a node with two children

Case 1: Deletinga leaf node

We use the following steps to delete a leaf node from BST...

 Step1-Find the node to be deleted using search operation

 Step2-Deletethe node using free function (If it is a leaf)and terminate the function.

Case2: Deleting a node with one child

We use the following steps to delete a node with one child from BST...

 Step1-Find the node to be deleted using search operation

 Step2- If it has only one child then create a link between its parent node and child node.
 Step3-Delete the node using free function and terminate the function.

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST...

 Step1-Find the node to be deleted using search operation

 Step2- If it has two children, then find the largest node in its left subtree (OR)
the smallest node in its right subtree.
 Step3 -Swap both deleting node and node which is found in the above step.
 Step4 -Then check whether deleting node came to case1 or case2 or else goto step 2
 Step5 - If it comes to case1, then delete using case1 logic.
 Step6-If it comes to case2, then delete using case2 logic.
 Step7-Repeat the same process until the node is deleted from the tree.
30
Example
Construct a Binary Search Tree by inserting the following sequence of numbers...

10,12,5,4,20,8,7,15and13
Above elements are inserted into a Binary Search Tree as follows...

31
// C program to insert a node in a Binary Search
Tree
#include <stdio.h>
#include <stdlib.h>

// Given Node
struct node {
int data;
struct node *left, *right;
};

// Function to create a new BST node

struct node* newNode(int item)
{
struct node* temp
= (struct node*)malloc(
sizeof(struct node));
temp->data = item;
32
 temp->left = temp->right = NULL;
return temp;
}

// Function to insert a new node with

// given key in BST
struct node* insert(struct node* node, int data)
{
// If the tree is empty, return a new node
if (node == NULL)
return newNode(data);

// Otherwise, recur down the tree

if (data < node->data) {
node->left = insert(node->left, data);
}
else if (data > node->data) {
node->right = insert(node->right, data);
}

// Return the node pointer

return node;
}

// Function to do inorder traversal of BST

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

// Driver Code
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80
*/
struct node* root = NULL;

// inserting value 50
root = insert(root, 50);
33
 // inserting value 30
insert(root, 30);

// inserting value 20
insert(root, 20);

// inserting value 40
insert(root, 40);

// inserting value 70
insert(root, 70);

// inserting value 60
insert(root, 60);

// inserting value 80
insert(root, 80);

// print the BST

inorder(root);

return 0;
}
OUTPUT:
20 30 40 50 60 70 80

Program for Binary Search Tree operations in C

#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left, *right;
};
// Create a node
struct node *newNode(int item) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;

34
}

// Inorder Traversal
void inorder(struct node *root) {
if (root != NULL) {
// Traverse left
inorder(root->left);
// Traverse root
printf("%d -> ", root->key);
// Traverse right
inorder(root->right);
}
}
// Insert a node
struct node *insert(struct node *node, int key) {
// Return a new node if the tree is empty
if (node == NULL) return newNode(key);
// Traverse to the right place and insert the node
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
// Find the inorder successor
struct node *minValueNode(struct node *node) {
struct node *current = node;
// Find the leftmost leaf
while (current && current->left != NULL)
current = current->left;
return current; }

35
// Deleting a node
struct node *deleteNode(struct node *root, int key) {
// Return if the tree is empty
if (root == NULL) return root;
// Find the node to be deleted
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// If the node is with only one child or no child
if (root->left == NULL) {
struct node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct node *temp = root->left;
free(root);
return temp;
}
// If the node has two children
struct node *temp = minValueNode(root->right);
// Place the inorder successor in position of the node to be deleted
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
int main() {
struct node *root = NULL;

36
 root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 7);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 4);
printf("Inorder traversal: ");
inorder(root);
printf("\nAfter deleting 10\n");
root = deleteNode(root, 10);
printf("Inorder traversal: ");
inorder(root);
}
OUTPUT:
In order traversal: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 14 ->
After deleting 10
In order traversal: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 14 ->

 AVL Tree Data structure

The AVL tree was introduced in the year 1962 by G.M. Adelson, Velsky and E.M. Landis.

AVL tree is a height 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 the height of left and right children of
every differs by either-1, 0 or +1.

In an AVL tree, every node maintains an extra information known as balance factor.
An AVL tree is defined as follows...

An AVL tree is a balanced binary search tree . In an AVL tree, balance factor of every node is

either-1,0 or +1.

37
Balance factor of a node is the difference between the heights of left and right subtrees of that
node.
The balance factor of an order is calculated either height of left sub tree-height of right

subtree(OR)height of right subtree - height of left subtree.

In the following explanation, we calculate as follows...

Balance factor=height Of Left Subtree – height Of Right Subtree

 If balance factor of any node is 1, it means that the left sub-tree is one level higher than the right
sub-tree.

 If balance factor of any node is 0, it means that the left sub-tree and right sub-tree contain equal
height.

 If balance factor of any node is -1, it means that the left sub-tree is one level lower than the right
sub-tree.

Example of AVL Tree:

The above tree is a binary search tree and every node is satisfying balance factor condition. So
this tree is said to be an AVL tree.

38
NOTE: Every AVL Tree is a binary search tree but every Binary Search Tree need not
be AVL tree.

Complexity
Algorithm Average case Worstcase

Space o(n) o(n)

Search o(log n) o(log n)

Insert o(log n) o(log n)

Delete o(log n) o(log n)

AVL Tree Rotations

In AVL tree, after performing operations like insertion and deletion we need to check the
balance factor of every node in the tree. If every node satisfies the balance factor condition then
we conclude the operation otherwise we must make it balanced. Whenever the tree becomes
imbalanced due to any operation we use rotation operations to make the tree is balanced.
Rotation operations are used to make the tree balanced.
Rotation is the process of moving nodes either to left or to right to make the tree balanced.

Depending upon the type of insertion, the Rotations are categorized into four categories.

SN Rotation Description

1 LL Rotation The new node is inserted to the left sub-tree of left sub-tree of critical
node A.

2 RR Rotation The new node is inserted to the right sub-tree of the right sub-tree of the
critical node A.

3 LR Rotation The new node is inserted to the right sub-tree of the left sub-tree of the
critical node A.

4 RL Rotation The new node is inserted to the left sub-tree of the right sub-tree of the
critical node A.

[Link] Right Rotation (LL Rotation)

The tree shown in following figure is an AVL Tree, however, we, need to insert an element into
the left of the left sub-tree of A. the tree can become unbalanced with the presence of the critical
node A.

39
The node whose balance factor doesn't lie between -1 and 1,is called critical node.

In order to rebalance the tree, LL rotation is performed as shown in the following diagram.

The node B becomes the root, with A and T3 as its left and right child. T1 and T2 becomes the
left and right sub-trees of A.

[Link] Left Rotation(RR Rotation)

If the node is inserted into the right of the right sub-tree of a node A and the tree becomes unbalanced
then, in that case, RR rotation will be performed as shown in the following diagram.

While the rotation, the node B becomes the root node of the tree. The critical node A will be
moved to its left and becomes the left child of B.

The sub-tree T3 becomes the right sub-tree of A. T1 and T2 becomes the left and right sub-tree
of node A.

40
[Link]-Right Rotation(LR Rotation)
LRrotationistobeperformedifthenewnodeisinsertedintotherightoftheleftsub-treeof node A.
In LR rotation, node C (as shown in the figure) becomes the root node of the tree, while the node
B and A becomes its left and right child respectively.

T1 and T2 becomes the left and right sub-tree of Node B respectively where as, T3 and T4 becomes the
left and right sub-tree of Node A.

[Link]-Left Rotation(RL Rotation)

RL rotations are to be performed if the new node is inserted into the left of right sub-tree of the
critical node A. Letusconsider,NodeBistherootoftherightsub-treeofthecriticalnode,Node C is the
root of the sub-tree in which the new node is inserted.

Let T1 be the left sub-tree of the critical nodeA,T2and T3 be the left and right sub-tree of Node
C respectively, sub-tree T4 be the right sub-tree of Node B.

Since, RL rotation is the mirror image of LR rotation. In this rotation, the node C becomes the
root node of the tree with A and B as its left and right children respectively. Sub-trees T1 and T2
41
becomes the left and right sub-trees of A whereas, T3 and T4 becomes the left and right sub-trees
of B. The process of RL rotation is shown in the following image.

Operations on an AVL Tree

The following operations are performed on AVL tree...

1. Insertion
2. Deletion
3. Search

[Link] Operation in AVL Tree

In an AVL tree, the insertion operation is performed with O(log n)time complexity. In AVL
Tree, new node is always inserted as a leaf node. The insertion operation is performed as
follows...

 Step 1- Insert the new element into the tree using Binary Search Tree insertion logic.
 Step2-Afterinsertion, check the Balance Factor of every node.
 Step3 - If the Balance Factor of every node is 0 or 1 or-1 then go for next operation.
 Step 4 -If the Balance Factor of any node is other than 0 or 1 or -1 then that tree is said
to be imbalanced. In this case, perform suitable Rotation to make it balanced and go for
next operation.

Example:Construct an AVL tree by inserting the following

elements in the given order.
63, 9, 19, 27, 18, 108, 99, 81

All the elements are inserted in order to maintain the order of binary search tree.

42
43
[Link] Operation in AVL Tree:
The deletion operation in AVL Tree is similar to deletion operation in BST. But after every
deletion operation we need to check with the Balance Factor condition. If the tree is balanced
after deletion go for next operation otherwise perform suitable rotation to make the tree
Balanced.

Deleting a node from an AVL tree is similar to that in a binary search tree. Deletion may disturb
the balance factor of an AVL tree and therefore the tree needs to be rebalanced in order to
maintain the AVL ness. For this purpose, we need to perform rotations. The two types of
rotations are L rotation and R rotation. Here, we will discuss R rotations. L rotations are the
mirror images of them.

If the node which is to be deleted is present in the left sub-tree of the critical node, then L
rotation needs to be applied elseif, the node which is to be deleted is present in the right sub-tree
of the critical node, the R rotation will be applied.

Let us consider that, A is the critical node and B is the root node of its left sub-tree. If node X,
present in the right sub-tree of A, is to be deleted, then there can be three different situations:

R0 rotation(Node B has balance factor 0)

If the node B has 0 balance factor, and the balance factor of node A disturbed upon deleting the
node X, then the tree will be rebalanced by rotating tree using R0 rotation.

The critical node A is moved to its right and the node B becomes the root of the tree with T1 as
its left sub-tree. The sub-trees T2 and T3 becomes the left and right sub-tree of the node A. the
process involved in R0 rotation is shown in the following image.

LL rotation

44
R1 Rotation(Node B has balance factor 1)
R1 Rotation is to be performed if the balance factor of Node B is 1. In R1 rotation, the critical
node A is moved to its right having sub-trees T2 and T3 as its left and right child respectively.T1
is to be placed as the left sub-tree of the node B.
The process involved in R1 rotation is shown in the following image.

LL Rotation

R-1 Rotation(Node B has balance factor-1)

Rotation is to be performed if the node B has balance factor -1. This case is treated in the
same way as LR rotation. In this case, the node C, which is the right child of node B,
becomes the root node of the tree with B and A as its left and right children respectively.

The sub-trees T1, T2 becomes the left and right sub-trees of B whereas, T3, T4 become the left
and right sub-trees of A. The process involved in R-1 rotation is shown in the following image.
LR Rotation

45
Similarly, L0, L1, L-1
[Link] Operation in AVL Tree
In an AVL tree, the search operation is performed with O(log n)time complexity. The search
operation in AVL tree is similar to search operation in Binary search tree. We use the following
steps to search an element in AVL tree...

 Step1-Read the search element from the user.

 Step2 -Compare the search element with the value of root node in the tree.
 Step3-If both are matched, then display "Given node is found!!!" and terminate the
function
 Step 4 -If both are not matched, then check whether search element is smaller or larger
than that node value.
 Step5- Ifsearchelementissmaller,thencontinuethesearchprocessinleftsubtree.
 Step6-Ifsearchelementislarger,thencontinuethesearchprocessinrightsubtree.
 Step7-Repeat the same until we find the exact element or until the search element is
compared with the leaf node.
 Step 8 -If we reach to the node having the value equal to the search value, then display
"Element is found" and terminate the function.
 Step 9 -If we reach to the leaf node and if it is also not matched with the search element,
then display "Element is not found" and terminate the function.

// AVL tree implementation in C

#include <stdio.h>

#include <stdlib.h>

// Create Node

struct Node {

int key;

struct Node *left;

struct Node *right;

int height;

};

int max(int a, int b);

// Calculate height

int height(struct Node *N) {

if (N == NULL)

return 0;
46
 return N->height;

int max(int a, int b) {

return (a > b) ? a : b;

// Create a node

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;

return (node);

// Right rotate

struct Node *rightRotate(struct Node *y) {

struct Node *x = y->left;

struct Node *T2 = x->right;

x->right = y;

y->left = T2;

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

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

return x;

// Left rotate

struct Node *leftRotate(struct Node *x) {

47
 struct Node *y = x->right;

struct Node *T2 = y->left;

y->left = x;

x->right = T2;

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

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

return y;

// Get the balance factor

int getBalance(struct Node *N) {

if (N == NULL)

return 0;

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

// Insert node

struct Node *insertNode(struct Node *node, int key) {

// Find the correct position to insertNode the node and insertNode it

if (node == NULL)

return (newNode(key));

if (key < node->key)

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

else if (key > node->key)

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

else

return node;

// Update the balance factor of each node and

// Balance the tree

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

height(node->right));

int balance = getBalance(node);

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

return rightRotate(node);

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

return leftRotate(node);

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

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

return rightRotate(node);

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

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

return leftRotate(node);

return node;

struct Node *minValueNode(struct Node *node) {

struct Node *current = node;

while (current->left != NULL)

current = current->left;

return current;

// Delete a nodes

49
struct Node *deleteNode(struct Node *root, int key) {

// Find the node and delete it

if (root == NULL)

return root;

if (key < root->key)

root->left = deleteNode(root->left, key);

else if (key > root->key)

root->right = deleteNode(root->right, key);

else {

if ((root->left == NULL) || (root->right == NULL)) {

struct Node *temp = root->left ? root->left : root->right;

if (temp == NULL) {

temp = root;

root = NULL;

} else

*root = *temp;

free(temp);

} else {

struct Node *temp = minValueNode(root->right);

root->key = temp->key;

root->right = deleteNode(root->right, temp->key);

if (root == NULL)

return root;

50
 // Update the balance factor of each node and

// balance the tree

root->height = 1 + max(height(root->left),

height(root->right));

int balance = getBalance(root);

if (balance > 1 && getBalance(root->left) >= 0)

return rightRotate(root);

if (balance > 1 && getBalance(root->left) < 0) {

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

return rightRotate(root);

if (balance < -1 && getBalance(root->right) <= 0)

return leftRotate(root);

if (balance < -1 && getBalance(root->right) > 0) {

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

return leftRotate(root);

return root;

// Print the tree

void printPreOrder(struct Node *root) {

if (root != NULL) {

printf("%d ", root->key);

printPreOrder(root->left);

printPreOrder(root->right);

51
int main() {

struct Node *root = NULL;

root = insertNode(root, 2);

root = insertNode(root, 1);

root = insertNode(root, 7);

root = insertNode(root, 4);

root = insertNode(root, 5);

root = insertNode(root, 3);

root = insertNode(root, 8);

printPreOrder(root);

root = deleteNode(root, 3);

printf("\nAfter deletion: ");

printPreOrder(root);

return 0;

OUTPUT:

4213758

After deletion: 4 2 1 7 5 8

52