Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

UNIT IV

Graphs: Definition, Terminology, Representation, Traversal.

Trees: Definition, Terminology, Binary Trees, Traversal of Binary Tree,

Binary Search Tree, Inserting, Deleting and Searching in Binary Search Tree

Introduction to Graph Data Structure

Graph Data Structure is a non-linear data structure consisting of
vertices and edges. It is useful in fields such as social network analysis,
recommendation systems, and computer networks. In the field of sports
data science, graph data structure can be used to analyze and
understand the dynamics of team performance and player interactions
on the field.

Graph is a non-linear data structure consisting of vertices and edges. The

vertices are sometimes also referred to as nodes and the edges are lines or
arcs that connect any two nodes in the graph. More formally a Graph is
composed of a set of vertices( V ) and a set of edges( E ). The graph is
denoted by G(V, E).

Components of Graph Data Structure

 Vertices: Vertices are the fundamental units of the graph. Sometimes,
vertices are also known as vertex or nodes. Every node/vertex can be
labeled or unlabelled.
 Edges: Edges are drawn or used to connect two nodes of the graph. It
can be ordered pair of nodes in a directed graph. Edges can connect any
two nodes in any possible way. There are no rules. Sometimes, edges are
also known as arcs. Every edge can be labelled/unlabelled.

Prepared By: Mr.A.M Saudagar UNIT-IV 1 / 16

Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

Basic Graph Terminology:

1. Graph

A graph ‘G’ is defined as G = (V, E) Where V is a set of all vertices and E is a set
of all edges in the graph.

Example 1

In the above example, ab, ac, cd, and bd are the edges of the graph. Similarly,
a, b, c, and d are the vertices of the graph.

2. Vertex (Node)

A vertex is a point where multiple lines meet. It is also called a node. Similar
to points, a vertex is also denoted by an alphabet.

Example

Here, the vertex is named with an alphabet ‘a’.

3. Edge

An edge is the mathematical term for a line that connects two vertices. Many
edges can be formed from a single vertex. Without a vertex, an edge cannot
be formed. There must be a starting vertex and an ending vertex for an edge.

Example

Prepared By: Mr.A.M Saudagar UNIT-IV 2 / 16

Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

Here, ‘a’ and ‘b’ are the two vertices and the link between them is called an
edge.

4. Degree of a Vertex
The Degree of a Vertex in a graph is the number of edges incident to that
vertex. In a directed graph, the degree is further categorized into the in-
degree (number of incoming edges) and out-degree (number of outgoing
edges) of the vertex.
5. Path
A Path in a graph is a sequence of vertices where each adjacent pair is
connected by an edge. Paths can be of varying lengths and may or may not
visit the same vertex more than once. The shortest path between two
vertices is of particular interest in algorithms such as Dijkstra's algorithm
for finding the shortest path in weighted graphs.
6. Cycle
A Cycle in a graph is a path that starts and ends at the same vertex, with
no repetitions of vertices (except the starting and ending vertex, which are
the same). Cycles are essential in understanding the connectivity and
structure of a graph and play a significant role in cycle detection algorithms.

Representations of Graph
Here are the two most common ways to represent a graph.
1.Adjacecy Matrix.
2. Adjacency list.

1. Adjacency Matrix :

An adjacency matrix is a way of representing a graph as a matrix

of boolean (0's and 1's)

Let's assume there are n vertices in the graph So, create a 2D

matrix adjMat[n][n] having dimension n x n.
 If there is an edge from vertex i to j, mark adjMat[i][j] as 1.
 If there is no edge from vertex i to j, mark adjMat[i][j] as 0.

An undirected graph and its adjacency matrix representation is shown in the

following figure.

Prepared By: Mr.A.M Saudagar UNIT-IV 3 / 16

Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

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.

Prepared By: Mr.A.M Saudagar UNIT-IV 4 / 16

Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

2. Adjacency List (Adjacency List Representation)

An array of Lists is used to store edges between two vertices. The size of
array is equal to the number of vertices (i.e, n). Each index in this array
represents a specific vertex in the graph. The entry at the index i of the
array contains a linked list containing the vertices that are adjacent to
vertex i.
Let's assume there are n vertices in the graph So, create an array of list of
size n as adjList[n].
 adjList[0] will have all the nodes which are connected (neighbour) to
vertex 0.
 adjList[1] will have all the nodes which are connected (neighbour) to
vertex 1 and so on.
Representation of Undirected Graph as Adjacency list:
The below undirected graph has 3 vertices. So, an array of list will be
created of size 3, where each indices represent the vertices. Now, vertex 0
has two neighbours (i.e, 1 and 2). So, insert vertex 1 and 2 at indices 0 of
array. Similarly, For vertex 1, it has two neighbour (i.e, 2 and 0) So, insert
vertices 2 and 0 at indices 1 of array. Similarly, for vertex 2, insert its
neighbours in array of list.

Representation of Directed Graph as Adjacency list:

The below directed graph has 3 vertices. So, an array of list will be created
of size 3, where each indices represent the vertices. Now, vertex 0 has no
neighbours. For vertex 1, it has two neighbour (i.e, 0 and 2) So, insert
vertices 0 and 2 at indices 1 of array. Similarly, for vertex 2, insert its
neighbours in array of list.

Prepared By: Mr.A.M Saudagar UNIT-IV 5 / 16

Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

Graphs Traversal:

To traverse a Graph means to start in one vertex, and go along the edges to
visit other vertices until all vertices, or as many as possible, have been visited.

The two most common ways a Graph can be traversed are:

 Depth First Search (DFS)

 Breadth First Search (BFS)

DFS is usually implemented using a Stack or by the use of recursion (which

utilizes the call stack), while BFS is usually implemented using a Queue.

Depth First Search (DFS)

Depth First Search or DFS traverses the graph vertically. It starts with the
root node or the first node of the graph and traverses all the child nodes
before moving to the adjacent nodes.

Example

Prepared By: Mr.A.M Saudagar UNIT-IV 6 / 16

Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

Traversing the above graph in BFS fashion would result from A -> B -> E -> F -
> C -> G -> D. The algorithm starts from node A and traverses all its child
nodes. As soon as it encounters B, it seems that it has further child nodes. So,
the child nodes of B are traversed before proceeding to the next child node of
A.

Breadth-First Search (BFS)

This is a traversal operation in the graph. BFS horizontally traverses the

graph. This means that it traverses all the nodes at a single level before
proceeding to the next level.
The BFS algorithm starts at the top of the first node in the graph and then
traverses all the adjacent nodes to it. Once all the adjacent nodes are
traversed, the algorithm repeats the same procedure for child nodes.

Example

Prepared By: Mr.A.M Saudagar UNIT-IV 7 / 16

Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

Traversing the above graph in BFS fashion would result from A -> B -> C -> D
-> E -> F -> G. The algorithm starts from node A and traverses all its adjacent
nodes B, C and D. It marks all the four nodes as visited. Once all the adjacent
nodes of A are traversed, the algorithm moves to the first adjacent node of A
and repeats the same procedure. In this case, the node is B, and the adjacent
nodes to B are E and F. Next, the adjacent nodes to C are traversed. Once all
the nodes are visited, the operation ends.

Trees:
Tree is a non-linear data structure. This structure is mainly used to
represent data containing a hierarchy or hierarchical relationship
between elements.
Ex.: Records, tables & family tree.
 Binary Trees :
- A binary tree T is defined as a finite set of elements, called nodes,
such that:
a) T is empty (called null tree or empty tree), or
b) T contains a distinguished node R, called the root of T and
the remaining nodes of T form an ordered pair of disjoint
binary trees T1 & T2.

Prepared By: Mr.A.M Saudagar UNIT-IV 8 / 16

Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

- If binary tree T does contain a root R, then two trees T1 and T2

are called left and right sub trees of R respectively.
- If T1 is non-empty then its root is called left successor of R.
- Similarly, if T2 is non-empty then its root is called the right
successor of R.
- Consider following binary tree:
A

C
B

E
D H
G

F
K
J

- The binary tree T represents as follows:

i. T consists of 11 nodes, represented by the letters A to L,
excluding I.
ii. The root node of T is the node A at the top of diagram.
iii. A left downward slanted line from a node N indicates a left
successor of node N, and right downward slanted from N
indicated right successor of N.
- In above tree observe that,
a) B is a left successor and C is a right successor of node A.
b) The left sub tree of root A consists of the nodes B, D, E & F
and right sub tree of A consists of the nodes C, G, H, J, K & L.

Prepared By: Mr.A.M Saudagar UNIT-IV 9 / 16

Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

- Any node N in binary tree T may have 0, 1 & 2 successors. The

nodes with no successor are called Terminal nodes.
- In above tree T, the nodes A, B, C, H has two successors & the
node E, J, has one successors and the node D, F, G, K & L has no
successor. Hence, these are terminal nodes.
- Binary tree T & T1 is said to be similar if they have similar
structure set.

A E

Fig. T Fig. T1
B F

D G H
C

- The binary tree T and T1 is said to be copies if they are some

value of node.

 Tree Terminology :
- In tree terminology, the relationship between the node of the tree
is described using three ways:
1. Family relationship.
2. Graph theory.
3. Horticulture concept.
1. Family Relationship :-
- Suppose N is a node in T with left successor S1 and right
successor S2.
- Then N is called the parent (or father) of S1 and S2. S1 and S2 are
called left and right child of N.
Prepared By: Mr.A.M Saudagar UNIT-IV 10 / 16
Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

- Furthermore, S1 and S2 are said to be siblings (brothers). Every

node N in a binary tree T, except the root, has a unique parent,
called the predecessor of node N.
- If node L is child of node N, then node L is said/called descendant
of node N, and N is called an ancestor of L.
- Here, node L may be left or right descendant of N according to
location in sub tree of root N.
2. Graph Theory :
- A line drawn from a node N of T to a successor is called an edge
and a sequence of consecutive edge is called a path.
3. Horticulture Concept :
- A terminal node is called a leaf and a path ending in a leaf is
called branch.
- Note: the depth (height) of a tree T is the maximum number of
nodes in branch of tree.
- Ex.: Consider a following tree.

