Tree

A tree is a non-linear data structure and consists of a non-empty finite collection of

nodes and edges such that-

a) There is a distinguished node called the root of the tree.

b) The remaining nodes of the tree form an ordered collection of 0 or more
subtrees.

B C D

E F G H I

J K

Figure: Tree

A tree is used to represent hierarchical (parent-child) relationship amongst nodes.

Terminology used in tree

a) Root
First node in the hierarchical arrangement of nodes.
OR
Node with no predecessor
OR
Node with no parent

Ex: Node A

b) Parent

 Any node which has an edge directed downwards to the child node is

known as parent node.

 Each parent can have one or more child node.

Ex: Node B is the parent of nodes E and F.

c) Child

 Any node which has an edge directed upwards to the parent node is

known as child node.

 Each child node has a single parent node.

Ex: Nodes E and F are the child nodes of the node B.

d) Sibling
The nodes that have the same parent are known as siblings.

Ex: Nodes E and F are the sibling nodes.

e) Leaf node(External node or Terminal node)

A node with no successor
OR
A node that does not have any child node.

Ex: Nodes E,H,I,J and K are the leaf nodes.

f) Branch node(Internal node)

A node which has at least one child node.

Ex: Nodes A,B,C,D,F and G are internal nodes.

g) Level
The entire tree structure is levelled in such a way that the root node is always
at level 0.
Then its immediate children are at level 1 and their immediate children are at
level 2 and so on up to the terminal node.

h) Ancestor of a node
An ancestor of a node is any predecessor node on a path from the root to
that node.
Ex: Nodes A,C and G are ancestors of node K.

i) Descendent of a node
The immediate successor of the given node is known as a descendant of a
node.
Ex: K is the descendant of node G.

j) Path
It is a sequence of consecutive edges from the source node to the destination
node.
Ex: The path between A and J is given by node pairs (A,B),(B,F),(F,J).

k) Depth of a node
It is the length of the path from the root to the node.
Ex: Depth of G is 2(A-C-G).

l) Depth of a tree
It is the maximum depth among all the nodes in the tree.

m) Height of a node
It is the length of the path from that node to the deepest node.
Ex: Height of B is 2(B-F-J).

n) Height of a tree
It is the maximum height among all the nodes in the tree.
OR
It is the maximum level of any node in the tree.

Note: For a given tree, depth and height returns the same value but for
individual node, we may get different results.

o) Forest
Forest is a collection of n≥0 disjoint trees.
Ex: In the above tree, if we remove its root node then it becomes a forest
with 3 trees.
A tree can be used to represent the lines of responsibilities in a business as
shown in the figure.

President

Vice-President Vice-President
Division A Division B

Manager Manager Manager

Dept. A1 Dept. A2 Dept. B1

Clerk Clerk Clerk Clerk Clerk Clerk

We can use the above tree to determine the total salary paid to employees either

by division or department.

The total salary for the division A can be found by computing sum of the salary paid

in department A1 and A2 plus the salary of vice-president of division A.

Similarly, the total salary paid in department A1 is the sum of salary of the manager

of department A1 and of the 2 clerks.

Binary Tree

A tree is called binary tree if each node has at most 2 children. In other words, a

node can have 0,1 or 2 children. Thus, we can say that in a binary tree the
maximum degree (the no. of subtrees) of any node is at most 2. That means, there

may be a 0 degree node,1 degree node or 2 degree node.

We can visualize binary tree as consisting of a root and 2 binary trees, called the

left and right subtree of the root.

Root 3

1 4

Left Subtree Right Subtree

2

Types of Binary Tree

a) Strict Binary Tree

A binary tree is called strict binary tree if each node has exactly 0 or 2 children. In
other words, degree of each node in a strict binary tree is either 0 or 2.

Ex.

3 4

2 5

b) Full Binary Tree

A binary tree is called full binary tree if each node has exactly 2 children and
all leaf nodes are at the same level.

Ex.
1

2 3

4 5 6 5
 The no. of nodes n in a full binary tree are 2 h+1-1.
 The no. of leaf nodes in a full binary tree are 2 h.

c) Complete Binary Tree

A binary tree is said to be a Complete binary tree if all the levels are
completely filled except possibly the last level; and the last level has all the
keys towards left.

Ex.
1

2 3

4 5

 The no. of nodes n in a complete binary tree is between 2(minimum) and

2h+1-1(maximum).
 The no. of NULL links (wasted pointers) in a complete binary tree of n
nodes are n+1.

Representation of Binary Tree

There are two types of representation of binary tree-

(i) Array Representation

(ii) Linked List Representation

Array Representation

An array can be used to store the nodes of a binary tree. The root node is always at
index 0. Then in successive memory locations the left child and the right child are
stored.

Consider the following binary tree.

- *

A B C /
Fig: Binary Tree

The array representation of above binary tree is

0 1 2 3 4 5 6 7 8 9 10 11 12 13
14

+ - * A B C / D E

The following rules are used to decide the location of any node in the array-

(a) The root node is at index 0.

(b) For any node with index i
(i) Parent(i) = floor((i-1)/2)
(ii) Leftchild(i) = 2*i+1
(iii) Rightchild(i) = 2*i+2

Linked List Representation

In this representation, each node of linked list is divided into 3 parts as follows

*lchild data *rchild

Where

 data part contains the information

 *lchild contains the address of left children
 *rchild contains the address of right children

● + ●

● - ● ● * ●
A B C ● / ●

D E

Advantage of array representation of binary tree

(a) Node can be accessed directly with the help of index.
(b) Data are stored without pointer reference of successor or predecessor.
(c) This representation is very much useful where the language does not
support dynamic memory allocation

