Data Structures and Applications (CS202) Module 4

Module 4 (Trees)
Binary Trees- Properties of Binary trees, Array and linked Representation, Binary Tree Traversals
Inorder, Postorder, Preorder;
Binary Search Trees- Critique the concept of and examine the Insertion, Deletion, Traversal,
Searching operations.
Balanced Search Trees- AVL Trees- Examine the operations: Create, Insert, Delete, Rotate
Case Study- Red Black Trees
Text book:1
4.1 Trees: Terminology
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 non-linear data structure which organizes data in hierarchical fashion and the tree
structure follows a recursive pattern of organizing and storing data.

A tree is a non-linear data structure which contains a finite set of one or more nodes such that:
(1) There is a specially designated node called the root. (2) The remaining nodes are partitioned
into n ≥ 0 disjoint sets T1, …, Tn, where each of these sets is a tree. We call T1, …, Tn as the
subtrees of the root.
Every individual element is called as Node. Node in a tree data structure, stores the actual data
of that particular element and link to next element in hierarchical structure.

Example

1. Root
In a tree data structure, the first node is called as Root Node. Every tree must have root node.
We 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. Ex: ‘A’ in the above 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.
Ex: Line between two nodes.

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

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 1

Data Structures and Applications (CS202) Module 4

parent node. Parent node can also bedefined as "The node which has child / children".
Ex: A,B,C,E & G are parent nodes
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 anynumber of child nodes. In a tree, all the nodes except root
are child nodes. Ex: B & C are children of A, G & H are children of C and K child of G

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. Ex: B & C are
siblings, D, E and F are siblings, G & H are siblings, I & J are siblings

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. Ex: D,I,J,F,K AND H are leaf nodes

7. Internal Nodes
In a tree data structure, the node which has atleast one child is called as INTERNAL Node.
In simple words,an internal node is a node with atleast 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.
Ex: A,B,C,E & G

8. Degree of a node
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'. Ex: Degree of
B is 3, A is 2 and of F is 0. Degree of Tree is 3.

9. Level of a node
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).

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 2

Data Structures and Applications (CS202) Module 4

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.

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 [Link] 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 the 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.

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 3

Data Structures and Applications (CS202) Module 4

13. Sub Tree

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.

14. The ancestors of a node are all the nodes along the path from the root to that node.
Ex: ancestor of j is B & A
15. A forest is a set of n>=0 disjoint trees. If we remove the root of a tree we get a forest. For
example, in figure 1 if we remove A we get a forest with two trees.
Types of Trees
1) General Tree
2) Binary Tree
3) Threaded Binary Tree
4) Binary Search Tree
5) AVL Tree
6) Red Black Tree
7) Selection Tree
General Tree
A tree is called a general tree when there is no constraint imposed on the hierarchy of the tree. In
general tree, each node can have infinite number of children. This tree is the super set of all other
types of trees.
4.2 Binary Tree (Degree two tree)
In a general tree, every node can have arbitrary number of children. 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. A tree in which every node can have a
maximum of two children is called as Binary Tree. In a binary tree, every node can have either
0 children or 1 child or 2 children but not more than 2 children. Example

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 4

Data Structures and Applications (CS202) Module 4

Types of Binary Trees

1. Full / Strictly Binary Tree / Proper Binary Tree
In a binary tree, every node can have a maximum of two children. But in strictly binary tree,
every node should have exactly two children or none. That means every internal node must
have exactly two children. A strictly Binary Tree can be defined as follows...
A binary tree in which every node has either two or zero number of children is called Strictly
Binary Tree. Strictly binary tree is also called as Full Binary Tree or Proper Binary
Tree or 2-Tree.

Strictly binary tree data structure is used to represent mathematical expressions.

A Binary Expression Tree is - A special kind of binary tree in which:
1. Each leaf node contains a single operand
2. Each non-leaf node contains a single binary operator
3. The left and right subtrees of an operator node represent sub expressions that must be
evaluated before applying the operator at the root of the subtree.
2. Complete Binary Tree / Perfect Binary Tree
In a binary tree, every node can have a maximum of two children. But in strictly binary tree,
every node should have exactly two children or none and in complete binary tree all the nodes
must have exactly two children and at every level of complete binary tree there must be 2 level
number of nodes. For example at level 2 there must be 22 = 4 nodes and at level 3 there must
be 23 = 8 nodes.

A binary tree in which every internal node has exactly two children and all leaf nodes are
at same level is called Complete Binary Tree. Complete binary tree is also called as Perfect
Binary Tree.

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 5

Data Structures and Applications (CS202) Module 4

3. Almost complete Binary Tree

It is complete binary tree but completeness property is not followed in last level. In the above
tree absence of leaf nodes L, M, N, O and P indicates its almost complete binary tree.
4. Right Skewed BT
Here the tree grows only towards right. The height of the right sub tree is greater than the
left sub tree.

5. Left Skewed BT
Here the tree grows only towards left. The height of the left subtree is greater than the right sub
tree.

[Link] Binary Tree

A binary tree can be converted into Full Binary tree by adding dummy nodes to existing
nodes wherever required. The full binary tree obtained by adding dummy nodes to a binary
tree is called as Extended BinaryTree.
In above figure, a normal binary tree is converted into full binary tree by adding dummy nodes
(In pink colour).

7. Binary Search Tree (BST)

