UNIT IV

GRAPH
A graph G consists of a set V of vertices (nodes) and a set E of edges (arcs). We write G= (V, E),V is a
finite and nom empty set of vertices. E is a set of pairs of vertices, these pairs are called edges.
An edge e=(v, w) is a pair of vertices v and w and is said to be incident with v and [Link] shows a
sample graph, for which V (G) = {v1,v2,v3,v4,v5} and E (G) = (e1, e2, e3, e4, e5}.

A graph may be pictorially also represented as:

We have numbered the nodes as 1, 2, 3, 4 and 5. Therefore V
(G)=(1,2,3, 4, 5) E (G) = {(1,2), (2, 4), (2, 3), (1, 4), (1, 5), (4, 5),
(3,4)} .

In an undirected graph, pair of vertices representing any edge is unordered. Thus (v, w) and (w, v)
represent the same edge. In the directed graph each edge is an ordered pair of vertices i.e., each edge is
represented by a directed pair. If e = (v, w), then v is initial vertex and w is the final vertex. Subsequently
(v, w) and (w, v) represent two different edges. A directed graph may be pictorially. represented as in
Fig

BASIC TERMINOLOGY
Adjacent Vertices: Vertex v1 is said to be adjacent to a vertex v2 if there is an edge (v1, v2) or
(v2, v1).
Let us consider graph in Fig
.

Vertices adjacent to node 2 are 1 and 3 and that to node 4 are 1, 3, 6 and 5.
Path: A path from vertex w is a sequence of vertices, each adjacent to the next. Consider the above
example again 1, 2, 3 is a path and 1, 4 and 3 is also a path.
Cycle: A cycle is a path in which first and last vertices are the same. In the above example (1, 2, 3, 4, 1)
is a cycle.
Connected graph: A graph is called connected if there exists a path from any vertex to any other vertex.
Consider the graph in Fig.

It is an unconnected graph having two unconnected components.

In a digraph the path is called a directed path and cycle is called as directed cycle.
A digraph is called strongly connected if there is a directed path from any vertex to any other
Degree: The number of edges incident on a vertex determine its degree. The degree of vertex u, is written
as degree (u). If degree (u) =0, this means that vertex u does not belong to any edge, then vertex u is
called isolated vertex.
In a Directed graph (Digraph), we attach an in degree and an out degree to each of the vertices.
Complete Graph: A graph G is said to complete or fully connected if there is an edge from every vertex
to every other vertex. A complete graph with n vertices will have 1 (n-1)/2 edges.
Weighted Graph: A graph is said to be weighted graph if every edge in the graph is assigned some
weight or value. The weight of the edge is a positive value that may be representing the cost of moving
along the edge or distance between the vertices.
In the above figure we mentioned the distance between Agra and Bharatpur as 45 km and Agra and
Mathura is 53 km.
TREE
A tree is a very popular non-linear hierarchical data structure used in a wide range of applications. A
tree is a collection of nodes(data items) connected to each other by means of edges which are either
directed or undirected. One of the node in tree is designated as root node and the remaining nodes are
called child nodes or leaf nodes.
In a tree data structure, if we have N number of nodes then we can have a maximum of N-1 number of
links or edges.
A tree is a connected graph without any circuits.
OR
If in a graph, there is one and only one path between every pair of vertices, then graph is called as a tree.

Properties-
The important properties of tree data structure are-
 There is one and only one path between every pair of vertices in a tree.
 A tree with n vertices has exactly (n-1) edges.
 A graph is a tree if and only if it is minimally connected.
 Any connected graph with n vertices and (n-1) edges is a tree.
Tree Terminology-
The important terms related to tree data structure are-
Root: The first node from where the tree originates is called as a root node. In any tree, there must be
only one root node. We can never have multiple root nodes in a tree data structure.
Example-

edge