Disadvantages of array representation of binary tree

(a) Memory is wasted because it will be allocated for all the nodes. Absence
of node will lead to empty entry in array.
(b) As the array size is limited, enhancement of tree structure is restricted.
(c) Inefficiency in processing time during insertion or deletion of node
because considerable movement of up and down in array structure.

Traversal of Binary Tree

Traversing is a method of visiting each node of a tree exactly once in a
systematic order.

The various traversal techniques of a binary tree shown below-

(a) Pre-order Traversal (Root->Left->Right)

 Visit the root node (Root)
 Traverse the left subtree in pre-order (Left)
 Traverse the right subtree in pre-order (Right)

Preorder Traversal
Algorithm

PREORDER(root)

Step1: If root = NULL then

return
[End of if structure]
Step 2: [Display the data]

write root->data

Step 3: [Traverse the left subtree in pre-order]

PREORDER(root->left)

Step 4: [Traverse the right subtree in pre-order]

PREORDER(root->right)
Step 5: return

(b) Inorder Traversal (Left->Root->Right)

 Traverse the left subtree in in-order (Left)

 Visit the root node (Root)
 Traverse the right subtree in in-order (Right)

Inorder Traversal
Algorithm

INORDER(root)

Step1: If root = NULL then

return
[End of if structure]
Step 2: [Traverse the left subtree in in-order]

INORDER(root->left)

Step 3: [Display the data]

write root->data

Step 4: [Traverse the right subtree in in-order]

INORDER(root->right)
Step 5: return

(c) Postorder Traversal (Left->Right->Root)

 Traverse the left subtree in post-order (Left)

 Traverse the right subtree in post-order (Right)
 Visit the root node (Root)

Postorder Traversal
Algorithm

POSTORDER(root)

Step1: If root = NULL then

return
[End of if structure]
Step 2: [Traverse the left subtree in post-order]

POSTORDER(root->left)

Step 3: [Traverse the right subtree in post-order]

POSTORDER(root->right)

Step 4: [Display the data]

write root->data

Step 5: return

Consider the following example-

B C

D E F

Preorder Traversal: A B D E C F
Inorder Traversal: DBEACF

Postorder Traversal: D E B F C A

Q. Consider the following binary trees and find their preorder,inorder and postorder
traversal-

(i) (ii)
A A

B C B C

D E F D E F
G

H I G I

K
(iii) (iv) H
A A
J

B G B C

C
H D E F

J
D I
G

(v) (vi) K
A
E E FH

B
A D

C D E K H G

E F G H C B
Q. The following sequence gives the preorder and inorder traversal of the binary
tree-

Preorder : ABDGHCEFIKJ

Inorder : BGHDAECIKFJ

Draw the diagram of the tree.

Sol: From the preorder traversal, we come to know that A is the root node. From
inorder traversal, we find that the nodes B, G, H and D should come in the left
subtree of A and the nodes E, C, I, K, F and J should come in right subtree of A.

Step 1: Start with the root node.

Step 2: In the preorder traversal, next node is B. From inorder traversal, we find
that B should come on the left of A.

B
Step 3: Next node is D in preorder traversal. It should come on right of B.

Step 4: Next node is G in preorder traversal. It should come on left of D.

A

By Following the same process, we get the final binary tree-

B C

D E F

G J
I

H K
Q. The following sequence gives the postorder and inorder traversal of the binary
tree-

Postorder : HGDBEKIJFCA

Inorder : BGHDAECIKFJ

Draw the diagram of the tree.

Sol: From the postorder traversal, we come to know that A is the root node. From
inorder traversal, we find that the nodes B, G, H and D should come in the left
subtree of A and the nodes E, C, I, K, F and J should come in right subtree of A.

Step 1: Start with the root node.

A

Step 2: In the postorder traversal, next node is C. From inorder traversal, we find
that C should come on the right of A.

C
Step 3: Next node is F in postorder traversal. It should come on right of C.

F
Step 4: Next node is J in postorder traversal. It should come on right of F.

F
J

By Following the same process, we get the final binary tree-

B C

D E F
Binary Search Tree (B.S.T)
In binary search tree, all the left subtree elements should be less than the root data
and all the right subtree elements should be greater than or equal to root data.

This is called binary search tree property. This property should be satisfied at every
node in the tree.

 The left subtree of a node contains only those nodes with data less than
the root data.
 The right subtree of a node contains only those nodes with data greater
than or equal to the root data.

Both the left and right subtree must also be binary search tree.

Root

<root >=root

Ex.

7
3

4 9
1 6

Fig 1 Fig 2
2 5 2 7
The binary tree in Fig 1 is B.S.T while the binary tree in Fig 2 is not a B.S.T.

Insertion in Binary Search Tree

Q. Insert the following keys(data) in binary search tree-

60,25,50,75,33,66,15,44

Sol:

Step 1: We insert item = 60 as root node.

60

Step 2: Next item = 25. We compare 25 with root node 60 and find that 25 is less
than 60 so we insert in on left of 60.

60

25

Step 3: Next item = 50. We compare 50 with root node 60 and find that 50 is less
than 60. Again we compare 50 with 25 and find that 50 is greater than 25 so we
insert it on right of 25.

60

25

50
By following the same process, we get the final B.S.T-

60

25 75

15 50 66

33

44
Algorithm

INSERT(root,item)

Step1: [Insert a new node]

If root=NULL then
root = (struct node*)malloc(sizeof(struct node))
root->data = item
root->left = NULL
root->right = NULL
return root
[End of if structure]
Step 2: [Finding the position to insert]