BST is a binary tree with a difference that for any node x, data of left subtree <= data(x) and data of
rightsubtree > data(x). The above condition should be satisfied by all the nodes.

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 6

Data Structures and Applications (CS202) Module 4

4.3 Binary Tree Representations

A binary tree data structure is represented using two methods. Those methods are as follows...
1. Array Representation
2. Linked List Representation
Consider the following binary tree...

1. Array Representation (static)

In array representation of binary tree, we use a one-dimensional array (1-D Array) to represent
a binary tree. Consider the above example of binary tree and it is represented as follows...

sum=20 + 21 + 22 + ...........................................+ 2i
First term=a=20=1
Common ratio=2
N=number of terms=i+1(since the power of 2 starts from 0 to i)
Sum=20(2i+1-1)/2-1
Sum=1*(2i+1-1)/1
Sum= 2i+1-1

To represent a binary tree of depth 'i' using array representation, we need one dimensional
array with a maximum size of 2i+1 - 1.
For any node with the position i (index of parent node is i), 2i + 1 gives the position of the left
child & 2i + 2 gives the position of the right child. For any node with a position i, its parent
node position is identified by using formula (i-1) / 2.
If i is the position of the left child i+1 gives the position of right child.

Advantages of array representation

• Faster access
• Easy for implementation
• Good for complete binary trees
Disadvantages

• Wastes memory for skewed trees

• Implementation of operations requires rearranging(shifting)of array elements

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 7

Data Structures and Applications (CS202) Module 4

2. Linked List Representation (dynamic)

The linked notation uses a doubly linked list to represent a binary tree. In a doubly linked list,
every node consists of three fields. First field for storing left child address, second for storing
actual data and third for storing right child address. In this linked list representation, a node
has the following structure...

The above example of binary tree represented using Linked list representation is shown as
follows...

4.4 Binary Tree Traversals

Tree traversal is a method of visiting the nodes of a tree in a particular order. The tree
nodes are visited exactly once and displayed as they are visited.
Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.
There are five types of binary tree traversals.
1. In - Order Traversal
2. Pre - Order Traversal
3. Post - Order Traversal
4. Iterative In-Order Traversal
5. Level Order Traversal
Consider the following binary tree...

1. In - Order Traversal ( left child - root – right child )

In In-Order traversal, the root node is visited between left child and right child. In this traversal,

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 8

Data Structures and Applications (CS202) Module 4

the left childnode is visited first, then the root node is visited and later we go for visiting right
child node. This in-order traversal is applicable for every root node of all subtrees in the tree.
This is performed recursively for all nodes in the tree.
In-Order Traversal for above example of binary tree is : I - D - J - B - F - A - G - K - C – H
void inorder(struct node *root)
{ struct node
if(root!=NULL) {
{ int data;
inorder(root->left); struct node *left, *right;
printf("%d ",root->data); };
inorder(root->right);
}
}

2. Pre - Order Traversal ( root – left child – right child )

In Pre-Order traversal, the root node is visited before left child and right child nodes. In this
traversal, the root node is visited first, then its left child and later its right child. This pre-order
traversal is applicable for every root node of all subtrees in the tree.

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

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

3. Post - Order Traversal ( left child – right child - root)

In Post-Order traversal, the root node is visited after left child and right child. In this traversal,
left child nodeis visited first, then its right child and then its root node. This is recursively
performed until the right most node is visited.

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

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

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 9

Data Structures and Applications (CS202) Module 4

}
}
4. Iterative Inorder Traversal
Traversal techniques using recursion consumes system stack space. The stack space used may
not be acceptable for unbalanced trees of trees of larger heights. In such cases, iterative
traversal can be implemented by simulating stack space with the help of an array. Another
solution would be to use threaded binary trees during traversal.
5. Level Order Traversal

• Level order traversal is a method of traversing the nodes of a tree level by level as in
breadth first traversal.

• Level order traversal uses queue thus avoiding stack space usage.

• Here the nodes are numbered starting with the root on level zero continuing with
nodes on level1, 2, 3…..

• The nodes at any level is numbered from left to right

• Visiting the nodes using the ordering of levels is called level order traversal

• Queue uses FIFO principle

The level order traversal of the above tree is F B G A D I C E H

4.5 Building Binary Tree from Traversal Pairs:
Sometimes 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
The basic principle for formulation is as follows:
If the preorder traversal is given, then the first node is the root node. If the postorder 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, two traversals are essential out of which one should be inorder traversal
and another preorder or postorder; alternatively, given preorder and postorder traversals,

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 10

Data Structures and Applications (CS202) Module 4

binary tree cannot be obtained uniquely.

Reconstructing binary tree from In-order and Pre-order traversal
Consider the following traversals of the tree.
Inorder = {4, 2, 5, 1, 6, 3, 7} Preorder = {1, 2, 4, 5, 3, 6, 7}
Steps of construction:
First element in Preorder will be the root of the tree, here its 1. Now search the element 1 in
inorder[], say we find it at position i, once we find it, make note of elements which are left to i
(this will construct the left subtree) and elements which are right to i (this will construct the
right subtree). Same technique can be applied repeatedly to form sub-trees.

Example 2:
Construct a binary tree from a given preorder and inorder sequence:
Pre-order: A B D G C E H I F
In-order: D G B A H E I C F
Solution:
Making the nodes according to the preorder sequence and the child nodes according to the
inorder sequence,

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 11