Figure :1
Here, node A is the only root node.
Edge: The connecting link between any two nodes is called as an [Link] a tree with n number of nodes,
there are exactly (n-1) number of edges.
Parent: The node which has one or more children is called as a parent [Link] a tree, a parent node can
have any number of child nodes.
Example- In figure 1, Node A is the parent of nodes B and C, Node B is the parent of nodes D, E and
F, Node C is the parent of nodes G and H, Node E is the parent of nodes I and J, Node G is the parent of
node K
Child: The node which is a successor of some node is called as a child [Link] the nodes except root
node are child nodes.
Example- Nodes B and C are the children of node A in figure 1
Siblings: Children’s of the same parent are termed as siblings.
Example- Nodes B and C are siblings, Nodes D, E and F are siblings in fig 1
Degree- Degree of a node is the total number of children of that node. Degree of a tree is the highest
degree of a node among all the nodes in the tree.
Degree of node A = 2 Degree of node B = 3 Degree of node C = 2 in fig 1
Internal Node: The node which has at least one child is called as an internal node. Internal nodes are
also called as non-terminal nodes. Every non-leaf node is an internal node.
In fig 1 , nodes A, B, C, E and G are internal nodes.
Leaf Node: The node which does not have any child is called as a leaf node. Leaf nodes are also called
as external nodes or terminal nodes.
Here, nodes D, I, J, F, K and H are leaf nodes in fig 1.
Level: Level of a node represent the generation of the node. In a tree, each step from top to bottom is
called as level of a tree. The root node is at level 0 and increments by 1 at each level or step.
Example-
Height: Total number of edges that lies on the longest path from any leaf node to a particular node is
called as height of that node.
Height of a tree is the height of root node.
Height of all leaf nodes = 0
Example-

Here,
Height of node A = 3 Height of node B = 2 Height of node C = 2 Height of node D = 0
Height of node E = 1 Height of node F = 0 Height of node G = 1 Height of node H = 0
Height of node I = 0 Height of node J = 0 Height of node K = 0
Depth: Total number of edges from root node to a particular node is called as depth of that node.
Depth of a tree is the total number of edges from root node to a leaf node in the longest path.
Depth of the root node = 0
The terms “level” and “depth” are used interchangeably.
Example-

Here,
Depth of node A = 0 Depth of node B = 1 Depth of node C = 1 Depth of node D = 2
 Depth of node E = 2 Depth of node F = 2 Depth of node G = 2 Depth of node H = 2
Depth of node I = 3 Depth of node J = 3 Depth of node K = 3
Sub tree : In a tree, each child from a node forms a sub tree recursively. Every child node forms a sub
tree on its parent node.
Example-

Forest: A forest is a set of disjoint trees.

Example-

BINARY TREE
In a normal tree, every node can have any number of children. A binary tree is a special type of tree data
structure in which every node can have a maximum of 2 children. One is known as a left child and the
other is known as right child.
A tree in which every node can have a maximum of two children is called Binary Tree.
In a binary tree, every node can have either 0 children or 1 child or 2 children but not more than 2
children.
Example

There are different types of binary trees and they are...

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

2. Complete Binary Tree

In complete binary tree all the nodes must have exactly two children and at every level of complete
binary tree there must be 2level number of nodes. For example at level 2 there must be 22 = 4 nodes and
at level 3 there must be 23 = 8 nodes.
A binary tree in which every internal node has exactly two children and all leaf nodes are at same
level is called Complete Binary Tree.
Complete binary tree is also called as Perfect Binary Tree

Example-

Here,
 First binary tree is not a complete binary tree.
 This is because all the leaf nodes are not at the same level.
3. Extended Binary Tree
A binary tree can be converted into Full Binary tree by adding dummy nodes to existing nodes wherever
required.
The full binary tree obtained by adding dummy nodes to a binary tree is called as Extended Binary
Tree.