If item<root->data then

set root->left = CALL INSERT(root->left,item)

else

set root->right = CALL INSERT(root->right,item)

[End of If structure]

Step 3: return root

Deletion in Binary Search Tree

It is very important to remember that once the node is deleted, the properties of
binary search tree are not violated i.e. elements in the left subtree should be lesser
and elements in the right subtree should be greater or equal to node data.

There are 3 cases to delete a node from binary search tree-

Case 1: Deleting a Node that has No Children

Delete 15
60
60

25 75
25 75

15 50 66
50 66

33
33

44
Case 2: Deleting a Node that has one Children

Delete 50

60 60

25 75 25 75

15 50 66 15 33 66

33 44

Case 3: Deleting a Node that has two Children

44
Delete 60

60 66

Replace 60 with its

25 75 25 66
inorder successor 75

15 50 66 15 50 66

33 66 33 66

Delete inorder successor 66

25 44 25 44 75
75

15 50 66 15 50

33 33
Algorithm

FINDSUCCESSOR(root)

Step1: If root=NULL then

return NULL
[End of if structure]
Step 2: If root->left=NULL then

return root

[End of if structure]

Step 3: return FINDSUCCESSOR(root->left)

Algorithm

DELETE(root,item)

Step1: If root=NULL then

write “Item not found”
return root
[End of if structure]
Step 2: If item<root->data then

set root->left = call DELETE(root->left,item)

else If item>root->data then

set root->right = call DELETE(root->right,item)

else

set temp = root

If temp->left=NULL and temp->right=NULL then

set root = NULL

free(temp)
else If temp->left=NULL then

set root = root->right

free(temp)

else If temp->right = NULL then

set root = root->left

free(temp)

else

set temp = call FINDSUCCESSOR(root->right)

set root->data = temp->data

set root->right = call DELETE(root->right,temp->data)

[End of If structure]

[End of If structure]

Step 3: return root

Algorithm

SEARCH(root,item)

Step1: If root=NULL then

return root
[End of if structure]
Step 3: If item=root->data then
return root
[End of if Structure]
Step 2: If item<root->data then

retrurn SEARCH(root->left,item)

[End of If structure]

Step 4: retrurn SEARCH(root->right,item)

/*A program to perform insertion, deletion, searching and traversal

operations on B.S.T(Binary Search Tree)*/

#include<stdio.h>
#include<stdlib.h>

struct node

int data;

struct node *left;

struct node *right;

};

struct node* INSERT(struct node *root,int item)

if(root==NULL)

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

root->data=item;

root->left=NULL;

root->right=NULL;

else if(item<root->data)

root->left = INSERT(root->left,item);

else

root->right = INSERT(root->right,item);

return root;

}
struct node* FINDSUCCESSOR(struct node *root)

if(root==NULL)

return root;

if(root->left==NULL)

return root;

return FINDSUCCESSOR(root->left);

struct node* DELETE(struct node *root,int item)

struct node *temp;

if(root==NULL)

printf("%d is not found",item);

else

if(item<root->data)

root->left= DELETE(root->left,item);

else if(item>root->data)

root->right= DELETE(root->right,item);

else

temp=root;

if(temp->left==NULL&&temp->right==NULL)

{
root=NULL;

free(temp);

else if(temp->left==NULL)

root=temp->right;

free(temp);

else if(temp->right==NULL)

root=temp->left;

free(temp);

else

temp=FINDSUCCESSOR(root->right);

root->data=temp->data;

root->right=DELETE(root->right,temp->data);

return root;

//This code is little short

/*struct node* DELETE(struct node *root,int item)

{

struct node *temp;

if(root==NULL)

printf("%d is not found",item);

else

if(item<root->data)

root->left=DELETE(root->left,item);

else if(item>root->data)

root->right=DELETE(root->right,item);

else

temp=root;

if(temp->left==NULL)

root=temp->right;

free(temp);

else if(temp->right==NULL)

root=temp->left;

free(temp);

else

temp=FINDSUCCESSOR(root->right);
root->data=temp->data;

root->right=DELETE(root->right,temp->data);

return root;

}*/

struct node* SEARCH(struct node *root,int item)

if(root==NULL)

return root;

if(item==root->data)

return root;

if(item<root->data)

return SEARCH(root->left,item);

return SEARCH(root->right,item);

void PREORDER(struct node *root)

if(root==NULL)

return;

printf("%d\t",root->data);

PREORDER(root->left);

PREORDER(root->right);
}

void INORDER(struct node *root)

if(root==NULL)

return;

INORDER(root->left);

printf("%d\t",root->data);

INORDER(root->right);

void POSTORDER(struct node *root)

if(root==NULL)

return;

POSTORDER(root->left);

POSTORDER(root->right);

printf("%d\t",root->data);

int main()

struct node *root=NULL;

struct node *node;

int choice,item;
while(1)

printf("\n\n\t\t***Operatons on Binary Search Tree***");

printf("\n\t\t1. Insertion of node in BST");

printf("\n\t\t2. Deletion of node from BST");

printf("\n\t\t3. Display(preorder)the BST");

printf("\n\t\t4. Display(inorder)the BST");

printf("\n\t\t5. Display(postorder)the BST");

printf("\n\t\t6. Searching");

printf("\n\t\t7. Exit");

printf("\n\nEnter your choice:");

scanf("%d",&choice);

switch(choice)

case 1:

printf("\nEnter item:");

scanf("%d",&item);

root = INSERT(root,item);

break;

case 2:

printf("\nEnter item:");

scanf("%d",&item);

root = DELETE(root,item);
break;

case 3:

if(root==NULL)