Data Structures and Applications (CS202) Module 4

4.6 Properties of Binary Tree

1. The Maximum number of nodes on level i of a Binary tree is 2i-1, i>=1 (Consider root as
level 1)
The Proof by induction on i:
Induction base: Root is the only node on level i = 1.
 Hence max no of nodes on level i =1, 2i-1= 20=1
Induction Hypothesis:
 Let i be an arbitrary positive integer > 1
 Assume that max no of nodes on level i-1 is 2i-1-1=2i-2
Induction Step:
 We know that max no of nodes on level i-1 is 2 i-2 by induction hypothesis
 We know that each node in a Binary Tree has maximum degree 2.
 Max no of nodes on level i = twice the max no of nodes on level i-1 i.e 2*2 i-2
= 2i-2+1 =2i-1. Hence the proof.
2. Prove that maximum number of nodes in a Binary Tree of depth k is 2k – 1, k>=1
Total no of nodes = 20 + 21 + 22 + .............. + 2i

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 12

Data Structures and Applications (CS202) Module 4

sum=20 + 21 + 22 + .......................................... + 2i
First term=a=20=1
Common ratio=2
N=number of terms=i+1(since the power of 2 starts from 0 to i)
Sum=20(2i+1-1)/2-1
Sum=1*(2i+1-1)/1
Sum= 2i+1-1

The above sequence is in geometric progression

= 1 * (2 i+1 - 1) / (2 – 1)
= 2 i+1 - 1
= 2k – 1 (where i+1 = k = depth of tree)
=> max no of nodes in a BT of depth K = 2k - 1
3. [Relation between number of leaf nodes and degree-2 nodes] For any non-empty
Binary Tree T, if N0 is the no of leaf nodes and N2 no of nodes of degree 2 then N0 = N2
+1
Proof: Let N1 be the no of nodes of degree 1 and N be the total no of nodes
Since all nodes in T are atmost of degree 2 we have
N = N0 + N1 + N2 (1)

If we count no of branches in a Binary Tree we see that every node except the root has
a branch leading into it. If B is the no of branches then
B=N-1 (i.e) N = B + 1
All branches stem from a node of degree one or two.
Therefore B = N1 + 2N2
 N=B+1
 N = N1 + 2N2 + 1 (2)
 from (1) and (2), we get
N0 + N1 + N2 = N1 + 2N2 + 1

N0 = N2 + 1
Hence the proof.

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 13

Data Structures and Applications (CS202) Module 4

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 14

Data Structures and Applications (CS202) Module 4

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 15

Data Structures and Applications (CS202) Module 4

4.7 Binary Search Tree

In a binary tree, every node can have maximum of two children but there is no order of nodes based on their
values. In binary tree, the elements are arranged as they arrive to the tree, from top to bottom and left to right.
To enhance the performance of binary tree, we use special type of binary tree known as Binary Search Tree.
Binary search tree mainly focus 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 sub tree
and only larger values in its right sub tree.

Example
The following tree is a Binary Search Tree. In this tree, left subtree of every node contains nodes with
smaller values and right subtree of every node contains larger values.

Every Binary Search Tree is a binary tree but all the Binary Trees need not to be binary search trees.

Example
Construct a Binary Search Tree by inserting the following sequence of numbers...

10, 12, 5, 4, 20, 8, 7, 15 and 13

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 1

Data Structures and Applications (CS202) Module 4

Operations on a Binary Search Tree

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

• Search

• Insertion

• Deletion

• Traversal
struct BST
{
int data;
struct BST *left;
struct BST *right;
};
typedef struct BST node;

Search Operation in BST

The searchoperation is performed as follows...
Step 1: Read the search element from the user
Step 2: Compare, the search element with the value of root node in the tree.
Step 3: If both are matching, then display "Given node found!!!" and terminate the function
Step 4: If both are not matching, then check whether search element is smaller or larger than that node value.
Step 5: If search element is smaller, then continue the search process in left subtree.
Step 6: If search element is larger, then continue the search process in right subtree.
Step 7: Repeat the same until we find exact element or we completed with a leaf node
Step 8: If we reach the node with search value, then display "Element is found" and terminate the function.
Step 9: If we reach a leaf node and it is also not matching, then display "Element not found" and terminate
the function.
void search(node *root, int key)
{
if (root == NULL)
{

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 2

Data Structures and Applications (CS202) Module 4

printf("key not found\n");

return;
}
if(root->data == key)
{
printf("key found\n");
return;
}
if (key<root->data)
search(root->left, key);
else
search(root->right, key);
}
Insertion Operation in BST
In binary search tree, new node is always inserted as a leaf node. The insertion operation is performed as
follows...
Step 1: Create a newNode with given value and set its left and right to NULL.
Step 2: Check whether tree is Empty.
Step 3: If the tree is Empty, then set root to newNode.
Step 4: If the tree is Not Empty, then check whether value of newNode is smaller or larger than the
node(here it is root node).
Step 5: If newNode is smaller than or equal to the node, then move to its left child. If newNode is larger
than the node, then move to its right child.
Step 6: Repeat the above step until we reach to a leaf node (i.e, reach to NULL).
Step 7: After reaching a leaf node, then insert the newNode as left child if newNode is smaller or equal
to that leaf else insert it as right child.
node* insert(node *root,int key)
{
if(root==NULL)
{
root=(node*)malloc(sizeof(node));
root->data=key;
root->left=NULL;
root->right=NULL;
return root;
}
if(key<root->data)
root->left=insert(root->left,key);
else if(key>root->data)
root->right=insert(root->right,key);
return root;
}
Deletion Operation in BST
Deleting a node from Binary search tree has following three cases...

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 3

