Page |1

Trees
Tree represents the nodes connected by edges.
A tree is also one of the data structures that represent hierarchical data.
Suppose we want to show the employees and their positions in the hierarchical form then it
can be represented as shown below:

General Tree:
The general tree is one of the types of tree data structure. In the general tree, a node can
have either 0 or maximum n number of nodes. There is no restriction imposed on the
degree of the node (the number of nodes that a node can contain). The topmost node in a
general tree is known as a root node. The children of the parent node are known
as subtrees
 Page |2

.
There can be n number of subtrees in a general tree. In the general tree, the subtrees are
unordered as the nodes in the subtree cannot be ordered.
Every non-empty tree has a downward edge, and these edges are connected to the nodes
known as child nodes. The root node is labeled with level 0. The nodes that have the same
parent are known as siblings.

Tree Terminologies:
In a tree data structure, if we have N number of nodes then we can have a maximum of N-
1 number of links.

Example

Terminology
In a tree data structure, we use the following terminology...

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

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.

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

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
 Page |4

tree, any parent node can have any number of child nodes. In a tree, all the nodes except
root are child nodes.

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

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.
 Page |5

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.

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

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

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'.

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

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

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.

Binary Tree:
 Page |8

The Binary tree means that the node can have maximum two children. Here, binary name
itself suggests that 'two'; therefore, each node can have either 0, 1 or 2 children.

Let's understand the binary tree through an example.

Properties of Binary Tree:

 At each level of i, the maximum number of nodes is 2i.
 The height of the tree is defined as the longest path from the root node to the leaf
node. The tree which is shown above has a height equal to 3. Therefore, the
maximum number of nodes at height 3 is equal to (1+2+4+8) = 15. In general, the
maximum number of nodes possible at height h is (20 + 21 + 22+….2h) = 2h+1 -1.
 The minimum number of nodes possible at height h is equal to h+1.
 If the number of nodes is minimum, then the height of the tree would be maximum.
Conversely, if the number of nodes is maximum, then the height of the tree would
be minimum.
If there are 'n' number of nodes in the binary tree.

The minimum height can be computed as:

As we know that,
n = 2h+1 -1
n+1 = 2h+1
Taking log on both the sides,
log2(n+1) = log2(2h+1)
log2(n+1) = h+1
h = log2(n+1) - 1
The maximum height can be computed as:
As we know that,
n = h+1
h= n-1
Variations of Binary Tree:
There are four types of Binary tree:
 Full/ proper/ strict Binary tree
 Complete Binary tree
 Perfect Binary tree
 Degenerate Binary tree
 Balanced Binary tree
 Page |9

Full/ proper/ strict Binary tree:

The full binary tree is also known as a strict binary tree. The tree can only be considered as
the full binary tree if each node must contain either 0 or 2 children. The full binary tree can
also be defined as the tree in which each node must contain 2 children except the leaf
nodes.
Let's look at the simple example of the Full Binary tree.

Properties of Full Binary Tree:

 The number of leaf nodes is equal to the number of internal nodes plus 1. In the
above example, the number of internal nodes is 5; therefore, the number of leaf
nodes is equal to 6.
 The maximum number of nodes is the same as the number of nodes in the binary
tree, i.e., 2h+1 -1.
 The minimum number of nodes in the full binary tree is 2*h-1.
 The minimum height of the full binary tree is log2(n+1) - 1.
 The maximum height of the full binary tree can be computed as:
n= 2*h - 1
n+1 = 2*h
h = n+1/2== 5+1/2=3

Complete Binary Tree:

The complete binary tree is a tree in which all the nodes are completely filled except the last
level. In the last level, all the nodes must be as left as possible. In a complete binary tree, the
nodes should be added from the left.
Let's create a complete binary tree.
 P a g e | 10

The above tree is a complete binary tree because all the nodes are completely filled, and all
the nodes in the last level are added at the left first.

Properties of Complete Binary Tree

o The maximum number of nodes in complete binary tree is 2h+1 - 1.
o The minimum number of nodes in complete binary tree is 2h.
o The minimum height of a complete binary tree is log2(n+1) - 1.
o The maximum height of a complete binary tree is h= n-1;

Perfect Binary Tree

A tree is a perfect binary tree if all the internal nodes have 2 children, and all the leaf nodes
are at the same level.

Right Skewed Tree:

A binary tree with only right sub tree.
 P a g e | 11

Left Skewed Tree:

A binary tree with only left sub tree.

Heap:
It is a special case of balanced binary tree data structure where the root-node key is
compared with its children and arranged accordingly. If α has child node β then −
key(α) ≥ key(β)
As the value of parent is greater than that of child, this property generates Max Heap.
Based on this criteria, a heap can be of two types −
For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap − Where the value of the root node is less than or equal to either of its children.
 P a g e | 12

Max-Heap − Where the value of the root node is greater than or equal to either of its
children.

Memory Representation of a binary tree:

Binary trees are to be maintained in memory. There are two methods used to store binary
trees in memory.
 Sequential Representation.
 Linked List Representation.

Sequential Representation:
Let us consider that we have a tree T. let our tree T is a binary tree that us complete binary
tree. Then there is an efficient way of representing T in the memory called the sequential
representation or array representation of T. This representation uses only a linear array
TREE as follows:
1. The root N of T is stored in TREE [1].
2. If a node occupies TREE [k] then its left child is stored in TREE [2 * k] and its right
child is stored into TREE [2 * k + 1].
For Example:
Consider the following Tree: Binary Tree
 P a g e | 13