printf("Tree is empty");

else

PREORDER(root);

break;

case 4:

if(root==NULL)

printf("Tree is empty");

else

INORDER(root);

break;

case 5:

if(root==NULL)

printf("Tree is empty");

else

POSTORDER(root);

break;

case 6:

printf("\nEnter item to search:");

scanf("%d",&item);
node=SEARCH(root,item);

if(node==NULL)

printf("%d is not found",item);

else

printf("%d is found",item);

break;

case 7:

printf("\n\t\t***Good bye***");

exit(0);

break;

default:

printf("\n\nWrong choice");

return 0;

/*FUNCTION TO FIND PREDECESSOR OF A NODE*/

struct node* FINDPREDECESSOR(struct node *root)

if(root==NULL)

return root;

if(root->right==NULL)

return root;

return FINDPREDECESSOR(root->right);

}
/*FUNCTION TO COUNT NUMBER OF NODES*/

int COUNTNODE(struct node *root)

int count;

if(root==NULL)

return 0;

count= COUNTNODE (root->left)+ COUNTNODE (root->right)+1;

return count;

/*FUNCTION TO COUNT NUMBER OF LEAF NODES*/

int COUNTLEAFNODE(struct node *root)

int count;

if(root==NULL)

return 0;

count= COUNTLEAFNODE (root->left)+ COUNTLEAFNODE (root->right);

if(count==0)

count++;

return count;

/*FUNCTION TO GET LARGEST SUBTREE HEIGHT*/

int getMax(int lheight,int rheight)

if(lheight>rheight)

return lheight;

return rheight;
}

/*FUNCTION TO GET THE HEIGHT OF A TREE*/

int getHeight(struct node *root)

int height;

if(root==NULL)

return 0;

height=getMax(getHeight(root->left),getHeight(root->right))+1;

return height;

}
AVL Tree
AVL tree is a self-balancing binary search tree invented by G.M. Adelson-Velsky and
E.M. Landis in 1962. In an AVL tree, for every node in the tree, the height of the left
and right sub-trees of a node may differ by at most 1. Due to this property, the AVL
tree is also known as a height-balanced tree. The key advantage of using an AVL
tree is that it takes O(log n) time to perform search, insert, and delete operations in
an average case as well as the worst case because the height of the tree is limited
to O(log n).
In AVL tree, every node has a balance factor associated with it. The balance factor
of a node is calculated by subtracting the height of its right sub-tree from the height
of its left sub-tree. A binary search tree in which every node has a balance factor of
–1, 0, or 1 is said to be height balanced. A node with any other balance factor is
considered to be unbalanced and requires rebalancing of the tree.

Balance factor = Height (left sub-tree) – Height (right sub-tree)

 If the balance factor of a node is 1, then it means that the left sub-tree of
the tree is one level higher than that of the right sub-tree. Such a tree is
therefore called as a left-heavy tree.
 If the balance factor of a node is 0, then it means that the height of the
left sub-tree (longest path in the left sub-tree) is equal to the height of the
right sub-tree.
 If the balance factor of a node is –1, then it means that the left sub-tree of
the tree is one level lower than that of the right sub-tree. Such a tree is
therefore called as a right-heavy tree.

1 -1 -1
45 45
1 0 0 -1

36 63
36 63
1 0 0 0 0 0 0
1
27 54 72
39
27 39 54 72
0 Di 0
18 70
Fig: Left-heavy AVL tree Fig: Right-
heavy AVL tree

0 45

360 0
63

27 39
0 0 54 072 0

Fig: Balanced tree

Inserting a New Node in an AVL Tree

Insertion in an AVL tree is also done in the same way as it is done in a binary search
tree. In the
AVL tree, the new node is always inserted as the leaf node.

 If the insertion of the new node disturbs the balance factor then the
balance factor of only those nodes will change which lie in the path
between the root of the tree and the newly inserted node.
In this case, rotations (single or double) are required to restore the AVL
tree property.
 If the insertion of the new node does not disturb the balance factor i.e if
the balance factor of every node is still –1, 0, or 1 then rotations are not
required.

Q. Construct an AVL tree by inserting the following elements in the given order.
3, 2, 1, 4, 5, 6, 7, 16, 15, 14
Sol:

Step 1: Insert 3
0

3
Step 2: Insert 2
1

0
2

Step 3: Insert 1
2 x 0
2
3

1 y Right rotate at x 0 0
2 3
1

0 z
1

Step 4: Insert 4

-1
2

0 - -1
1 3

4 0

Step 5: Insert 5
-2
-1
2
2

0 -2 x Left rotate at x
1 3
1 0 4 0

-1 y
4
0 0
3 5
5 0z
Step 6: Insert 6

-2 x 0
2
4

0 -1 y Left rotate at x 0 -1
1 4 2 5

0 -1 z 0 0 0
1 3 6
3 5 0

Step 7: Insert 7 6

-1 0
4
4
0 -2 x Left rotate at x 0 0
2 5 2 6
-1 y

0 0 0z 0 0 0
6 1 3 7
0 1 3 5
7

Step 8: Insert 16

-1
4

0 -1
2 6

3
1 5 7
0 0 0 -1

0
Step 9: Insert 15

-2
4
-2
4
0 -2 Right rotate at y

0 2 0 06 -2 x 0
-2 2 6

0 0 0 -2
1 3 5 7
x
1 3 5 7
1y
16

15
-1 y
15
0z

16
0z

-1 -1
4

0 -1 Left rotate at x
2 6
0 0 0 0

1 3 5 15

0 0
7 16
Step 10: Insert 14

-2
4
4