Data Structures and Applications (CS202) Module 4

Case 1: Deleting a Leaf node (A node with no children)

Case 2: Deleting a node with one child
Case 3: Deleting a node with two children

Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST...
Step 1: Find the node to be deleted using search operation.
Step 2: Delete the node using free function (If it is a leaf) and terminate the function.

Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST...
Step 1: Find the node to be deleted using search operation
Step 2: If it has only one child, then create a link between its parent and child node.
Step 3: 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...
Step 1: Find the node to be deleted using search operation
Step 2: If it has two children, then find the largest node in its left subtree (OR) the smallest node in its
rightsubtree.
Step 3: Copy the data of node which was found in above step to the data of deleting node and again delete root-
>right=deletekey(root->right,temp->data);
Step 4: Then, check whether deleting node came to case 1 or case 2 else goto steps 2
Step 5: If it comes to case 1, then delete using case 1 logic.
Step 6: If it comes to case 2, then delete using case 2 logic.
Step 7: Repeat the same process until node is deleted from the tree.
node* deletekey(node *root,int key)
{
node *temp;
if(root==NULL)
{
printf("Key not found");
return NULL;
}
if(key<root->data)
root->left=deletekey(root->left,key);
else if(key>root->data)
root->right=deletekey(root->right,key);
else
{
if(root->left==NULL && root->right==NULL)
{
free(root);
return NULL;
}

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 4

Data Structures and Applications (CS202) Module 4

else if(root->left==NULL)
{
temp=root;
root=root->right;
free(temp);
return NULL;
}
else if(root->right==NULL)
{
temp=root;
root=root->left;
free(temp);
return NULL;
}
else
{
temp=findleft(root->right);
root->data=temp->data;
root->right=deletekey(root->right,temp->data);
}
}
return root;
}

node* findleft(node *temp)

{
while(temp->left!=NULL)
temp=temp->left;
return temp;
}
To find max and min value in BST

int minvalue(node *root)

{
node *temp=root;
while(temp->left!=NULL)
temp=temp->left;
return temp->data;
}
int maxvalue(node *root)
{
node *temp=root;
while(temp->right!=NULL)
temp=temp->right;
return temp->data;

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 5

Data Structures and Applications (CS202) Module 4

Counting the number of leaf nodes in BST

int leafnodes(node *root)
{
static int count=0;
if(root!=NULL)
{
leafnodes(root->left);
if(root->left==NULL && root->right==NULL)
count++;
leafnodes(root->right);
}
return count;
}
Traversal Operation in BST
Inorder Traversal Function
If root is not NULL, recursively call inorder on the left child.
Print root->data.
Recursively call inorder on the right child.
void inorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d\t",root->data);
inorder(root->right);
}
}
Preorder Traversal Function
If root is not NULL, Print root->data.
Recursively call preorder on the left child.
Recursively call preorder on the right child.
void preorder(node *root)
{
if(root!=NULL)
{
printf("%d\t",root->data);
preorder(root->left);
preorder(root->right);
}
}

Postorder Traversal Function

If root is not NULL, recursively call postorder on the left child.

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 6

Data Structures and Applications (CS202) Module 4

Recursively call postorder on the right child.

Print root->data.
void postorder(node *root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d\t",root->data);
}
}
Lab program -6
Title: Design, Develop and Implement a menu driven Program in C for traversing a tree and search a
given item.
Program:

#include<stdio.h>
#include<stdlib.h>
struct BST
{
int data;
struct BST *left;
struct BST *right;
};
typedef struct BST node;
node* insert(node *root,int key)
{
if(root==NULL)
{
root=(node*)malloc(sizeof(node));
root->data=key;
root->left=NULL;
root->right=NULL;
return root;
}
if(key<root->data)
root->left=insert(root->left,key);
else if(key>root->data)
root->right=insert(root->right,key);
return root;
}
void inorder(node *root)

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 7

Data Structures and Applications (CS202) Module 4

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

printf("%d\t",root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(node *root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d\t",root->data);
}
}
void search(node *root, int key)
{
if (root == NULL)
{
printf("key not found\n");
return;
}
if(root->data == key)
{
printf("key found\n");
return;
}
if (key<root->data)
search(root->left, key);
else
search(root->right, key);

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 8

Data Structures and Applications (CS202) Module 4

}
int main()
{
int n,i,key,choice;
node *root=NULL;
printf("enter the number of nodes\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("enter the element\n");
scanf("%d",&key);
root=insert(root,key);
}
while(1)
{
printf("enter 1 for inorder\n 2 for preorder\n 3 for postorder\n 4 for search\n 5 for exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\ninorder is \n");
inorder(root);
break;
case 2: printf("\npre order is \n");
preorder(root);
break;
case 3: printf("\npost order is \n");
postorder(root);
break;
case 4:printf("\nenter the element to be searched");
scanf("%d",&key);
search(root,key);
break;
case 5: exit(0);
default:printf("invalid choice\n");
}
}
}

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 9

Data Structures and Applications (CS202) Module 4

4.8 AVL Trees