Sequential Representation:

Advantages & Disadvantages of Sequential Representation:

Advantages
The approach, known as a sequential tree representation, has the advantage of saving
space because no pointers are stored. It has the disadvantage that accessing any node in
the tree requires sequentially processing all nodes that appear before it in the node list.
Disadvantages
It has the disadvantage that accessing any node in the tree requires sequentially processing
all nodes that appear before it in the node list. In other words, node access must start at the
beginning of the node list, processing nodes sequentially in whatever order they are stored
until the desired node is reached.

Linked Representation of Binary Tree:

Consider a Binary Tree T. T will be maintained in memory by means of a linked list
representation which uses three parallel arrays; INFO, LEFT, and RIGHT pointer
variable ROOT as follows. In Binary Tree each node N of T will correspond to a
location k such that
1. LEFT [k] contains the location of the left child of node N.
2. INFO [k] contains the data at the node N.
3. RIGHT [k] contains the location of right child of node N.
Representation of a node:
 P a g e | 14

In this representation of binary tree root will contain the location of the root R of T. If any
one of the subtree is empty, then the corresponding pointer will contain the null value if the
tree T itself is empty, the ROOT will contain the null value.
Binary Tree:

Linked List Representation of binary tree:

Advantages and disadvantages of linked representation

Advantages
I. A particular node can be placed at any location in the memory.
II. Insertions and deletions can be made directly without data movements.
III. It is best for any type of trees.
IV. It is flexible because the system take care of allocating and freeing of nodes.

Disadvantages
I. It is difficult to understand.
II. Additional memory is needed for storing pointers
III. Accessing a particular node is not easy.

Binary Search Tree:

 P a g e | 15

1. Binary Search tree can be defined as a class of binary trees, in which the nodes are
arranged in a specific order. This is also called ordered binary tree.
2. In a binary search tree, the value of all the nodes in the left sub-tree is less than the
value of the root.
3. Similarly, value of all the nodes in the right sub-tree is greater than or equal to the
value of the root.
4. This rule will be recursively applied to all the left and right sub-trees of the root.

A Binary search tree is shown in the above figure. As the constraint applied on the BST, we
can see that the root node 30 doesn't contain any value greater than or equal to 30 in its left
sub-tree and it also doesn't contain any value less than 30 in its right sub-tree.

Create the binary search tree using the following data elements.
43, 10, 79, 90, 12, 54, 11, 9, 50
1. Insert 43 into the tree as the root of the tree.
2. Read the next element, if it is lesser than the root node element, insert it as the root
of the left sub-tree.
3. Otherwise, insert it as the root of the right of the right sub-tree.
The process of creating BST by using the given elements, is shown in the image below.
 P a g e | 16

Basic Operations:
Following are the basic operations of a tree −
 Search − Searches an element in a tree.
 Insert − Inserts an element in a tree.
 Pre-order Traversal − Traverses a tree in a pre-order manner.
 In-order Traversal − Traverses a tree in an in-order manner.
 Post-order Traversal − Traverses a tree in a post-order manner.

Search Operation:
Whenever an element is to be searched, start searching from the root node. Then if the
data is less than the key value, search for the element in the left subtree. Otherwise, search
for the element in the right subtree. Follow the same algorithm for each node.

Algorithm:
 P a g e | 17

11 void insert(node ** tree, int val) {

12 node *temp = NULL;
13 if((*tree)) {
14 temp = (node *)malloc(sizeof(node));
15 temp->left = temp->right = NULL;
16 temp->data = val;
17 *tree = temp;
18 return;
19 }
20
21 if(val < (*tree)->data) {
22 insert(&(*tree)->left, val);
23 } else if(val > (*tree)->data) {
24 insert(&(*tree)->right, val);
25 }
26 }

This function would determine the position as per value of node to be added and new node
would be added into binary tree. Function is explained in steps below and code snippet lines
are mapped to explanation steps given below.

[Lines 13-19] Check first if tree is empty, then insert node as root.
[Line 21] Check if node value to be inserted is lesser than root node value, then
 a. [Line 22] Call insert() function recursively while there is non-NULL left node
 b. [Lines 13-19] When reached to leftmost node as NULL, insert new node.
[Line 23] Check if node value to be inserted is greater than root node value, then
 a. [Line 24] Call insert() function recursively while there is non-NULL right node
 b. [Lines 13-19] When reached to rightmost node as NULL, insert new node.

Searching into binary tree

Searching is done as per value of node to be searched whether it is root node or it lies in left
or right sub-tree. Below is the code snippet for search function. It will search node into
binary tree.

Algorithm:

46 node* search(node ** tree, int val) {

47 if(!(*tree)) {
48 return NULL;
49 }
50 if(val == (*tree)->data) {
51 return *tree;
52 } else if(val < (*tree)->data) {
53 search(&((*tree)->left), val);
54 } else if(val > (*tree)->data){
 P a g e | 18

55 search(&((*tree)->right), val);
56 }
57 }