0 -2 x x
2 6
0 0 0 0 1 y Right rotate at
2 y 6

1 3 5 15
-1 z 0 1 3 5 7

15
7 16
0 14
14 16

-1
4

0 0 Left rotate at x
2 7

0 0 1 0
6 15
1 3

16
0 0 0
5 14

Fig: AVL tree

Q. Construct an AVL tree by inserting the following elements in the given order.
BRIJESH, FIZZA, IMRAN,NAVEEN, LOVELY, PRITY, JASSI, AJIT, AMIT, HEENA, DANNY

Sol:

Step 1: Insert BRIJESH

BRIJESH

Step 2: Insert FIZZA and IMRAN

BRIJESH
-2 x
FIZZA
-1 y Left rotate at x
FIZZA BRIJESH IMRAN

0z
IMRAN

Step 3: Insert NAVEEN

FIZZA

BRIJESH IMRAN

NAVEEN

Step 4: Insert LOVELY

FIZZA FIZZA

-2 x x x
IMRAN
BRIJESH BRIJESH IMRAN
Right rotate at y

1NAVEEN y
LOVELY
0 z
NAVEEN

LOVELY Left rotate at x

FIZZA

BRIJESH LOVELY
IMRAN NAVEEN

Step 5: Insert PRITY

-2 x
FIZZA LOVELY
-1 y

BRIJESH LOVELY Left rotate at x

FIZZA NAVEEN
-1 z

IMRAN NAVEEN
PRITY BRIJESH IMRAN PRITY

Similarly, we obtain the following AVL tree-

FIZZA

LOVELY
AMIT

IMRAN NAVEEN
AJIT BRIJESH

PRITY
DANNY HEENA JASSI
//This program insert nodes in avl tree
#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *left;
struct node *right;
int balf;
};

/*This function searches in binary tree

struct node* search(struct node *root,int item)
{
static struct node *found=NULL;
if(root==NULL)
return NULL;
if(item==root->data)
return root;

found=search(root->left,item);
if(!found)
found=search(root->right,item);

return found;
}*/

struct node* search(struct node *root,int item)

{
if(root==NULL)
return root;
if(item==root->data)
return root;
if(item<root->data)
return search(root->left,item);

return search(root->right,item);
}

int getMax(int lheight,int rheight)

{
if(lheight>rheight)
return lheight;
return rheight;
}

int getHeight(struct node *root)

{
int height;
if(root==NULL)
return 0;
height=getMax(getHeight(root->left),getHeight(root->right))+1;
return height;
}

struct node* rotateLeft(struct node *x)

{
struct node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->balf=getHeight(x->left)-getHeight(x->right);
return y;
}

struct node* rotateRight(struct node *x)

{
struct node *y;
y=x->left;
x->left=y->right;
y->right=x;
x->balf=getHeight(x->left)-getHeight(x->right);
return y;
}

struct node* insert(struct node *root,int item)

{
int isRotate=0;
if(root==NULL)
{
root=(struct node*)malloc(sizeof(struct node));
root->data=item;
root->left=NULL;
root->right=NULL;
root->balf=0;
}
else if(item<root->data)
root->left=insert(root->left,item);
else
root->right=insert(root->right,item);

root->balf=abs(getHeight(root->left)-getHeight(root->right));
if(root->balf==2)
{
if(item<root->data)
{
if(item<root->left->data)
root=rotateRight(root);
else
{
root->left=rotateLeft(root->left);
root=rotateRight(root);
}
}
else if(item>root->data)
{
if(item>root->right->data)
root=rotateLeft(root);
else
{
root->right=rotateRight(root->right);
root=rotateLeft(root);
}
}
isRotate=1;
}
if(isRotate)
root->balf=getHeight(root->left)-getHeight(root->right);

return root;
}

struct node* getPredecessor(struct node *root)

{
if(root==NULL)
return NULL;
if(root->right==NULL)
return root;
return getPredecessor(root->right);
}

struct node* getSuccessor(struct node *root)

{
if(root==NULL)
return NULL;
if(root->left==NULL)
return root;
return getSuccessor(root->left);
}

void inorder(struct node *root)

{
if(root==NULL)

return;
inorder(root->left);

printf("%d\t",root->data);

inorder(root->right);
}

//This function is also correct

//no is global variable

/*int no=0;
void countNode(struct node *root)
{
if(root!=NULL)
{
no++;
countNode(root->left);
countNode(root->right);
}
}*/

int countNode(struct node *root)

{
int count;
if(root==NULL)
return 0;
count=countNode(root->left)+countNode(root->right)+1;
return count;
}

int countLeafNode(struct node *root)

{
int count;
if(root==NULL)
return 0;
count=countLeafNode(root->left)+countLeafNode(root->right);
if(count==0)
count++;
return count;
}