AVL Tree is invented by GM Adelson - Velsky and EM Landis in 1962. The tree is named AVL in honour of
its inventors.

AVL Tree can be defined as height balanced binary search tree in which each node is associated with a
balance factor which is calculated by subtracting the height of its right sub-tree from that of its left sub-tree.

Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise, the tree will be
unbalanced and need to be balanced.

Balance Factor (k) = height (left-subtree(k)) - height (right-subtree(k))

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.

An AVL tree is given in the following figure. We can see that, balance factor associated with each node is in
between -1 and +1. therefore, it is an example of AVL tree.

Operations on AVL tree

Due to the fact that, AVL tree is also a binary search tree therefore, all the operations are performed in the
same way as they are performed in a binary search tree. Searching and traversing do not lead to the
violation in property of AVL tree. However, insertion and deletion are the operations which can violate
this property and therefore, they need to be revisited.

Operation Description

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 1

Data Structures and Applications (CS202) Module 4

Traversing Same as Binary Search Tree

Search Same as Binary Search Tree

Insertion in AVL tree is performed in the same way as it is performed in a binary search tree.
Insertion However, it may lead to violation in the AVL tree property and therefore the tree may need
balancing. The tree can be balanced by applying rotations.

Deletion can also be performed in the same way as it is performed in a binary search tree.
Deletion Deletion may also disturb the balance of the tree therefore; various types of rotations are used to
rebalance the tree.
Why AVL Tree?
AVL tree controls the height of the binary search tree by not letting it to be skewed.

AVL Rotations
We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0, and 1. There are basically
four types of rotations which are as follows:

1. LL rotation: Inserted node is in the left subtree of left subtree of a node that became unbalanced due to
insertion.
2. RR rotation: Inserted node is in the right subtree of right subtree of a node that became unbalanced due to
insertion.
3. LR rotation: Inserted node is in the right subtree of left subtree of a node that became unbalanced due to
insertion.
4. RL rotation: Inserted node is in the left subtree of right subtree of a node that became unbalanced due to
insertion.

Where unbalanced node is the node whose balance Factor is other than -1, 0, 1.

The first two rotations LL and RR are single rotations and the next two rotations LR and RL are double
rotations. For a tree to be unbalanced, minimum height must be at least 2, Let us understand each rotation.
1. RR Rotation
When BST becomes unbalanced, due to a node is inserted into the right subtree of the right subtree of A, then
we perform RR rotation, RR rotation is an anticlockwise rotation, which is applied on the edge below a node
having balance factor -2

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 2

Data Structures and Applications (CS202) Module 4

In above example Insert A,B,C: node A has balance factor -2 because a node C is inserted in the right subtree
of A right subtree. We perform the RR rotation on the edge below A.
2. LL Rotation
When BST becomes unbalanced, due to a node is inserted into the left subtree of the left subtree of C, then we
perform LL rotation, LL rotation is clockwise rotation, which is applied on the edge below a node having
balance factor 2.

In above example Insert C,B,A:, node C has balance factor 2 because a node A is inserted in the left subtree of
C left subtree. We perform the LL rotation on the edge below A.

3. LR Rotation
Double rotations are bit tougher than single rotation which has already explained above. LR rotation = RR
rotation + LL rotation, i.e., first RR rotation is performed on subtree and then LL rotation is performed.

Let us understand each and every step very clearly:

State Action

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 3

Data Structures and Applications (CS202) Module 4

Insert C,A,B:

Node B has been inserted into the right subtree of A the left subtree of C,
because of which C has become an unbalanced node having balance factor 2.
This case is L R rotation where: Inserted node is in the right subtree of left
subtree of C.

As LR rotation = RR + LL rotation, hence RR (anticlockwise) on subtree

rooted at A is performed first. By doing RR rotation, node A, has become the
left subtree of B.

After performing RR rotation, node C is still unbalanced, i.e., having balance

factor 2, as inserted node A is in the left of left of C

Now we perform LL clockwise rotation on tree, i.e. on node C. node C has

now become the right subtree of node B, A is left subtree of B

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 4

Data Structures and Applications (CS202) Module 4

Balance factor of each node is now either -1, 0, or 1, i.e. BST is balanced
now.

4. RL Rotation

R L rotation = LL rotation + RR rotation, i.e., first LL rotation is performed on subtree and then RR rotation is
performed.

State Action

Insert A,C,B:

A node B has been inserted into the left subtree of C the right subtree of A,
because of which A has become an unbalanced node having balance factor
- 2. This case is RL rotation where: Inserted node is in the left subtree of
right subtree of A

As RL rotation = LL rotation + RR rotation, hence, LL (clockwise) on

subtree rooted at C is performed first. By doing RR rotation, node C has
become the right subtree of B.

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 5

Data Structures and Applications (CS202) Module 4

After performing LL rotation, node A is still unbalanced, i.e. having

balance factor -2, which is because of the right-subtree of the right-subtree
node A.

Now we perform RR rotation (anticlockwise rotation) on tree, i.e. on node

A. node C has now become the right subtree of node B, and node A has
become the left subtree of B.

Balance factor of each node is now either -1, 0, or 1, i.e., BST is balanced
now.

Q: Construct an AVL tree having the following elements: H, I, J, B, A, E, C, F, D

1. Insert H, I, J

On inserting the above elements, especially in the case of H, the BST becomes unbalanced as the Balance
Factor of H is -2. Since the BST is right-skewed, we will perform RR Rotation on node H.