This search function would search for value of node whether node of same value already
exists in binary tree or not. If it is found, then searched node is returned otherwise NULL
(i.e. no node) is returned. Function is explained in steps below and code snippet lines are
mapped to explanation steps given below.
1. [Lines 47-49] Check first if tree is empty, then return NULL.
2. [Lines 50-51] Check if node value to be searched is equal to root node value, then return
node
3. [Lines 52-53] Check if node value to be searched is lesser than root node value, then call
search() function recursively with left node
4. [Lines 54-55] Check if node value to be searched is greater than root node value, then
call search() function recursively with right node
5. Repeat step 2, 3, 4 for each recursion call of this search function until node to be
searched is found.

Deletion of binary tree

Binary tree is deleted by removing its child nodes and root node. Below is the code snippet
for deletion of binary tree.

38 void deltree(node * tree) {

39 if (tree) {
40 deltree(tree->left);
41 deltree(tree->right);
42 free(tree);
43 }
44 }

This function would delete all nodes of binary tree in the manner – left node, right node and
root node. Function is explained in steps below and code snippet lines are mapped to
explanation steps given below.
[Line 39] Check first if root node is non-NULL, then
 a. [Line 40] Call deltree() function recursively while there is non-NULL left node
 b. [Line 41] Call deltree() function recursively while there is non-NULL right node
 c. [Line 42] Delete the node.

Traversal of a Binary Tree:

Tree traversal is the process of visiting each node in the tree exactly once. Visiting each
node in a graph should be done in a systematic manner. If search result in a visit to all the
vertices, it is called a traversal. There are basically three traversal techniques for a binary
tree that are,
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
 P a g e | 19

Preorder traversal:
To traverse a binary tree in preorder, following operations are carried out:
1. Visit the root.
2. Traverse the left sub tree of root.
3. Traverse the right sub tree of root.

Note: Preorder traversal is also known as NLR traversal.

Algorithm:
Algorithm preorder(t)
/*t is a binary tree. Each node of t has three fields:
lchild, data, and rchild.*/
{
If t! =0 then
{
Visit(t);
Preorder(t->lchild);
Preorder(t->rchild);
}
}

Example:

Therefore, the preorder traversal of the above tree will be: 7,1,0,3,2,5,4,6,9,8,10

Inorder traversal:
To traverse a binary tree in inorder traversal, following operations are carried out:
1. Traverse the left most sub tree.
2. Visit the root.
3. Traverse the right most sub tree.
 P a g e | 20

Note: Inorder traversal is also known as LNR traversal.

Algorithm:
Algorithm inorder(t)

/*t is a binary tree. Each node of t has three fields:

lchild, data, and rchild.*/
{
If t! =0 then
{
Inorder(t->lchild);
Visit(t);
Inorder(t->rchild);
}
}

Example:

Therefore the inorder traversal of above tree will be: 0,1,2,3,4,5,6,7,8,9,10

Postorder traversal:
To traverse a binary tree in postorder traversal, following operations are carried out:
1. Traverse the left sub tree of root.
2. Traverse the right sub tree of root.
3. Visit the root.
Note: Postorder traversal is also known as LRN traversal.

Algorithm:

Algorithm postorder(t)

/*t is a binary tree .Each node of t has three fields:

 P a g e | 21

lchild, data, and rchild.*/

{
If t! =0 then
{
Postorder(t->lchild);
Postorder(t->rchild);
Visit(t);
}
}

Therefore the postorder traversal of the above tree will be: 0,2,4,6,5,3,1,8,10,9,7

Working Program:

#include<stdlib.h>
#include<stdio.h>
struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;
void insert(node ** tree, int val)
{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
 P a g e | 22

if(val < (*tree)->data)

{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}
}
void print_preorder(node * tree)
{
if (tree)
{
printf("%d\n",tree->data);
print_preorder(tree->left);
print_preorder(tree->right);
}
}
void print_inorder(node * tree)
{
if (tree)
{
print_inorder(tree->left);
printf("%d\n",tree->data);
print_inorder(tree->right);
}
}
void print_postorder(node * tree)
{
if (tree)
{
print_postorder(tree->left);
print_postorder(tree->right);
printf("%d\n",tree->data);
}
}
void deltree(node * tree)
{
if (tree)
{
deltree(tree->left);
deltree(tree->right);
free(tree);
}
 P a g e | 23

node* search(node ** tree, int val)

{
if(!(*tree))
{
return NULL;
}
if(val < (*tree)->data)
{
search(&((*tree)->left), val);
}
else if(val > (*tree)->data)
{
search(&((*tree)->right), val);
}
else if(val == (*tree)->data)
{
return *tree;
}
}
void main()
{
node *root;
node *tmp;
//int i;

root = NULL;
/* Inserting nodes into tree */
insert(&root, 9);
insert(&root, 4);
insert(&root, 15);
insert(&root, 6);
insert(&root, 12);
insert(&root, 17);
insert(&root, 2);
/* Printing nodes of tree */
printf("Pre Order Display\n");
print_preorder(root);

printf("In Order Display\n");

print_inorder(root);

printf("Post Order Display\n");

print_postorder(root);
 P a g e | 24

/* Search node into tree */

tmp = search(&root, 4);
if (tmp)
{
printf("Searched node=%d\n", tmp->data);
}
else
{
printf("Data Not found in tree.\n");
}

/* Deleting all nodes of tree */

deltree(root);
}

Output:

Pre Order Display

9
4
2
6
15
12
17
In Order Display
2
4
6
9
12
15
17
Post Order Display
2
6
4
12
17
15
9
Searched node=4

Height balance: AVL Trees:

 P a g e | 25

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.

Why AVL Tree?

AVL tree controls the height of the binary search tree by not letting it to be skewed. The
time taken for all operations in a binary search tree of height h is O(h). However, it can be
extended to O(n) if the BST becomes skewed (i.e. worst case). By limiting this height to log
n, AVL tree imposes an upper bound on each operation to be O(log n) where n is the
number of nodes.

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(k)) - height (right(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.

Representation of AVL Trees:

Struct AVLNode
{
int data;
struct AVLNode *left, *right;
int balfactor;
};
 P a g e | 26

Operations on AVL Trees:

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.

SN Operation Description
1 Insertion Insertion in AVL tree is performed in the same way as it is performed in
a binary search tree. 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.
2 Deletion Deletion can also be performed in the same way as it is performed in a
binary search tree. Deletion may also disturb the balance of the tree
therefore, various types of rotations are used to rebalance the tree.

Algorithm for Insertion:

Step 1: First, insert a new element into the tree using BST's (Binary Search Tree) insertion
logic.
Step 2: After inserting the elements you have to check the Balance Factor of each node.
Step 3: When the Balance Factor of every node will be found like 0 or 1 or -1 then the
algorithm will proceed for the next operation.
 P a g e | 27

Step 4: When the balance factor of any node comes other than the above three values then
the tree is said to be imbalanced. Then perform the suitable Rotation to make it balanced
and then the algorithm will proceed for the next operation.

Algorithm for Deletion:

Step 1: Firstly, find that node where k is stored

Step 2: Secondly delete those contents of the node (Suppose the node is x)
Step 3: Claim: Deleting a node in an AVL tree can be reduced by deleting a leaf. There are
three possible cases:
When x has no children then, delete x
When x has one child, let x' becomes the child of x.
Notice: x' cannot have a child, since subtrees of T can differ in height by at
most one: then replace the contents of x with the contents of x' then delete
x' (a leaf)
Step 4: When x has two children,
then find x's successor z (which has no left child)
then replace x's contents with z's contents, and
delete z
In all of the three cases, you will end up removing a leaf.

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:

 L L rotation: Inserted node is in the left subtree of left subtree of A.

 R R rotation: Inserted node is in the right subtree of right subtree of A.
 L R rotation: Inserted node is in the right subtree of left subtree of A.
 R L rotation: Inserted node is in the left subtree of right subtree of A.

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

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
 P a g e | 28

In above example, 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, 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 on full tree, by full tree we mean the first node from the path of
inserted node whose balance factor is other than -1, 0, or 1.

State Action
 P a g e | 29

A 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 full tree, i.e. on node C.

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

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

balanced now.

4.RL Rotation:

As already discussed, that double rotations are bit tougher than single rotation which has
already explained above. R L rotation = LL rotation + RR rotation, i.e., first LL rotation is
 P a g e | 30

performed on subtree and then RR rotation is performed on full tree, by full tree we mean
the first node from the path of inserted node whose balance factor is other than -1, 0, or 1.

State Action

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.

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 full

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.
 P a g e | 31

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

is balanced now.

Construct an AVL tree having the following elements

H, I, J, B, A, E, C, F, D, G, K, L

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:

2. Insert B, A
 P a g e | 32

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

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:
 P a g e | 33

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:
 P a g e | 34

5. Insert G

On inserting G, BST become unbalanced as the Balance Factor of H is 2, since if we travel

from G to H, we find that it is inserted in the left subtree of right subtree of H, we will
perform LR Rotation on node I. LR = RR + LL rotation.

5 a) We first perform RR rotation on node C

The resultant tree after RR rotation is:

5 b) We then perform LL rotation on node H

The resultant balanced tree after LL rotation is:
 P a g e | 35

6. Insert K

On inserting K, BST becomes unbalanced as the Balance Factor of I is -2. Since the BST is
right-skewed from I to K, hence we will perform RR Rotation on the node I.
The resultant balanced tree after RR rotation is:

7. Insert L
On inserting the L tree is still balanced as the Balance Factor of each node is now either, -1,
0, +1. Hence the tree is a Balanced AVL tree
 P a g e | 36

Heap Data Structure

Heap is a special case of balanced binary tree data structure where the root-node key is
compared with its children and arranged accordingly. If α has child node β then −

key(α) ≥ key(β)

As the value of parent is greater than that of child, this property generates Max Heap. Based
on this criteria, a heap can be of two types −

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap − Where the value of the root node is less than or equal to either of its children.

Max-Heap − Where the value of the root node is greater than or equal to either of its
children.
 P a g e | 37

Max Heap Construction Algorithm

The procedure to create Min Heap is similar but we go for min values instead of max values.

We are going to derive an algorithm for max heap by inserting one element at a time. At any
point of time, heap must maintain its property. While insertion, we also assume that we are
inserting a node in an already heapified tree.

Step 1 − Create a new node at the end of heap.

Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Note − In Min Heap construction algorithm, we expect the value of the parent node to be
less than that of the child node.

Let's understand Max Heap construction by an animated illustration. We consider the same
input sample that we used earlier

Max Heap Deletion Algorithm

Deletion in Max (or Min) Heap always happens at the root to remove the Maximum (or
minimum) value.
 P a g e | 38

Step 1 − Remove root node.

Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property hol