int main()
{
struct node *root=NULL;
struct node *node,*predecessor,*successor;
int choice,item;
while(1)
{
printf("\n\n\t\t***Operatons on AVL Tree***");
printf("\n\t\t1. Insertion of node");
printf("\n\t\t2. Display(inorder)");
printf("\n\t\t3. Count node");
printf("\n\t\t4. Count leaf node");
printf("\n\t\t5. Find height of tree");
printf("\n\t\t6. Find predecessor of node");
printf("\n\t\t7. Find successor of node");
printf("\n\t\t8. Searching");
printf("\n\t\t9. Exit");

printf("\n\nEnter your choice:");

scanf("%d",&choice);

switch(choice)
{
case 1:
printf("\n\nEnter item:");
scanf("%d",&item);
root=insert(root,item);
break;

case 2:
if(root==NULL)
printf("Tree is empty");
else
inorder(root);
break;

case 3:
printf("no. of nodes = %d",countNode(root));
break;

case 4:
printf("no. of leaf nodes = %d",countLeafNode(root));
break;

case 5:
printf("Height of tree = %d",getHeight(root));
break;

case 6:
printf("\n\nEnter item:");
scanf("%d",&item);
node=search(root,item);
if(node==NULL)
printf("%d is not found",item);
else
{
predecessor=getPredecessor(node->left);
if(predecessor==NULL)
printf("Predecessor of %d does not exist",node->data);
else
printf("Predecessor of %d = %d",node->data,predecessor->data);
}
break;

case 7:
printf("\n\nEnter item:");
scanf("%d",&item);
node=search(root,item);
if(node==NULL)
printf("%d is not found",item);
else
{
successor=getSuccessor(node->right);
if(successor==NULL)
printf("Successor of %d does not exist",node->data);
else
printf("Successor of %d = %d",node->data,successor->data);
}
break;

case 8:
printf("\n\nEnter item to search:");
scanf("%d",&item);
node=search(root,item);
if(node==NULL)
printf("%d is not found",item);
else
printf("%d is found",item);
break;

case 9:
printf("\n\t\t***Good bye***");
exit(0);
break;
default:
printf("\n\nWrong choice");
}
}
return 0;
}

Deleting a Node from an AVL Tree

Deletion of a node in an AVL tree is similar to that of binary search trees. After
deletion of node, we trace the path from the parent of the deleted node to the root
node. During tracing, if any unbalanced node(a node that does not has its balance
factor as 1,0 or -1) is found then we rebalanced that node by performing rotation.
After fixing that node, we may have to perform a rotation at some ancestor of that
node. Thus, we must continue to trace the path until we reach the root node.

Note: In insertion there is at most one node that needs to be rebalanced

whereas in deletion there may be multiple nodes that need to be
rebalanced.

Consider the following AVL Tree

3 16

2 5 11 18

1 4 6 9 13 17 19

7 10 12 14 20

15
Deleting node 1 from AVL tree

x
3 16
y

2 5 11 18
z

4 6 9 13 17 19

7 10 12 14 20

While its parent 2 is not unbalanced but its grandparent 3 is so we assume 3 as x.

15
Since the height of right subtree of 3 is longer so we assume 5 as y. Again, the
height of right subtree of 5 is longer so we finally assume 6 as z.
After left rotation at x, we get the Avl tree as follows-

x
8

y
5 16
z

3 6 11 18

2 7

4 9 13 17 19

10 12 14 20

The subtree at 5 is now balanced but 8 is unbalanced so we assume

15 8 as x. Since
the longest subtree of 8 is right subtree so we assume 16 as y.

Similarly, longest subtree of 16 is left subtree so we assume 11 as z.

After right rotation at y and left rotation at x, we get the Avl tree as follows-

11

8 16

5 9 13 18

6 10 12 14 17 19
2 4 7
Fig: AVL Tree
15 20

Consider another tree-

x
30

y
5 45
z

35
50

55
32

The above tree is unbalanced at 30 so we assume 30 as x. Since the right subtree of

30 is longer so we assume 45 as y. Since both subtrees of 45 are of the same
height, and since 45 is the RIGHT child of 30 so we will choose 45’s right child 50 as
z.

After left rotation at x, we get the AVL tree as follows-

45

30 50

55
5 35
Fig: AVL Tree

B-Tree

A B-tree is a height balanced search tree. A node of the tree may contain many
records or keys and pointers to children. Storing many keys in a single node keeps
the height of the tree relatively small. The B-tree is used in external sorting. It is not
a binary tree.

A B-tree of order m has the following properties-

(a) The root node has at least two children if it is not a leaf node.
(b) Each node except the root node and leaf node has at least(minimum)
ceil(m/2) children. Each node has at most(maximum) m children.
(c) Each node except the root node and leaf node has at least(minimum)
ceil(m/2)-1 keys. Each node has at most(maximum) m-1 keys.
(d) All leaf nodes are at the same level.

Fig: B-tree of order 4

Inserting a New Element(key) in a B Tree

In a B tree, all insertions are done at the leaf node level. A new value is inserted in
the B tree as follows-
1. Search the B tree to find the leaf node where the new key should be inserted.
2. If the leaf node is not full, that is, it contains less than m–1 keys, then insert the
new
key in the node keeping the node’s keys ordered.
3. If the leaf node is full, that is, the leaf node already contains m–1 keys, then
(a) insert the new key in order into the existing set of keys,
(b) split the node at its median(middle) key into two nodes and
(c) push the median key up to its parent’s node. If the parent’s node is already full,
then
split the parent node by following the same steps.

Q. Create a B-Tree of order 5(odd order) by inserting following keys

1,5,6,2,8,11,13,18,20,7

Sol: Here the order of B-tree is m=5

A B-tree of order m=5 has the following properties-

Minimum no. of children = ceil(m/2) = ceil(5/2) = ceil(2.5) = 3

Maximum no. of children = m = 5

Minimum no. of keys = ceil(m/2) - 1 = ceil(5/2) - 1 = ceil(2.5) - 1 = 3 – 1 = 2

Maximum no. of keys = m - 1 = 5 – 1 = 4

Step 1: We insert the keys 1,5,6 and 2 into root node.

1 2 5 6

Step 2: Next key is 8. Since the root node is already full so it splits at median key 5
as follows-

1 2 6 8

Step 3: Next we insert the keys 11 and 13.

5
1 2 6 8 11 13

Step 4: Next key is 18. Since the node is already full so it splits at
median key 11. 6 8 11 13

5 11