The resultant balance tree is:

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 6

Data Structures and Applications (CS202) Module 4

2. Insert B, A

On inserting the above elements, especially in case of A, the BST becomes unbalanced as the Balance
Factor of H and I is 2, we consider the first node from the last inserted node i.e. H. Since the BST from H
is left-skewed, we will perform LL Rotation on node H.

The resultant balance tree is:

3. Insert E

On inserting E, BST becomes unbalanced as the Balance Factor of I is 2, since if we travel from E to I we
find that it is inserted in the left subtree of right subtree of I, we will perform LR Rotation on node I. LR
= RR + LL rotation

3 a) We first perform RR rotation on node B

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 7

Data Structures and Applications (CS202) Module 4

The resultant tree after RR rotation is:

3b) We first perform LL rotation on the node I

The resultant balanced tree after LL rotation is:

4. Insert C, F, D

On inserting C, F, D, BST becomes unbalanced as the Balance Factor of B and H is -2, since if we travel
from D to B we find that it is inserted in the right subtree of left subtree of B, we will perform RL
Rotation on node I. RL = LL + RR rotation.

4a) We first perform LL rotation on node E - The resultant tree after LL rotation is:

4b) We then perform RR rotation on node B

The resultant balanced tree after RR rotation is:

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 8

Data Structures and Applications (CS202) Module 4

Program - AVL Tree Implementation

#include <stdio.h>
#include <stdlib.h>
struct AVL
{
int data;
struct AVL *left;
struct AVL *right;
int height;
};
typedef struct AVL node;
int getHeight(node *n){
if(n==NULL)
return 0;
return n->height;
}
node *createNode(int key)
{
node* n = (node *) malloc(sizeof(node));
n->data = key;
n->left = NULL;
n->right = NULL;
n->height = 1;
return n;
}
int max (int a, int b)
{
return (a>b)?a:b;
}
int getBalanceFactor(node * n)
{
if(n==NULL)
{
return 0;
}
return getHeight(n->left) - getHeight(n->right);

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 9

Data Structures and Applications (CS202) Module 4

}
node* leftRotate(node* y) //LL Rotation
{
node* x = y->left;
node* t2 = x->right;
x->right = y;
y->left = t2;
y->height = max(getHeight(y->right), getHeight(y->left)) + 1;
x->height = max(getHeight(x->right), getHeight(x->left)) + 1;
return x;
}
node* rightRotate(node* x) //RR Rotation
{
node* y = x->right;
node* t2 = y->left;
y->left = x;
x->right = t2;
x->height = max(getHeight(x->right), getHeight(x->left)) + 1;
y->height = max(getHeight(y->right), getHeight(y->left)) + 1;
return y;
}
node *insert(node* root, int key)
{
if (root == NULL)
return createNode(key);
if (key < root->data)
root->left = insert(root->left, key);
else if (key > root->data)
root->right = insert(root->right, key);
root->height = 1 + max(getHeight(root->left), getHeight(root->right));
int bf = getBalanceFactor(root);
// Left Left Case
if(bf>1 && key < root->left->data)
{
return leftRotate(root);
}
// Right Right Case
if(bf<-1 && key > root->right->data)
{
return rightRotate(root);
}
// Left Right Case

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 10

Data Structures and Applications (CS202) Module 4

if(bf>1 && key > root->left->data)

{
root->left = rightRotate(root->left);
return leftRotate(root);
}
// Right Left Case
if(bf<-1 && key < root->right->data)
{
root->right = leftRotate(root->right);
return rightRotate(root);
}
return root;
}
void printtree(node *root, int space,int n)
{
int i;
if (root != NULL)
{
space +=n; // The variable space is incremented by n, the indentation level for the next level of nodes
printtree(root->right, space,n);
printf("\n");
for (i =n; i < space; i++)
printf(" ");
printf("%d\n", root->data);
printtree(root->left, space,n);
}
}
int main()
{
node * root = NULL;
int n,i,key;
printf("enter the number of nodes\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("enter the key\n");
scanf("%d",&key);
root = insert(root, key);
}
printtree(root, 0, n) ;
return 0;
}

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 11

Data Structures and Applications (CS202) Module 4

Program - AVL Tree Deletion Implementation