What is heap sort?

Heapsort is a popular and efficient sorting algorithm. The concept of heap sort is to
eliminate the elements one by one from the heap part of the list, and then insert them into
the sorted part of the list.

Heapsort is the in-place sorting algorithm.

Now, let's see the algorithm of heap sort.

Working of Heap sort Algorithm

Now, let's see the working of the Heapsort Algorithm.

In heap sort, basically, there are two phases involved in the sorting of elements. By using the
heap sort algorithm, they are as follows -
The first step includes the creation of a heap by adjusting the elements of the array.
After the creation of heap, now remove the root element of the heap repeatedly by shifting
it to the end of the array, and then store the heap structure with the remaining elements.

First, we have to construct a heap from the given array and convert it into max heap.
First, we have to construct a heap from the given array and convert it into max heap.
 P a g e | 39

After converting the given heap into max heap, the array elements are -

Next, we have to delete the root element (89) from the max heap. To delete this node, we
have to swap it with the last node, i.e. (11). After deleting the root element, we again have
to heapify it to convert it into max heap.

After swapping the array element 89 with 11, and converting the heap into max-heap, the
elements of array are -

In the next step, again, we have to delete the root element (81) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (54). After deleting the root
element, we again have to heapify it to convert it into max heap.
 P a g e | 40

After swapping the array element 81 with 54 and converting the heap into max-heap, the
elements of array are -

In the next step, we have to delete the root element (76) from the max heap again. To
delete this node, we have to swap it with the last node, i.e. (9). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 76 with 9 and converting the heap into max-heap, the
elements of array are -

In the next step, again we have to delete the root element (54) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (14). After deleting the root
element, we again have to heapify it to convert it into max heap.
 P a g e | 41

After swapping the array element 54 with 14 and converting the heap into max-heap, the
elements of array are -

In the next step, again we have to delete the root element (22) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (11). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 22 with 11 and converting the heap into max-heap, the
elements of array are -

In the next step, again we have to delete the root element (14) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (9). After deleting the root
element, we again have to heapify it to convert it into max heap.
 P a g e | 42

After swapping the array element 14 with 9 and converting the heap into max-heap, the
elements of array are -

In the next step, again we have to delete the root element (11) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (9). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 11 with 9, the elements of array are -

Now, heap has only one element left. After deleting it, heap will be empty.

After completion of sorting, the array elements are -

Now, the array is completely sorted.

Write a program to implement heap sort in C language.