1 2 6 8 13 18

Step 5: Next we insert the keys 20 and 7.

5 11

1 2 6 7 8 13 18 20

Fig: B-tree of order 5

Insertion in a B-tree of even order

left-bias: The node is split such that its left subtree has more keys than the right
subtree.

right-bias: The node is split such that its right subtree has more keys than the left
subtree.

Example: Insert the key 5 in the following B-tree of order 4:

Q. Create a B-Tree of order 4(even order) by inserting following keys

1,5,6,2,8,11,13,18,20,7

Sol: Here the order of B-tree is m=4

A B-tree of order m=4 has the following properties-

Minimum no. of children = ceil(m/2) = ceil(4/2) = ceil(2) = 2

Maximum no. of children = m = 4

Minimum no. of keys = ceil(m/2) - 1 = ceil(4/2) - 1 = ceil(2) - 1 = 2 – 1 = 1

Maximum no. of keys = m - 1 = 4 – 1 = 3

Step 1: We insert the keys 1,5 and 6 into root node.

1 5 6

Step 2: Next key is 2. Since the root node is already full so we it splits at median
key 5 as follows-

1 2 6
Step 3: Next we insert the keys 8 and 11.

1 2 6 8 11

Step 4: Next key is 13. Since the node is already full so it splits at
median key 11 as follows- 6 8 11

5 11

1 2 6 8 13

Step 5: Next we insert the keys 18, 20 and 7.

5 11

1 2 6 7 8 13 18 20
Fig: B-tree of order 4

Q. Create a B-tree of order 5 from the following keys

CNGAHEKQMFWLTZDPRXYS

Sol: Here the order of B-tree is m=5

A B-tree of order m=5 has the following properties-

Minimum no. of children = ceil(m/2) = ceil(5/2) = ceil(2.5) = 3

Maximum no. of children = m = 5

Minimum no. of keys = ceil(m/2) - 1 = ceil(5/2) - 1 = ceil(2.5) - 1 = 3 – 1 = 2

Maximum no. of keys = m - 1 = 5 – 1 = 4

Step 1: We insert the keys C, N, G and A into root node.

A C G N

Step 2: Next key is H. Since the root node is already full so it splits at median key G
as follows-

A C H N
Step 3: Next we insert the keys E, K and Q.

A C E H K N Q

Step 4: Next key is M. Since the node is already full so it

H K N Q
splits at median key M as follows-

G M

A C E H K
N Q

Step 5: Next we insert the keys F, W, L and T.

G M

A C E F H K L N Q T W

Step 6: Next key is Z. Since the node is already full so it

N Q T W
splits at median key T as follows-
G M T

A C E F H K L N Q W Z

Step 7: Next we insert the keys D, P, R, X and Y.

D G M T

A C H K L
E F N P Q R W X Y Z

Step 6: Next key is S. Since the node is already full so it

splits at median key N P Q R

Q. In this, root node is also split at median key M as follows-

D G Q T

A C E F H K L N P
Fig: B-tree of order 5 R S W X Y Z

Deleting an Element(key) from a B Tree

Like insertion, deletion is also done from the leaf nodes. There are two cases of
deletion. In the
first case, a leaf node has to be deleted. In the second case, an internal node has to
be deleted.

Deletion of an element from a leaf node

1. Locate the leaf node from which the key has to be deleted.
2. If the leaf node contains more than the minimum number of keys then delete the
key.
3. Else, if the leaf node contain less than minimum no. of keys, then fill the node by
taking a key
either from the left or from the right sibling.
(a) If the left sibling has more than the minimum number of keys, push its largest
key into its parent’s node and pull down the intervening key from the parent node
to the leaf node where the key is deleted.
(b) Else, if the right sibling has more than the minimum number of keys, push its
smallest key into its parent node and pull down the intervening key from the parent
node to the leaf node where the key is deleted.
4. Else, if both left and right siblings contain only the minimum number of keys,
then
create a new leaf node by combining the two leaf nodes and the intervening key of
the
parent node (ensuring that the number of keys does not exceed the maximum
number
of keys a node can have, that is, m). If pulling the intervening key from the parent
node leaves it with less than the minimum number of keys in the node, then
propagate the
process upwards, thereby reducing the height of the B tree.

Deletion of an element from internal node

To delete a key from an internal node, promote the successor or predecessor of the
key to be deleted to occupy the position of the deleted key. This predecessor or
successor will always be in the leaf node.

Q. Consider the following B tree of order 5 and delete values 93, 201, 180, and 72
from it.

108

63 81 117 201

36 45 72 79 90 93 101 111 114 151 180 243 256 333 450

Sol:

Delete 93

Since the key 93 is in a leaf and the leaf has more than the minimum number of
keys so this is easy.

108

63 81 117 201
36 45

Delete 201

Since the key 201 is in internal node so we can replace 201 with either its
immediate predecessor 180 (maximum key in left sibling) or immediate successor
243(minimum key in right sibling).

The node containing the immediate predecessor has already

minimum keys
151 180
so we replace 201 with its immediate successor 243.

108

63 81 117 243

Delete 180
256 333 450
Although 72
36 45 the79 key 180 is in
90leaf 111 leaf
101node but this 151 not
114 node does 180 have an extra key
so the deletion results in a node with only 1 key which is not acceptable for a B-tree
of order 5. If the sibling node to the immediate left or right has an extra key, we can
then borrow a key from the parent and move a key up from this sibling to the
parent.

In our specific case, the sibling to the right has an extra key.

Therefore, we move down key 243 from parent to the leaf node that underflows and
move up the successor key 256 of 243 from the right sibling to replace 243.