#include <stdio.h>
#include <stdlib.h>
struct AVL
{
int data;
struct AVL *left;
struct AVL *right;
int height;
};
typedef struct AVL node;
int getHeight(node *n){
if(n==NULL)
return 0;
return n->height;
}
int max (int a, int b)
{
return (a>b)?a:b;
}
int getBalanceFactor(node * n)
{
if(n==NULL)
{
return 0;
}
return getHeight(n->left) - getHeight(n->right);
}
node* leftRotate(node* y) //LL Rotation
{
node* x = y->left;
node* t2 = x->right;
x->right = y;
y->left = t2;
x->height = max(getHeight(x->right), getHeight(x->left)) + 1;
y->height = max(getHeight(y->right), getHeight(y->left)) + 1;
return x;
}
node* rightRotate(node* x) //RR Rotation
{
node* y = x->right;

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 12

Data Structures and Applications (CS202) Module 4

node* t2 = y->left;
y->left = x;
x->right = t2;
x->height = max(getHeight(x->right), getHeight(x->left)) + 1;
y->height = max(getHeight(y->right), getHeight(y->left)) + 1;
return y;
}
node* findleft(node *temp)
{
while(temp->left!=NULL)
temp=temp->left;
return temp;
}
node* deletekey(node *root,int key)
{
node *temp;
if(root==NULL)
{
printf("Key not found");
return NULL;
}
if(key<root->data)
root->left=deletekey(root->left,key);
else if(key>root->data)
root->right=deletekey(root->right,key);
else
{
if(root->left==NULL && root->right==NULL)
{
free(root);
return NULL;
}
else if(root->left==NULL)
{
temp=root;
root=root->right;
free(temp);
return NULL;
}
else if(root->right==NULL)
{
temp=root;
root=root->left;
free(temp);
return NULL;

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 13

Data Structures and Applications (CS202) Module 4

}
else
{
temp=findleft(root->right);
root->data=temp->data;
root->right=deletekey(root->right,temp->data);
}
}
root->height = 1 + max(getHeight(root->left), getHeight(root->right));
int bf = getBalanceFactor(root);
// Left Left Case
if(bf>1 && key < root->left->data)
{
return leftRotate(root);
}
// Right Right Case
if(bf<-1 && key > root->right->data)
{
return rightRotate(root);
}
// Left Right Case
if(bf>1 && key > root->left->data)
{
root->left = rightRotate(root->left);
return leftRotate(root);
}
// Right Left Case
if(bf<-1 && key < root->right->data)
{
root->right = leftRotate(root->right);
return rightRotate(root);
}
return root;
}

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 14

Data Structures and Applications (CS202) Module 4

4.9 Red Black Trees Construction

The Red-Black tree is a binary search tree. In a binary search tree, the values of the nodes in the left sub tree
should be less than the value of the root node, and the values of the nodes in the right subtree should be greater
than the value of the root node.

Each node in the Red-black tree contains an extra bit that represents a color to ensure that the tree is balanced
during any operations performed on the tree like insertion, deletion, etc.

Let's understand the different scenarios of a binary search tree.

In the above tree, if we want to search the 80. We will first compare 80 with the root node. 80 is greater
than the root node, i.e., 10, so searching will be performed on the right subtree. Again, 80 is compared
with 15; 80 is greater than 15, so we move to the right of the 15, i.e., 20. Now, we reach the leaf node 20,
and 20 is not equal to 80. Therefore, it will show that the element is not found in the tree. After each
operation, the search is divided into half.

The above tree shows the right-skewed BST. If we want to search the 80 in the tree, we will compare 80
with all the nodes until we find the element or reach the leaf node.

In the above BST, the first one is the balanced BST, whereas the second one is the unbalanced BST. We
conclude from the above two binary search trees that a balanced tree takes less time than an unbalanced
tree for performing any operation on the tree.

Therefore, we need a balanced tree, and the Red-Black tree is a self-balanced binary search tree. Now, the
question arises that why do we require a Red-Black tree if AVL is also a height-balanced tree. The Red-
Black tree is used because the AVL tree requires many rotations when the tree is large, whereas the Red-
Black tree requires a maximum of fewer rotations to balance the tree. The main difference between

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 1

Data Structures and Applications (CS202) Module 4

the AVL tree and the Red-Black tree is that the AVL tree is strictly balanced, while the Red-Black tree is
not completely height-balanced. So, the AVL tree is more balanced than the Red-Black tree.

Insertion is easier in the AVL tree as the AVL tree is strictly balanced, whereas deletion and searching
are easier in the Red-Black tree as the Red-Black tree requires fewer rotations.

As the name suggests that the node is either colored in Red or Black color. Sometimes no rotation is
required, and only re-coloring is needed to balance the tree.

Properties of Red-Black tree

o It is a self-balancing Binary Search tree. Here, self-balancing means that it balances the tree itself by
either doing the rotations or recoloring the nodes.
o This tree data structure is named as a Red-Black tree as each node is either Red or Black in color. Every
node stores one extra information known as a bit that represents the color of the node. For example, 0 bit
denotes the black color while 1 bit denotes the red color of the node. Other information stored by the
node is similar to the binary tree, i.e., data part, left pointer and right pointer.
o In the Red-Black tree, the root node is always black in color.
o In a binary tree, we consider those nodes as the leaf which have no child. In contrast, in the Red-Black
tree, the nodes that have no child are considered the internal nodes and these nodes are connected to the
NIL nodes that are always black in color. The NIL nodes are the leaf nodes in the Red-Black tree.
o If the node is Red, then its children should be in Black color. In other words, we can say that there
should be no red-red parent-child relationship.
o Every path from a node to any of its descendant's NIL node should have same number of black nodes.

Is every AVL tree can be a Red-Black tree?

Yes, every AVL tree can be a Red-Black tree if we color each node either by Red or Black color. But every
Red-Black tree is not an AVL because the AVL tree is strictly height-balanced while the Red-Black tree is
not completely height-balanced.

Insertion in Red Black tree

The following are some rules used to create the Red-Black tree:

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 2

Data Structures and Applications (CS202) Module 4

1. If the tree is empty, then we create a new node as a root node with the color black.
2. If the tree is not empty, then we create a new node as a leaf node with a color red.
3. If the parent of a new node is black, then exit.
4. If the parent of a new node is Red, then we have to check the color of the parent's sibling of a new
node.
4a) If the color is Black or no sibling, then we perform rotations and recoloring.
4b) If the color is Red then we recolor the node. We will also check whether the parents' parent of a new
node is the root node or not; if it is not a root node, we will recolor and recheck the node.