#include <stdio.h>
/* function to heapify a subtree. Here 'i' is the
index of root node in array a[], and 'n' is the size of heap. */
void heapify(int a[], int n, int i)
{
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
// If left child is larger than root
if (left < n && a[left] > a[largest])
largest = left;
// If right child is larger than root
if (right < n && a[right] > a[largest])
largest = right;
// If root is not largest
 P a g e | 43

if (largest != i) {
// swap a[i] with a[largest]
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;

heapify(a, n, largest);
}
}
/*Function to implement the heap sort*/
void heapSort(int a[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
/* Move current root element to end*/
// swap a[0] with a[i]
int temp = a[0];
a[0] = a[i];
a[i] = temp;

heapify(a, i, 0);
}
}
/* function to print the array elements */
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("%d", arr[i]);
printf(" ");
}

}
int main()
{
int a[] = {48, 10, 23, 43, 28, 26, 1};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
heapSort(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
 P a g e | 44

Output:

The Trie Data Structure

Tries are made up of a set of nodes connected by pointers, which indicate parent-child
relationship between them. Each node can contain multiple branches, with each of the
branches representing a possible key character.

Let us consider a trie which stores strings of English alphabets, in this case we will have a
total 26 possible characters. In case of binary tries, we would have only 2 characters.

In the usual implementation, we have a blank root node which points to all other starting
characters of the set of strings, which then point to the corresponding next character.

So let us build a trie. Suppose we have a list of strings ,

List = { "study", "student", "stuff" , "ton", "tight" }

So we start with a blank node and point it to character 's'. Now we will keep on linking it to
the next characters until the end is reached, i.e., we finish the 'study' string. Now for
'student', we start from blank node, search if there is any 's' there. Since we already have
one, now we search if it has a connected node with character 't'. We proceed in the same
way and create a new node if we are not able to find an existing one.

Advantages of Tries:
 Faster search
 P a g e | 45

 Less Space
 Longest Prefix Matching

Disadvantages of Trie Data Structure:

 Slower than Hash tables while searching data.
 All key values cannot be represented as strings.

B Tree:
B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order
m can have at most m-1 keys and m children. One of the main reason of using B tree is its
capability to store large number of keys in a single node and large key values by keeping the
height of the tree relatively small.

A B tree of order m contains all the properties of an M way tree. In addition, it contains the
following properties.

Every node in a B-Tree contains at most m children.

Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.
The root nodes must have at least 2 nodes.
All leaf nodes must be at the same level.
It is not necessary that, all the nodes contain the same number of children but, each node
must have m/2 number of nodes.

A B tree of order 4 is shown in the following image.

Operations
Searching:
Searching in B Trees is similar to that in Binary search tree. For example, if we search for an
item 49 in the following B Tree.
The process will something like following:

 Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-tree.
 Since, 40<49<56, traverse right sub-tree of 40.
 49>45, move to right. Compare 49.
 P a g e | 46

 match found, return.

Searching in a B tree depends upon the height of the tree. The search algorithm takes O(log
n) time to search any element in a B tree.

Inserting:
Insertions are done at the leaf node level. The following algorithm needs to be followed in
order to insert an item into B Tree.

 Traverse the B Tree in order to find the appropriate leaf node at which the node can
be inserted.
 If the leaf node contain less than m-1 keys then insert the element in the increasing
order.
 Else, if the leaf node contains m-1 keys, then follow the following steps.
o Insert the new element in the increasing order of elements.
o Split the node into the two nodes at the median.
o Push the median element upto its parent node.
o If the parent node also contain m-1 number of keys, then split it too by
following the same steps.
Example:
Insert the node 8 into the B Tree of order 5 shown in the following image.

8 will be inserted to the right of 5, therefore insert 8.

 P a g e | 47

The node, now contain 5 keys which is greater than (5 -1 = 4 ) keys. Therefore split the node
from the median i.e. 8 and push it up to its parent node shown as follows.

Deletion
Deletion is also performed at the leaf nodes. The node which is to be deleted can either be a
leaf node or an internal node. Following algorithm needs to be followed in order to delete a
node from a B tree.

 Locate the leaf node.

 If there are more than m/2 keys in the leaf node then delete the desired key from
the node.
 If the leaf node doesn't contain m/2 keys then complete the keys by taking the
element from eight or left sibling.
o If the left sibling contains more than m/2 elements then push its largest
element up to its parent and move the intervening element down to the
node where the key is deleted.
o If the right sibling contains more than m/2 elements then push its smallest
element up to the parent and move intervening element down to the node
where the key is deleted.
 If neither of the sibling contain more than m/2 elements then create a new leaf node
by joining two leaf nodes and the intervening element of the parent node.
 If parent is left with less than m/2 nodes then, apply the above process on the parent
too.
If the the node which is to be deleted is an internal node, then replace the node with its in-
order successor or predecessor. Since, successor or predecessor will always be on the leaf
node hence, the process will be similar as the node is being deleted from the leaf node.

Example 1

Delete the node 53 from the B Tree of order 5 shown in the following figure.

53 is present in the right child of element 49. Delete it.

 P a g e | 48

Now, 57 is the only element which is left in the node, the minimum number of elements
that must be present in a B tree of order 5, is 2. it is less than that, the elements in its left
and right sub-tree are also not sufficient therefore, merge it with the left sibling and
intervening element of parent i.e. 49.

The final B tree is shown as follows.

Application of B tree:
B tree is used to index the data and provides fast access to the actual data stored on the
disks since, the access to value stored in a large database that is stored on a disk is a very
time consuming process.

Searching an un-indexed and unsorted database containing n key values needs O(n) running
time in worst case. However, if we use B Tree to index this database, it will be searched in
O(log n) time in worst case.

Graphs
A graph can be defined as group of vertices and edges that are used to connect these
vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any
complex relationship among them instead of having parent child relationship.
A graph is a pictorial representation of a set of objects where some pairs of objects are
connected by links. The interconnected objects are represented by points termed
as vertices, and the links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of
edges, connecting the pairs of vertices. Take a look at the following graph −
 P a g e | 49

In the above graph,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

Directed and Undirected Graph:

A graph can be directed or undirected. However, in an undirected graph, edges are not
associated with the directions with them. An undirected graph is shown in the above figure
since its edges are not attached with any of the directions. If an edge exists between vertex
A and B then the vertices can be traversed from B to A as well as A to B.
In a directed graph, edges form an ordered pair. Edges represent a specific path from some
vertex A to another vertex B. Node A is called initial node while node B is called terminal
node.
A directed graph is shown in the following figure.

Types of Graphs:
Null Graph, Trivial Graph, Non-directed Graph, Directed Graph, Connected Graph,
Disconnected Graph, Regular Graph, Complete Graph, Cycle Graph, Cyclic Graph, Acyclic
Graph, Finite Graph, Infinite Graph, Bipartite Graph, Planar Graph, Simple Graph, Multi
Graph, Pseudo Graph, Euler Graph &Hamiltonian Graph
Null Graph:
 A graph whose edge set is empty is called as a null graph.
 In other words, a null graph does not contain any edges in it.
Example-
 P a g e | 50

Here,
 This graph consists only of the vertices and there are no edges in it.
 Since the edge set is empty, therefore it is a null graph.

Connected Graph:
A graph in which we can visit from any one vertex to any other vertex is called as a
connected graph.
 In connected graph, at least one path exists between every pair of vertices.

Example-

Here,
 In this graph, we can visit from any one vertex to any other vertex.
 There exists at least one path between every pair of vertices.
 Therefore, it is a connected graph.

Disconnected Graph:
A graph in which there does not exist any path between at least one pair of vertices is called
as a disconnected graph.
Example
 P a g e | 51

Here,
 This graph consists of two independent components which are disconnected.
 It is not possible to visit from the vertices of one component to the vertices of other
component.
 Therefore, it is a disconnected graph.

Complete Graph:
 A graph in which exactly one edge is present between every pair of vertices is called as a
complete graph.
 A complete graph of ‘n’ vertices contains exactly nC2 edges.
 A complete graph of ‘n’ vertices is represented as Kn.
Examples:

In these graphs,
 Each vertex is connected with all the remaining vertices through exactly one edge.
 Therefore, they are complete graphs.
Cycle Graph:
 P a g e | 52

 A simple graph of ‘n’ vertices (n>=3) and n edges forming a cycle of length ‘n’ is called as a
cycle graph.
 In a cycle graph, all the vertices are of degree 2.
Examples

In these graphs,
 Each vertex is having degree 2.
 Therefore, they are cycle graphs.

Cyclic Graph:
 A graph containing at least one cycle in it is called as a cyclic graph.
Example:

Here,
 This graph contains two cycles in it.
 Therefore, it is a cyclic graph.

Acyclic Graph:
 A graph not containing any cycle in it is called as an acyclic graph.
Example:
 P a g e | 53

Here,
 This graph do not contain any cycle in it.
 Therefore, it is an acyclic graph.

Weighted Graph:
A weighted graph is a graph in which each branch is given a numerical weight. A weighted
graph is therefore a special type of labelled graph in which the labels are numbers

In degree, out degree, degree of node:

In a graph, the total number of edges incident on a node is called indegree of that node. The
total number of edges marking a node is called out degree. The sum of outdegree and
indegree is the total degree of a node in a graph.
Outdegree of node 2 is 1
Indegree of node 2 is 2
Total degree of node 2 is 3
Path:
Path in a graph is a finite or infinite sequence of edges which joins a sequence of
vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are
the edges).
Directed Path:
A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence
of edges which joins a sequence of distinct vertices, but with the added restriction that the
 P a g e | 54

edges be all directed in the same direction. Paths are fundamental concepts of graph
theory, described in the introductory sections of most graph theory texts.
Length of Graph:
The length of a path is the number of edges it contains. For a simple graph, a path is
equivalent to a trail and is completely specified by an ordered sequence of vertices.
Simple Path:
The path is said to be simple path if the edges in a path of graph are distinct.

Representation of Graph in Memory:

By Graph representation, we simply mean the technique which is to be used in order to
store some graph into the computer's memory.
There are two ways to store Graph into the computer’s memory. In this part of this tutorial,
we discuss each one of them in detail.
 Sequential Representation
 Linked Representation.
Sequential Representation:
In sequential representation, we use adjacency matrix to store the mapping represented by
vertices and edges. In adjacency matrix, the rows and columns are represented by the graph
vertices. A graph having n vertices, will have a dimension n x n.
An entry Mij in the adjacency matrix representation of an undirected graph G will be 1 if
there exists an edge between Vi and Vj.
An undirected graph and its adjacency matrix representation is shown in the following
figure.

In the above figure, we can see the mapping among the vertices (A, B, C, D, E) is represented
by using the adjacency matrix which is also shown in the figure.
There exists different adjacency matrices for the directed and undirected graph. In directed
graph, an entry Aij will be 1 only when there is an edge directed from Vi to Vj.
A directed graph and its adjacency matrix representation is shown in the following figure.
 P a g e | 55

Representation of weighted directed graph is different. Instead of filling the entry by 1, the
Non- zero entries of the adjacency matrix are represented by the weight of respective
edges.
The weighted directed graph along with the adjacency matrix representation is shown in the
following figure.

Linked Representation:
In the linked representation, an adjacency list is used to store the Graph into the computer's
memory.
Node list: it is a key value each element in a node list a node in graph.
Node Next adj
Edge List: each element will correspond to edge of graph G.
Dest link

Consider the undirected graph shown in the following figure and check the adjacency list
representation.
 P a g e | 56

An adjacency list is maintained for each node present in the graph which stores the node
value and a pointer to the next adjacent node to the respective node. If all the adjacent
nodes are traversed then store the NULL in the pointer field of last node of the list. The sum
of the lengths of adjacency lists is equal to the twice of the number of edges present in an
undirected graph.

Consider the directed graph shown in the following figure and check the adjacency list
representation of the graph.

In a directed graph, the sum of lengths of all the adjacency lists is equal to the number of
edges present in the graph.
In the case of weighted directed graph, each node contains an extra field that is called the
weight of the node. The adjacency list representation of a directed graph is shown in the
following figure.

Graph Traversal Algorithm:

 P a g e | 57

In this part, we will discuss the techniques by using which, we can traverse all the vertices of
the graph.
Traversing the graph means examining all the nodes and vertices of the graph. There are
two standard methods by using which, we can traverse the graphs. Let’s discuss each one of
them in detail.
o Breadth First Search
o Depth First Search
Breadth First Search (BFS) Algorithm:
Breadth first search is a graph traversal algorithm that starts traversing the graph from root
node and explores all the neighbouring nodes. Then, it selects the nearest node and explore
all the unexplored nodes. The algorithm follows the same process for each of the nearest
node until it finds the goal.
The algorithm of breadth first search is given below. The algorithm starts with examining the
node A and all of its neighbours. In the next step, the neighbours of the nearest node of A
are explored and process continues in the further steps. The algorithm explores all
neighbours of all the nodes and ensures that each node is visited exactly once and no node
is visited twice.
Algorithm:
o Step 1: SET STATUS = 1 (ready state)
for each node in G
o Step 2: Enqueue the starting node A
and set its STATUS = 2
(waiting state)
o Step 3: Repeat Steps 4 and 5 until
QUEUE is empty
o Step 4: Dequeue a node N. Process it
and set its STATUS = 3
(processed state).
o Step 5: Enqueue all the neighbours of
N that are in the ready state
(whose STATUS = 1) and set
their STATUS = 2
(waiting state)
[END OF LOOP]
o Step 6: EXIT

Example:
Consider the graph G shown in the following image, calculate the minimum path p from
node A to node E. Given that each edge has a length of 1.
 P a g e | 58

Solution:
Minimum Path P can be found by applying breadth first search algorithm that will begin at
node A and will end at E. the algorithm uses two queues,
namely QUEUE1 and QUEUE2. QUEUE1 holds all the nodes that are to be processed
while QUEUE2 holds all the nodes that are processed and deleted from QUEUE1.
Lets start examining the graph from Node A.
1. Add A to QUEUE1 and NULL to QUEUE2.
1. QUEUE1 = {A}
2. QUEUE2 = {NULL}
2. Delete the Node A from QUEUE1 and insert all its neighbours. Insert Node A into QUEUE2
1. QUEUE1 = {B, D}
2. QUEUE2 = {A}
3. Delete the node B from QUEUE1 and insert all its neighbours. Insert node B into QUEUE2.
1. QUEUE1 = {D, C, F}
2. QUEUE2 = {A, B}
4. Delete the node D from QUEUE1 and insert all its neighbours. Since F is the only
neighbour of it which has been inserted, we will not insert it again. Insert node D into
QUEUE2.
1. QUEUE1 = {C, F}
2. QUEUE2 = { A, B, D}
5. Delete the node C from QUEUE1 and insert all its neighbours. Add node C to QUEUE2.
1. QUEUE1 = {F, E, G}
2. QUEUE2 = {A, B, D, C}
6. Remove F from QUEUE1 and add all its neighbours. Since all of its neighbours has already
been added, we will not add them again. Add node F to QUEUE2.
1. QUEUE1 = {E, G}
2. QUEUE2 = {A, B, D, C, F}
7. Remove E from QUEUE1, all of E's neighbours has already been added to QUEUE1
therefore we will not add them again. All the nodes are visited and the target node i.e. E is
encountered into QUEUE2.
1. QUEUE1 = {G}
2. QUEUE2 = {A, B, D, C, F, E}
 P a g e | 59

Now, backtrack from E to A, using the nodes available in QUEUE2.

The minimum path will be A → B → C → E.

Depth First Search Traversal Algorithm:

Depth first search (DFS) algorithm starts with the initial node of the graph G, and then goes
to deeper and deeper until we find the goal node or the node which has no children. The
algorithm, then backtracks from the dead end towards the most recent node that is yet to
be completely unexplored.
The data structure which is being used in DFS is stack. The process is similar to BFS
algorithm. In DFS, the edges that leads to an unvisited node are called discovery edges while
the edges that leads to an already visited node are called block edges.

Algorithm:
o Step 1: SET STATUS = 1 (ready state) for each node in G
o Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)
o Step 3: Repeat Steps 4 and 5 until STACK is empty
o Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
o Step 5: Push on the stack all the neighbours of N that are in the ready state (whose
STATUS = 1) and set their
STATUS = 2 (waiting state)
[END OF LOOP]
o Step 6: EXIT