1
A

2
B C

3
G H

J K 4

L 5

The above tree has depth = 5.

Prepared By: Mr.A.M Saudagar UNIT-IV 11 / 16

Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

 Traversing Binary Tree:-

- Traversing is one of the common data structure function which is
perform on a tree to process or visit each node of the tree exactly
once in a systematic manner.
- There are mainly three standard way used to traverse given
binary tree T with root B.
- These three ways are,
1. Preorder Traversing.
2. Inorder Traversing.
3. Postorder Traversing.
- For detail study of above traversal methods, consider a following
binary tree.

B D

E E G
C

1. Preorder Traversing :-
- This traversing method works on follows,
I. Process the Root node R.
II. Traverse the left sub tree of R in preorder.
III. Traverse the right sub tree of R in preorder.
- Also this traversing method is called node-left-right (N-L-R)
traversal.
- The preorder traversal of given tree T shown in above fig. is, A B
C D E F G.
Prepared By: Mr.A.M Saudagar UNIT-IV 12 / 16
Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

2. Inorder Traversal :-
- This traversing method works as follows,
I. Traverse the left sub tree of R in inorder.
II. Process the root R.
III. Traverse the right sub tree of R in inorder.
- Also this traversing method is called left-node-right (L-N-R)
traversal.
- The inorder traversal of given tree T shown in above figure is, C
B A E F D G.

3. Postorder Traversal :-
- This traversing method works as follows,
I. Traverse the left sub tree of R in postorder.
II. Travers the right sub tree of R in postorder.
III. Process the root node R.
- Also this traversing method is also called left-right-node (L-R-N)
traversal.
- The postorder traversal of given tree T shown in above figure is,
C B F E G D A.

Binary Search Tree (BST):

Binary Search Tree is a data structure used in computer science for

organizing and storing data in a sorted manner. Binary search tree follows
all properties of binary tree and for every nodes, its left subtree contains
values less than the node and the right subtree contains values greater than
the node.
This hierarchical structure allows for efficient Searching, Insertion,
and Deletion operations on the data stored in the tree.

Prepared By: Mr.A.M Saudagar UNIT-IV 13 / 16

 Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

Properties of Binary Search Tree:

 The left subtree of a node contains only nodes with keys less than the
node’s key.
 The right subtree of a node contains only nodes with keys greater
than the node’s key.
 The left and right subtree each must also be a binary search tree.
 There must be no duplicate nodes(BST may have duplicate values
with different handling approaches).

Operations on a Binary Search Tree:

1. Search:
The search operation in a BST can be performed efficiently by leveraging the
ordered structure of the tree. Starting from the root, you compare the
search value with the node's value. If the search value is less than the node's
value, you move to the left subtree. If it's greater, you move to the right
subtree. If the search value is found, you have located the node. If you reach
a leaf node without finding the value, the value is not in the tree.
Algorithm to search for a key in a given Binary Search Tree:
1. Let's say we want to search for the number X, We start at the root.
Then:
2. We compare the value to be searched with the value of the root.

Prepared By: Mr.A.M Saudagar UNIT-IV 14 / 16

 Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

o If it's equal we are done with the search if it's smaller we know
that we need to go to the left subtree because in a binary search
tree all the elements in the left subtree are smaller and all the
elements in the right subtree are larger.
3. Repeat the above step till no more traversal is possible
4. If at any iteration, key is found, return True. Else False.

2. Insertion:
To insert a new value, you start from the root and compare the new value
with the node's value. If the new value is less, you move to the left subtree. If
it's greater, you move to the right subtree. This process continues until you
reach a leaf node, where you insert the new value as a child of that node.
Example:
Given a BST, the task is to insert a new node in this BST.

How to Insert a value in a Binary Search Tree:

A new key is always inserted at the leaf by maintaining the property of the
binary search tree. We start searching for a key from the root until we hit a
leaf node. Once a leaf node is found, the new node is added as a child of the
leaf node. The below steps are followed while we try to insert a node into a
binary search tree:
 Initilize the current node (say, currNode or node) with root node
 Compare the key with the current node.
 Move left if the key is less than or equal to the current node value.
Prepared By: Mr.A.M Saudagar UNIT-IV 15 / 16
 Class: BCAFY(Sem II) COCSIT, Latur Sub: Data Structures

 Move right if the key is greater than current node value.

 Repeat steps 2 and 3 until you reach a leaf node.
 Attach the new key as a left or right child based on the comparison
with the leaf node's value.

3. Deletion:
Deleting a node in a BST involves different cases depending on whether the
node has one or two children. If the node has no children (a leaf node), you
can simply remove it. If it has one child, you can replace the node with its
child. If it has two children, you need to find the inorder successor or
predecessor of the node and replace it with that value, then delete the
successor or predecessor.

Prepared By: Mr.A.M Saudagar UNIT-IV 16 / 16