Let's understand the insertion in the Red-Black tree.

10, 18, 7, 15, 16, 30, 25

Step 1: Initially, the tree is empty, so we create a new node having value 10. This is the first node of the
tree, so it would be the root node of the tree. As we already discussed, that root node must be black in
color, which is shown below:

Step 2: The next node is 18. As 18 is greater than 10 so it will come at the right of 10 as shown below.

We know the second rule of the Red Black tree that if the tree is not empty then the newly created node
will have the Red color. Therefore, node 18 has a Red color, as shown in the below figure:

Now we verify the third rule of the Red-Black tree, i.e., the parent of the new node is black or not. In the
above figure, the parent of the node is black in color; therefore, it is a Red-Black tree.

Step 3: Now, we create the new node having value 7 with Red color. As 7 is less than 10, so it will come
at the left of 10 as shown below.

Now we verify the third rule of the Red-Black tree, i.e., the parent of the new node is black or not. As we
can observe, the parent of the node 7 is black in color, and it obeys the Red-Black tree's properties.

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 3

Data Structures and Applications (CS202) Module 4

Step 4: The next element is 15, and 15 is greater than 10, but less than 18, so the new node will be
created at the left of node 18. The node 15 would be Red in color as the tree is not empty.

The above tree violates the property of the Red-Black tree as it has Red-red parent-child relationship.
Now we have to apply some rule to make a Red-Black tree. The rule 4 says that if the new node's parent
is Red, then we have to check the color of the parent's sibling of a new node. The new node is node 15;
the parent of the new node is node 18 and the sibling of the parent node is node 7. As the color of the
parent's sibling is Red in color, so we apply the rule 4b. The rule 4b says that we have to recolor both the
parent and parent's sibling node. So, both the nodes, i.e., 7 and 18, would be recolored as shown in the
below figure.

We also have to check whether the parent's parent of the new node is the root node or not. As we can
observe in the above figure, the parent's parent of a new node is the root node, so we do not need to
recolor it.

Step 5: The next element is 16. As 16 is greater than 10 but less than 18 and greater than 15, so node 16
will come at the right of node 15. The tree is not empty; node 16 would be Red in color, as shown in the
below figure:

In the above figure, we can observe that it violates the property of the parent-child relationship as it has a
red-red parent-child relationship. We have to apply some rules to make a Red-Black tree. Since the new
node's parent is Red color, and the parent of the new node has no sibling, so rule 4a will be applied. The
rule 4a says that some rotations and recoloring would be performed on the tree.

Since node 16 is right of node 15 and the parent of node 15 is node 18. Node 15 is the left of node 18.
Here we have an LR relationship, so we require to perform two rotations. First, we will perform right,
and then we will perform the left rotation. The right rotation would be performed on nodes 15 and 16,

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 4

Data Structures and Applications (CS202) Module 4

where node 16 will move upward, and node 15 will move downward. Once the right rotation is
performed, the tree looks like as shown in the below figure:

In the above figure, we can observe that there is an LL relationship. The above tree has a Red-red
conflict, so we perform the left rotation. When we perform the left rotation, the median element would be
the root node. Once the left rotation is performed, node 16 would become the root node, and nodes 15
and 18 would be the left child and right child, respectively, as shown in the below figure.

After rotation, node 16 and node 18 would be recolored; the color of node 16 is red, so it will change to
black, and the color of node 18 is black, so it will change to a red color as shown in the below figure:

Step 6: The next element is 30. Node 30 is inserted at the right of node 18. As the tree is not empty, so
the color of node 30 would be red.

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 5

Data Structures and Applications (CS202) Module 4

The color of the parent and parent's sibling of a new node is Red, so rule 4b is applied. In rule 4b, we
have to do only recoloring, i.e., no rotations are required. The color of both the parent (node 18) and
parent's sibling (node 15) would become black, as shown in the below image.

We also have to check the parent's parent of the new node, whether it is a root node or not. The parent's
parent of the new node, i.e., node 30 is node 16 and node 16 is not a root node, so we will recolor the
node 16 and changes to the Red color. The parent of node 16 is node 10, and it is not in Red color, so
there is no Red-red conflict.

Step 7: The next element is 25, which we have to insert in a tree. Since 25 is greater than 10, 16, 18 but
less than 30; so, it will come at the left of node 30. As the tree is not empty, node 25 would be in Red
color. Here Red-red conflict occurs as the parent of the newly created is Red color.

Since there is no parent's sibling, so rule 4a is applied in which rotation, as well as recoloring, are
performed. First, we will perform rotations. As the newly created node is at the left of its parent and the

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 6

Data Structures and Applications (CS202) Module 4

parent node is at the right of its parent, so the RL relationship is formed. Firstly, the left rotation is
performed in which node 25 goes upwards, whereas node 30 goes downwards, as shown in the below
figure.

After the first rotation, there is an RR relationship, so right rotation is performed. After right rotation, the
median element, i.e., 25 would be the root node; node 30 would be at the right of 25 and node 18 would
be at the left of node 25.

Now recoloring would be performed on nodes 25 and 18; node 25 becomes black in color, and node 18
becomes red in color.

The above tree is a Red-Black tree as it follows all the Red-Black tree properties.

[Link] Devi, Dept. of CSE, CITech 2025-26 Page 7