In above figure, a normal binary tree is converted into full binary tree by adding dummy nodes (In pink
colour).
Tree Traversal
Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes
are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly
access a node in a tree. There are three ways which we use to traverse a tree −
 In-order Traversal
 Pre-order Traversal
 Post-order Traversal
Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values
it contains.
Following three traversal techniques fall under Depth First Traversal-
1. Preorder Traversal
2. Inorder Traversal
3. Postorder Traversal
1. Preorder Traversal-
To traverse a non-empty tree in pre order we perform three operations
1. Visit the root
2. raverse the left sub tree in Preorder
3. Traverse the right sub tree in Preorder
Root → Left → Right
Algorithm
Preorder Tree Traversal (x)
Step 1: If x≠ null
Step 2. Then Print data [x]
Step 3. Preorder Tree Traversal (Left[x])
Step 4. Preorder Tree Traversal (Right[x])
Example-
Consider the following example-

Preorder Traversal Shortcut

Traverse the entire tree starting from the root node keeping yourself to the left.

2. Inorder Traversal-
To traverse a non-empty tree in in order we perform three operations
1. Traverse the left sub tree in Inorder
2. Visit the root
3. Traverse the right sub tree in Inorder
Left → Root → Right
Algorithm
Inorder Tree Traversal (x)
Step 1: If x≠ null
Step 2. Then Inorder Tree Traversal (Left[x])
Step 3. Print data [x]
Step 4. Inorder Tree Traversal (Right[x])
Example-
Consider the following example-

Inorder Traversal Shortcut

Keep a plane mirror horizontally at the bottom of the tree and take the projection of all the nodes.

3. Postorder Traversal- \
To traverse a non-empty tree in post order we perform three operations
1. Traverse the left sub tree in Postorder
2. Traverse the right sub tree in Postorder (right sub tree)
3. Visit the root
Left → Right → Root
Algorithm
Postorder Tree Traversal (x)
Step 1: If x≠ null
Step 2. Then Post order Tree Traversal (Left[x])
Step 3. Post order Tree Traversal (Right[x])
Step 4. Print data [x]
Example-
Consider the following example-

Postorder Traversal Shortcut

Pluck all the leftmost leaf nodes one by one.

BINARY SEARCH TREE

Binary Search Tree is a node-based binary tree data structure in which all the nodes with values smaller
than the value in the root in its left sub-tree and all the nodes with values larger than the value in the root
in its right sub-tree.
The properties of a binary search tree are:
 All nodes of left sub-tree are less than root node
 All nodes of right sub-tree are more than root node
 Both sub-trees of each node are also BSTs i.e. they have the above two properties.

CREATION OF BINARY SEARCH TREE

A binary search tree is created by successively reading values for the nodes. The first node becomes the
root node. The next node value is compared with the value of the root node. If it is less the node is
inserted to root's left sub-tree otherwise to right sub-tree and so on.
Say we have to build a BST of the keys, 50, 80, 30, 20, 100, 40. It can be clearly seen below, for inserting,
first the key is compared with the root, if smaller then go to Left sub tree else Right sub tree. The same
step is repeated until all the keys are inserted.

