Data Structures and its
Application
Subject code: BCS304
1
4/5/2024 Dept of CSE
MODULE-4
TREES & GRAPH
2
4/5/2024 Dept of CSE
TREES
1. Binary Search Tree
Definition
Searching a Binary Search Tree
Inserting into a Binary Search Tree
Deleting from a Binary Search Tree
Height of a Binary Search Tree
Other Operations on Binary Search Tree
2. Selection Trees
3. Forests
Transforming Forest into Binary Search Tree
Forests Traversal
4. Set Representation
[Link] Binary Tree
3
4/5/2024 Dept of CSE
GRAPHS
1. Graph
Definition
Directed Graph
Undirected Graph
Set Representation of Graph
Restrictions ( Self loops and Multigraphs)
Complete Graph
Sub Graph
path
Cyclic and Acyclic Graph
Connected Component & Strongly Connected Component
2. Graph Representation
Adjacency Matrices
Adjacency Lists
Adjacency Multilists
3. Graph Operations
DFS (Depth First Search)
BFS (Breadth First Search)
Spanning Trees
4
4/5/2024 Dept of CSE
Definition of Binary Search Tree
5
4/5/2024 Dept of CSE
Operations on Binary Search Tree
6
4/5/2024 Dept of CSE
Inserting into a Binary Search Tree
Step 1: Create a node (called temp) and copy the item into the node.
Step 2: if the tree is empty then root will be null then, return the temp
itself.
Step 3: if the tree is not empty then point prev=Null and cur =root.
Step 4: if the item to be inserted is same as root then delete the temp.
no duplicate item is inserted.
Step 5: as long as cur is not null ,Obtain the
i. parent position ( prev=cur)
ii. Left child postion (item < cur->info) cur = cur->llink
iii. right position for the new node (item > cur->info)
cur = cur->rlink
Step 6: If the node to be inserted is less than parent then insert the item
to left side else insert the item to right side.
if( item<parent->info)
parent->llink=temp;
else
parent->rlink=temp;
Step 7: return the root.
7
4/5/2024 Dept of CSE
Inserting into a Binary Search Tree
8
4/5/2024 Dept of CSE
Searching in a Binary Search Tree
9
4/5/2024 Dept of CSE
Searching in a Binary Search Tree
10
4/5/2024 Dept of CSE
Searching in a Binary Search Tree
11
4/5/2024 Dept of CSE
Deleting from a Binary Search Tree
12
4/5/2024 Dept of CSE
Deleting from a Binary Search Tree
13
4/5/2024 Dept of CSE
Deleting from a Binary Search Tree
14
4/5/2024 Dept of CSE
Deleting from a Binary Search Tree
15
4/5/2024 Dept of CSE
Deleting from a Binary Search Tree
16
4/5/2024 Dept of CSE
Deleting from a Binary Search Tree
17
4/5/2024 Dept of CSE
Function to Delete an Item from BST
18
4/5/2024 Dept of CSE
19
4/5/2024 Dept of CSE
20
4/5/2024 Dept of CSE
Height of Binary Search Tree
21
4/5/2024 Dept of CSE
Other Operations on BST
22
4/5/2024 Dept of CSE
Find Maximum Value in BST
23
4/5/2024 Dept of CSE
Find Minimum Value in BST
24
4/5/2024 Dept of CSE
Count the number of nodes in BST
25
4/5/2024 Dept of CSE
Count the number of leaf nodes in BST
4/5/2024 Dept of CSE 26
Questions on Binary Search Tree
1. Construct a Binary Search Tree for the given set of values :
14,15,4,9,7,18,3,5,16,20 Also perform the inorder, preorder and post
order for the obtained Binary Search Tree [ 06 Marks]
2. Develop a C function to perform the following operations:
i. Iterative Search to search a key in a BST
ii. Delete an item in a BST [08 Marks}
3. Draw a BST for the given sequence of values :
51,60,5,34,12,47,68,18,54 and also write the recursive search function
to search an item in BST [ 06 Marks]
4. Write a c routine to insert an item into Binary Search Tree (BST) [4
Marks]
5. For the Given Data draw the Binary Search Tree:
100,85,45,55,110,20,70,65 and show the Array and Linked List
representation for the same [06 Marks]
4/5/2024 Dept of CSE 27
Questions on Binary Search Tree
6. Construct a Binary Search Tree using the following preorder and inorder
sequence Preorder: ABCDEFGHI Inorder: BCAEDGHFI [06 Marks]
7. Draw a Binary Search Tree for the following given sequence of input;
43 10 79 90 12 54 11 9 50 and also write the c function to search an
item in BST [10 Marks]
4/5/2024 Dept of CSE 28
Selection Tree
4/5/2024 Dept of CSE 29
Selection Tree
The Selection tree is a complete binary tree with n external nodes
and n – 1 internal nodes. The external nodes represent the
players, and the internal nodes are representing the winner of the
match between the two players. This tree is also known as
Tournament tree.
Types of Selection/Tournament Tree
There exist a loser and a winner in every match. So, there are two
methods to represent both ideas:
1. Winner Tree
2. Loser Tree
4/5/2024 Dept of CSE 30
Winner Tree
In a Selection/tournament tree, when the internal nodes
represent the winner of the match, the tree obtained is referred to
as the winner tree.
Each internal node stores either the smallest or greatest of
its children, depending on the winning criteria.
When the winner is the smaller value then the winner tree
is referred to as the minimum winner tree
when the winner is the larger value, then the winner tree
is referred to as the maximum winner tree.
4/5/2024 Dept of CSE 31
Example: Maximum winner Tree
Eight players participate in a tournament where a number
represents each player, from 1 to 8. The pairings of these
players are given below:
Group A: 1, 3, 5, 7 (Matches: 1 - 7 and 3 – 5)
Group B: 2, 4, 6, 8 (Matches: 2 - 6, and 4 - 8)
Winning Criteria - The player having the maximum value wins
the match. Represent the winner tree (maximum winner tree)
for this tournament tree.
The winner tree (maximum winner tree) is represented below in
the figure:
4/5/2024 Dept of CSE 32
Loser Tree
In a Selection/tournament tree, when the internal nodes are used
to represent the loser of the match between two, then the tree
obtained is referred to as the loser tree.
When the loser is the smaller value then the loser tree is
referred to as the minimum loser tree
when the loser is the larger value, then the loser tree is
referred to as the maximum loser tree.
4/5/2024 Dept of CSE 33
Example: Minimum looser Tree
Eight players participate in a tournament where a number
represents each player, from 1 to 8. The pairings of these
players are given below:
Group A: 1, 3, 5, 7 (Matches: 1 - 7 and 3 – 5)
Group B: 2, 4, 6, 8 (Matches: 2 - 6, and 4 - 8)
Winning Criteria - The player having the minimum value wins
the match. Represent the Looser tree (minimum loser tree)
for this tournament tree.
The loser tree (minimum looser tree) is represented below in the
figure:
4/5/2024 Dept of CSE 34
Applications of Selection Tree
It can find the maximum or minimum value in an
array.
It is generally used in sorting.
It can be used in M-way merges.
It is used to find the median of the sorted array
It is also used in the truck loading problem
4/5/2024 Dept of CSE 35
Forests
4/5/2024 Dept of CSE 36
Forests
Forests : Forests is a collection of zero/more disjoint trees.
The below diagram/figure shows the forests with three trees
4/5/2024 Dept of CSE 37
Transforming a Forest into Binary Tree
In order to transfer the forests into a Binary Tree we follow the
following steps.
Step1: Obtain the Binary tree representation of each disjoint tree in
the forest.
Step2: link all the binary trees together through the sibling field of
the root node.
Example: Convert the following Forest into a Binary Tree
4/5/2024 Dept of CSE 38
Step1: Obtain the Binary tree representation of each disjoint tree in
the forest.
4/5/2024 Dept of CSE 39
Step2: link all the binary trees together through the sibling field of
the root node.
4/5/2024 Dept of CSE 40
Forests Traversals
4/5/2024 Dept of CSE 41
COUNTING BINARY TREES
4/5/2024 Dept of CSE 42
COUNTING BINARY TREE
Counting Binary Trees: In this we are going to count
the distinct Binary trees present in a given Binary Tree.
Consider the three problems:
1. Number of distinct binary trees with n Nodes.
2. The number of distinct permutations of the numbers from 1to
n obtainable by a stack.
3. The number of distinct ways of multiplying n + 1 matrices.
4/5/2024 Dept of CSE 43
COUNTING BINARY TREE
Distinct Binary Trees: We know that
if n = 0 or n = 1, there is only one binary tree.
if n = 2, then there are two distinct trees .
if n = 3, there are five such trees.
How many distinct trees are there with n nodes? So in general
C(n) = (2n)! / ((n+1)! * n!)
The below diagram shows the distinct binary trees when n=2 and n=3
4/5/2024 Dept of CSE 44
Stack Permutation: We know that we can construct the
binary tree if the preorder and Inorder is given.
Example: consider the following preorder and inorder sequence.
Preorder : ABCDEFGHI
Inorder: BCAEDGHFI
The binary tree for the above sequence is
4/5/2024 Dept of CSE 45
Let the nodes of an n node binary tree be numbered from 1 to n.
The inorder permutation defined by such a binary tree is the
order in which its nodes are visited during an inorder traversal of
the tree. A preorder permutation is similarly defined.
If the nodes of the tree are numbered such that its preorder
permutation is 1, 2, • • • ,n, then from our earlier discussion it
follows that distinct binary trees define distinct inorder
permutations. Thus, the number of distinct binary trees is equal
to the number of distinct inorder permutations obtainable from
binary trees having the preorder permutation, 1,2, • • • n.
4/5/2024 Dept of CSE 46
Using the concept of an inorder permutation, we can show that
the number of distinct permutations obtainable by passing the
numbers 1 to n through a stack and deleting in all possible ways
is equal to the number of distinct binary trees with n nodes.
Example:. If we start with the numbers 1, 2, 3, then the possible
permutations obtainable by a stack are:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 2, 1)
Obtaining (3, 1, 2) is impossible. Each of these five permutations
corresponds to one of the five distinct binary trees with three
nodes
4/5/2024 Dept of CSE 47
4/5/2024 Dept of CSE 48
Matrix Multiplication: In this we wish to compute the
product of n matrices.
M1 * M 2 * • • • * Mn
Since matrix multiplication is associative, we can perform these
multiplications in any order. We would like to know how many
different ways we can perform these multiplications. For example,
if n = 3, there are two possibilities:
M1 * (M 2 * M3)
( M1 * M 2) * M3
4/5/2024 Dept of CSE 49
4/5/2024 Dept of CSE 50
4/5/2024 Dept of CSE 51
GRAPHS
1. Graph
Definition
Directed Graph
Undirected Graph
Set Representation of Graph
Restrictions ( Self loops and Multigraphs)
Complete Graph
Sub Graph
path
Cyclic and Acyclic Graph
Connected Component & Strongly Connected Component
2. Graph Representation
Adjacency Matrices
Adjacency Lists
3. Graph Operations (GRAPH TRAVERSAL)
DFS (Depth First Search)
BFS (Breadth First Search)
Spanning Trees
52
4/5/2024 Dept of CSE
Definition of Graph
53
4/5/2024 Dept of CSE
Directed Graph/ Diagraph
54
4/5/2024 Dept of CSE
Undirected Graph
55
4/5/2024 Dept of CSE
Set Representation of Graph
56
4/5/2024 Dept of CSE
Self Loop and Multi Graph
57
4/5/2024 Dept of CSE
Complete Graph
58
4/5/2024 Dept of CSE
Sub Graph
59
4/5/2024 Dept of CSE
Path
60
4/5/2024 Dept of CSE
Cyclic and Acyclic Graph
61
4/5/2024 Dept of CSE
Connected & Strongly
Connected Component
62
4/5/2024 Dept of CSE
Connected Component
63
4/5/2024 Dept of CSE
Connected Component
64
4/5/2024 Dept of CSE
Strongly Connected Component
65
4/5/2024 Dept of CSE
Degree of a Vertex in a Undirected Graph
In the given graph the degree of
deg(1) = 2
deg(2) = 1
deg(3) = 1
deg(4) = 1
deg(5) = 2
deg(6)= 3
deg(7) = 1
deg(8) = 3
66
4/5/2024 Dept of CSE
Degree of a Vertex in a Directed Graph
In a directed graph there are two types of degrees
1. In-degree
[Link] degree
In-degree: The number of edges that are incoming towards the vertex is in-degree
of a vertex.
Out-degree: The number of edges that are emerging from a vertex are called the
out-degree of a vertex
Degree of a vertex in Directed Graph : is the total number of indegree + outdegree
deg(V) = indeg(v) + outdeg(v)
In a given graph :
Indegree of vertex 4 = 1
out degree of vertex 4 = 1
Degree of vertex 4 = 1+ 1 that is 2.
67
4/5/2024 Dept of CSE
GRAPH REPRESENTATION
68
4/5/2024 Dept of CSE
GRAPH REPRESENTATION
69
4/5/2024 Dept of CSE
EXAMPLE OF ADJACENCY MATRICES
70
4/5/2024 Dept of CSE
ADJACENCY LINKED LIST
71
4/5/2024 Dept of CSE
EXAMPLE OF ADJACENCY LINKED LIST
72
4/5/2024 Dept of CSE
COST ADJACENCY MATRIX
73
4/5/2024 Dept of CSE
DIRECTED WEIGHTED COST ADJACENCY MATRICES
74
4/5/2024 Dept of CSE
UNDIRECTED WEIGHTED COST ADJACENCY MATRICES
75
4/5/2024 Dept of CSE
COST ADJACENCY LINKED LIST
76
4/5/2024 Dept of CSE
COST ADJACENCY LINKED LIST
77
4/5/2024 Dept of CSE
EXAMPLE OF COST ADJACENCY LINKED LIST
78
4/5/2024 Dept of CSE
INCIDENCE MATRICES
79
4/5/2024 Dept of CSE
INCIDENCE MATRICES FOR UNDIRECTED GRAPH
The incidence matrix A of an undirected graph has a row for each vertex
and a column for each edge of the graph.
The element A[[i,j]] of A is 1 if the ith vertex is a vertex of the jth edge and 0
otherwise.
The incidence matrix A of a directed graph has a row for each vertex and
a column for each edge of the graph.
80
4/5/2024 Dept of CSE
INCIDENCE MATRICES FOR DIRECTED GRAPH
The incidence matrix A of a directed graph has a row for each vertex and
a column for each edge of the graph.
The entries of incidence matrix is always -1, 0, +1. This matrix is always
analogous to KCL (Krichoff Current Law). Thus from KCL we can derive
that,
81
4/5/2024 Dept of CSE
GRAPH OPERATIONS/GRAPH
TRAVERSAL
[Link]
[Link]
82
4/5/2024 Dept of CSE
GRAPH TRVERSAL and BREADTH FIRST SEARCH
83
4/5/2024 Dept of CSE
BREADTH FIRST SEARCH
84
4/5/2024 Dept of CSE
BREADTH FIRST SEARCH
85
4/5/2024 Dept of CSE
BREADTH FIRST SEARCH
86
4/5/2024 Dept of CSE
ALGORITHM FOR BREADTH FIRST SEARCH
87
4/5/2024 Dept of CSE
DEPTH FIRST SEARCH
88
4/5/2024 Dept of CSE
DEPTH FIRST SEARCH
89
4/5/2024 Dept of CSE
ALGORITHM FOR DEPTH FIRST SEARCH
90
4/5/2024 Dept of CSE
SPANNING TREE
A spanning tree is a subset of Graph G, such that all the vertices are
connected using minimum possible number of edges. Hence, a spanning
tree does not have cycles and a graph may have more than one spanning
tree.
91
4/5/2024 Dept of CSE
PROPERTIES OF SPANNING TREE
A Spanning tree does not exist for a disconnected graph.
For a connected graph having N vertices then the number of
edges in the spanning tree for that graph will be N-1.
A Spanning tree does not have any cycle.
We can construct a spanning tree for a complete graph by
removing E-N+1 edges, where E is the number of Edges
and N is the number of vertices.
Cayley’s Formula: It states that the number of spanning trees
in a complete graph with N vertices is
N N-2
For example: N=4, then maximum number of spanning tree
possible == 16 .
92
4/5/2024 Dept of CSE
MINIMUM SPANNING TREE
A minimum spanning tree (MST) is defined as a spanning tree
that has the minimum weight among all the possible spanning
trees.
93
4/5/2024 Dept of CSE