Example:
Consider the graph G along with its adjacency list, given in the figure below. Calculate the
order to print all the nodes of the graph starting from node H, by using depth first search
(DFS) algorithm.
 P a g e | 60

Solution:
Push H onto the stack
1. STACK : H
POP the top element of the stack i.e. H, print it and push all the neighbours of H onto the
stack that are is ready state.
1. Print H
2. STACK : A
Pop the top element of the stack i.e. A, print it and push all the neighbours of A onto the
stack that are in ready state.
1. Print A
2. Stack : B, D
Pop the top element of the stack i.e. D, print it and push all the neighbours of D onto the
stack that are in ready state.
1. Print D
2. Stack : B, F
Pop the top element of the stack i.e. F, print it and push all the neighbours of F onto the
stack that are in ready state.
1. Print F
2. Stack : B
Pop the top of the stack i.e. B and push all the neighbours
1. Print B
2. Stack : C
Pop the top of the stack i.e. C and push all the neighbours.
1. Print C
2. Stack : E, G
Pop the top of the stack i.e. G and push all its neighbours.
1. Print G
2. Stack : E
Pop the top of the stack i.e. E and push all its neighbours.
1. Print E
2. Stack :
Hence, the stack now becomes empty and all the nodes of the graph have been traversed.
The printing sequence of the graph will be :
1. H → A → D → F → B → C → G → E

Comparison between DFS & BFS:

 P a g e | 61

Sr. Key BFS DFS

No.

Definition BFS, stands for Breadth DFS, stands for Depth First
1
First Search. Search.

Data structure BFS uses Queue to find the DFS uses Stack to find the
2
shortest path. shortest path.

Source BFS is better when target is DFS is better when target is far
3
closer to Source. from source.

Suitability for As BFS considers all DFS is more suitable for decision
decision tree neighbour so it is not tree. As with one decision, we
4 suitable for decision tree need to traverse further to
used in puzzle games. augment the decision. If we
reach the conclusion, we won.

5 Speed BFS is slower than DFS. DFS is faster than BFS.

Time Time Complexity of BFS = Time Complexity of DFS is also

6 Complexity O(V+E) where V is vertices O(V+E) where V is vertices and E
and E is edges. is edges.