SEARCHING
The search function is used to find whether a given value is present in the tree or not. The searching
process begins at the root node. The function first checks if the binary search tree is empty. If it is empty.
then the value we are searching for is not present in the tree. So, the search algorithm terminates by
displaying an appropriate message. However, if there are nodes in the tree, then the search function
checks to see if the key value of the current node is equal to the value to be searched. If not, it checks if
the value to be searched for is less than the value of the current node, in which case it should be
recursively called on the left child node. In case the value is greater than the value of the current node,
it should be recursively called on the right child node.
Algorithm
SearchElement (root, val)
step 1: if root = null
return null;
elseif value== root->data
return root->data
[end of if]
if val< root -> data
return searchElement(root-> left, val) else
return searchElement(root -> right, val) [end of if
[end of if]
step 2: end

Searching key in a BST

INSERTING A NEW NODE IN A BINARY SEARCH TREE
The insert function is used to add a new node with a given value at the correct position in the binary
search tree. Adding the node at the correct position means that the new node should not violate the
properties of the binary search tree.
The initial code for the insert function is similar to the search function. This is because we first find the
correct position where the insertion has to be done and then add the node at that position. The insertion
function changes the structure of the tree. Therefore, when the insert function is called recursively, the
function should return the new tree pointer.
Agorithm
Insert (root, val)
Step 1: IF root = NULL
Allocate memory for root
SET root -> DATA = VAL
SET root -> LEFT =root -> RIGHT = NULL ELSE
IF VAL< root -> DATA
insert (root -> LEFT, VAL)
ELSE
insert (root -> RIGHT, VAL) [END OF IF]
[END OF IF]
Step 2: END
In step 1 of the algorithm, the insert function checks if the current node of ROOT is NULL. If it is NULL,
the algorithm simply adds the node, else it looks at the current node's value and then recurs down the
left or right sub-tree.
If the current node's value is less than that of the new node, then the right sub-tree is traversed, else the
left sub-tree is traversed. The insert function continues moving down the levels of a binary tree until it
reaches a leaf node. The new node is added by following the rules of the binary search trees. That is, if
the new node's value is greater than that of the parent node, the new node is inserted in the right sub-
tree, else it is inserted in the left sub-tree.
HEIGHT BALANCED TREES
A binary tree of height h is completely balanced if all leaves occur at nodes of level h or h-1 and if all
nodes at levels lower than h-1 have two children.
7

4 10

2 6 9 11

1 3 5 8

According to this definition, the tree in Fig is balanced, because all leaves occur at level 3 and 2 and all
nodes at levels 1 (lower than h-1) have two children.
A tree is height balanced if, for each node in the tree, the height of the left subtree differs from the
height of the right subtree by no more than 1
6

4 9

2 5 8 10

1 3 7

Fig: Height balanced

5 10

2 6 9 11 Fig: not height balanced

1 4 7

3
AVL Trees
An AVL tree is a special type of height-balanced binary search tree (BST) where the balance factor of
every node is at most 1. If the balance factor becomes greater than 1 or less than -1, the tree is rebalanced
using rotations.
Each node of an AVL tree has the property that the height of the left sub tree is either one more, equal,
or one less than the height of the right sub tree.
Building of Height Balanced Tree

We may define a balance factor (BF) as

BF = (Height of Left sub tree - Height of Right sub tree)
Further
If two sub trees are of same height BF=0
If right sub tree is higher BF = -1
If left sub tree is higher BF = +1
For example balance factors are stated near the nodes in Fig. 8.36. BF of the root node is zero because
height of the right subtree and the left subtree is three. etc.

0
HENNA 0
+1

DANNY LOVELY
+1 0 +1 -1
0

BRIJESH FIZZA JASSI NAVIN

0 0 0

AJIT
IMRAN PRITY

Consider an [Link] the values given were in the order:

BRIJESH, FIZZA, IMRAN, NAVIN, LOVELY, PRITY needed to make the height balanced tree. It
would work out as follows:
We begin at the root of the tree We have Fizza to be added
0 BRIJESH
BRIJESH
0

FIZZA
The resulting tree is height balanced Since BF of one of the nodes is other than 0,-1 or +1
Now we add IMRAN we need to rebalance the [Link] the new node

-2 goes to the longer side we need to rotate the

structure counter clockwise
BRIJESH 0
-1
FIZA
0 0
FIZZA
0 IMRAN
BRIJESH
IMRAN

On adding Naveen we get Now we add Lovely

-1 -2
FIZZA
FIZZA
-2
0
0 -1
IMRAN
BRIJESH
BRIJESH IMRAN +1
0
NAVEEN
NAVEEN 0

LOVELY

To regain balance we need to rotate the tree counter On adding Prity we get a balanced tree
clockwise 0 0
IMRAN 0

IMRAN 0
+1 +1 +1
0
0

FIZZA NAVEEN
FIZZA NAVEEN
0
0 0 0 0
0 0

BRIJESH
0
LOVELY PRITY
BRIJESH LOVELY