108

63 81 117 256

333 450
36 45 72 79 90 101 111 114 151 243
Delete 72

This one causes lots of problems. Although 72 is in a leaf but the leaf has no extra
keys nor do the siblings to the immediate left or right. In such a case the leaf has to
be combined with one of these two siblings. This includes moving down the parent's
key that was between those of these two leaves. In our example, let's combine the
leaf containing 79 with the leaf containing 36 and 45. We also move down 63.

108

81
117 256

36 45 63 79 90 101 111 114 151 243 333 450

The parent node now contains only one key 81. This is not acceptable. If this
problem node had a sibling to its immediate left or right that had a spare key then
we would again "borrow" a key. Since we have no way to borrow a key from a
sibling, we must again combine with the sibling, and move down the key 108 from
the parent. In this case, the tree shrinks in height by one.

81 108 117 256

36 45 63 79 90 101 111 114 151 243 333 450

Q. Consider the following B tree of order 5 and delete C from it.

C F M R U

A B D E G I K L N P S T X Z

Sol: Find the immediate successor which would be D and move the D up to replace
the C. However, this leaves us with a node with too few keys.

D F M R U

C is removed and D went up so E is the only node (not allowed). Since neither the
sibling to the left or right of the node containing E has an extra key, we must
A B the node Ewith one of G
combine I
these K L
two siblings. Let's Nconsolidate
P S T the A B X Z
with
node.

F M R U

A B D E G I K L N P S T X Z
But now the node containing F does not have enough keys. However, its sibling has
an extra key. Thus we borrow the M from the sibling, move it up to the parent, and
bring the J down to join the F. Note that the K L node gets reattached to the right of
the J.
M
Heap

A heap is a complete binary tree in which the value of each node is ≥ or ≤ to the
value of its children. This is called heap property.
F J R U

7 11
A B D E G I K L N P S T X Z

3 5 2
6

1 2 1
Fig 4 6 17Fig 2 14 3

The tree in Fig 1 is a heap since the value of each node is greater than its children
but the tree in Fig 2 is not a heap since the value of each node is lesser than its
children except the node 11.

Types of Heaps

Based on the heap property, heap is of two types-

(a) Max heap

The value of each node is greater than or equal to (≥) the value of its
children.

17

13 6

1 4 2 5

(b) Min heap

The value of each node is less than or equal to (≤) the value of its
children.

15 2

16 17 4 3
Inserting a New Element in a Binary Heap
Consider a max heap H with n elements. Inserting a new value into the heap is done
in the following two steps:
1. Add the new value at the bottom of H in such a way that H is still a complete
binary tree but
not necessarily a heap.
2. Let the new value rise to its appropriate place in H so that H now becomes a heap
as well.

To do this, compare the new value with its parent to check if they are in the correct
order. If
they are, then the procedure halts, else the new value and its parent’s value are
swapped and
Step 2 is repeated.

Q. Consider the max heap given in following figure and insert 99 in it.

54

45 36

18
27 21 21

Fig: Max Heap

11

Sol:
54
45 36

27 21 18 21

11 Fig: Insert 99 in Max Heap just like a

99
complete binary tree. After insertion of
99 it’s a complete binary tree but not a
Max Heap

To maintain Max Heap property, Compare 99 with its parent node value. If it is less
than its parent’s value, then the new node is in its appropriate place and H is a
heap. If the new value is greater than that of its parent’s node, then swap the two
values. Repeat the whole process until H becomes a heap.

Step 1:

54 Compare 99 with its 54

Parent 27. Since 99>27

45 36 45 36
So, swap them

27 21 18 21 99 21 18 21

11 99 11 27
Step 2:

54 Compare 99 with 45.

54
Since 99>45 so swap them.

45 36 99 36

99 21 18 21 45 21 18 21

11 27
11 27

Step 3:

Compare 99 with 54.

54 99
Since 99>54 so swap them.

99 36 54 36

45 21 18 21 45 21 18 21

11 27 11 27

Fig: Max Heap

Q. Build a Max Heap H from the given set of numbers 45, 36, 54, 27, 63, 72, 61 and
18.

Sol:
Step 1:

45
Step 2:
45

36

Step 3:

45 Compare 54 with 45.

54
Since 54>45 so we swap them.

36 54
36 45

Step 4:

54

Step 5: 36 45

54
27
Compare 63 with 36.
54
Since 63>36 so we swap them.
36 45

63 45
27 63

27 36
Step 6:

Compare 63 with 54.

54
63
Since 63>54 so we swap

63 45
54 45

27 36
27 36
Similarly, we obtain the final Max Heap as follows-

72

54 63

27 36 45 61
Di

18

Fig: Max Heap

Deleting an Element from a Binary Heap

Consider a max heap H having n elements. An element is always deleted from the
root of the heap. So, deleting an element from the heap is done in the following
three steps:

1. Replace the root node’s value with the last node’s value so that H is still a
complete binary tree but not necessarily a heap.
2. Delete the last node.
3. Sink down the new root node’s value so that H satisfies the heap property. In this
step, interchange the root node’s value with its child node’s value (whichever is
largest among its children).
Q. Consider the Max Heap H in the following figure and delete the root node’s
value.

54

45 36

27 29 18 21
Di

11

Sol: Here, the value of root node = 54 and the value of the last node = 11. So,
replace 54 with 11 and delete the last node.

Step 1:
45
11
Since 11<45 so we swap them

11 36
45 36

27 29 18 21
27 29 18 21 Di
Di

Step 2:

Since 11<29 so we swap them

45 45

11 36 29 36

27 29 18 21 27 11 18 21
Di Di