Problem Solving with Data
Structure and Algo. (T11001)
MCA (CCFSD)
Unit – 3/4:
Tree and Graph Data Structures
Prepared by:
Neeraj Sharma (A.P, SOET)
Introduction to Tree Data Structures
A tree is a finite set of one or more nodes such that:
1. There is a specially designated node called the root.
2. The remaining nodes are partitioned into n>=0 disjoint sets T1, ..., Tn, where each
of these sets is a tree.
3. We call T1, ..., Tn the subtrees of the root.
Binary Trees
1. A binary tree is a finite set of nodes that is A
either empty or consists of a root and two
disjoint binary trees called the left subtree B C
and the right subtree.
2. Properties:
D E F
Notation: depth(tree) = MAX {depth(leaf)} = height(root)
1. max # of leaves = 2depth(tree)
G H
2. max # of nodes = 2depth(tree)+1 – 1
3. max depth = n-1
3. Special Types of Binary trees: I J
1. Full Binary Tree: A full binary tree is also known as 2-tree in which every node
other than the leaf nodes has two child nodes.
2. Complete Binary Tree: A complete binary tree is a binary tree in which all the
levels are completely filled except possibly the lowest
one, which is filled from the left.
3. Skewed Binary Tree: A skewed binary tree is a type of binary tree in which all
the nodes have only either one child or no child
Binary Tree Implementation using Arrays
• If a complete binary tree with n nodes is represented sequentially, then for any node
with index i, 1<=i<=n, we have:
– parent(i) is at i/2. If i=1, i is at the root and has no parent.
– left_child(i) is at 2i if 2i<=n. If 2i>n, then i has no left child.
– right_child(i) is at 2i+1 if 2i +1 <=n. If 2i +1 >n, then i has no right child.
• Array implementation of Binary tree is only preferred with Complete Binary trees.
Otherwise there might be lot of memory wastage in the form of unused cells in array.
Binary Tree Implementation using Linked Lists
typedef struct node *tree_pointer;
typedef struct node {
int data;
tree_pointer left_child, right_child;
};
Binary Tree Traversals
• We can visit the nodes of tree in three different orders:
– Preorder: Visit Parent, Visit left child, Visit right child
– Inorder: Visit left child, Visit Parent, Visit right child
– Postorder: Visit left child, Visit right child, Visit Parent
Binary Search Tree
Binary Search Tree is a node-based binary tree data structure which has the following
properties:
1. The left subtree of a node contains only nodes with key value less than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.
Operations:
1. Insertion into a Binary Search Tree
2. Searching in a Binary Search Tree
3. Deleting node from a Binary Search Tree (3 Cases)
(Deletion of node with single child node)
(Deletion of node with two child node)
Height Balanced BST (AVL Trees)
1. AVL Tree is invented by GM Adelson - Velsky and EM
Landis in 1962. The left and right subtree each must also
be a binary search tree.
2. Optimized version of BST in which the Height/Levels of
BST is minimized to ensure minimum average Search
Time.
3. 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.
Bf = Height of Left Sub Tree – Height of Right Sub Tree
4. We apply a rotation for balancing an unbalanced tree.
5. Four types of Rotations are: LL, RR, LR, RL
Left – Left Rotation (LL)
Right – Right Rotation (RR)
Left – Right Rotation (LR)
Right – Left Rotation (RL)
Heap Trees
• A Heap is a special Tree-based data structure in which the tree is a complete binary
tree. Generally, Heaps can be of two types:
– Max-Heap: In a Max-Heap the key present at the root node must be greatest
among the keys present at all of it’s children. The same property must be
recursively true for all sub-trees in that Binary Tree.
– Min-Heap: In a Min-Heap the key present at the root node must be minimum
among the keys present at all of it’s children. The same property must be
recursively true for all sub-trees in that Binary Tree.
• Applications of Heap Trees:
• Heap Sort
• Priority Queues
B - Trees
• A B-tree is a self-balancing search tree data structure (like AVL tree) that keeps data
sorted and allows searches, insertions, and deletions.
• It is an m-way search tree and the main idea of using B-Trees is to reduce the number of
disk accesses.
• The height of B-Trees is kept low by putting maximum possible keys in a B-Tree node.
• Generally, the B-Tree node size is kept equal to the disk block size.
• Since the height of the B-tree is low so total disk accesses for most of the operations are
reduced significantly compared to balanced Binary Search Trees like AVL Tree.
Graph Data Structure
• A Graph is a non-linear data structure consisting of nodes and edges.
• The nodes are sometimes also referred to as vertices and the edges are lines or arcs
that connect any two nodes in the graph.
• In the below Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {0 –1, 1 –
2, 2 – 3, 3 – 4, 0 – 4, 1 – 4, 1 – 3}.
• Graphs are used to represent networks. The networks may include paths in a city or
telephone network or circuit network.
• Graphs are also used in social networks like LinkedIn, Facebook. For example, in
Facebook, each person is represented with a vertex(or node). Each node is a structure
and contains information like person id, name, gender, locale etc.
Types of Graph
• Undirected Graph: An undirected graph (graph) is a graph in which edges have no
orientation. The edge (x, y) is identical to edge (y, x), i.e., they are not ordered pairs.
• Directed Graph: A Directed graph (digraph) is a graph in which edges have orientations,
i.e., The edge (x, y) is not identical to edge (y, x).
• Directed Acyclic Graph (DAG): A Directed Acyclic Graph (DAG) is a directed graph that
contains no cycles.
• Multi Graph: A multigraph is an undirected graph in which multiple edges (and
sometimes loops) are allowed. Multiple edges are two or more edges that connect the
same two vertices. A loop is an edge (directed or undirected) that connects a vertex to
itself; it may be permitted or not.
Types of Graph
• Simple Graph: A simple graph is an undirected graph in which both multiple edges and
loops are disallowed as opposed to a multigraph. In a simple graph with n vertices,
every vertex’s degree is at most n-1.
• Weighted and Unweighted Graph: A weighted graph associates a value (weight/length)
with every edge in the graph. An unweighted graph does not have any value
(weight/length) associated with every edge in the graph.
Types of Graph
• Complete Graph: A complete graph is one in which every two vertices are adjacent: all
edges that could exist are present.
• Connected Graph: A Connected graph has a path between every pair of vertices. In
other words, there are no unreachable vertices. A disconnected graph is a graph that is
not connected.
• Bipartite Graph: A Bipartite Graph is a graph whose vertices can be divided into two
independent sets, U and V such that every edge (u, v) either connects a vertex from U to
V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U
and v to V, or u belongs to V and v to U.
Graph Terminologies
• An edge is (together with vertices) one of the two basic units out of which graphs are
constructed. Each edge has two vertices to which it is attached, called its endpoints.
• Two vertices are called adjacent if they are endpoints of the same edge.
• Outgoing edges of a vertex are directed edges that the vertex is the origin.
• Incoming edges of a vertex are directed edges that the vertex is the destination.
• The degree of a vertex in a graph is the total number of edges incident to it.
• In a directed graph, the out-degree of a vertex is the total number of outgoing edges,
and the in-degree is the total number of incoming edges.
• A vertex with in-degree zero is called a source vertex, while a vertex with out-degree
zero is called a sink vertex.
• An isolated vertex is a vertex with degree zero, which is not an endpoint of an edge.
• Path is a sequence of alternating vertices and edges such that the edge connects each
successive vertex.
Graph Terminologies
• Cycle is a path that starts and ends at the same vertex.
• Simple path is a path with distinct vertices.
• A graph is Strongly Connected if it contains a directed path from u to v and a directed path
from v to u for every pair of vertices u, v.
• A directed graph is called Weakly Connected if replacing all of its directed edges with
undirected edges produces a connected (undirected) graph. The vertices in a weakly
connected graph have either out-degree or in-degree of at least 1.
• Connected component is the maximal connected subgraph of an unconnected graph.
• A bridge is an edge whose removal would disconnect the graph.
• Forest is a graph without cycles.
• Tree is a connected graph with no cycles. If we remove all the cycles from DAG (Directed
Acyclic Graph), it becomes a tree, and if we remove any edge in a tree, it becomes a forest.
• Spanning tree of an undirected graph is a subgraph that is a tree that includes all the
vertices of the graph.
Graph Representation
Adjacency Matrix Representation: An adjacency matrix is a square matrix used to
represent a finite graph. The elements of the matrix indicate whether pairs of vertices are
adjacent or not in the graph.
- For a simple unweighted graph with vertex set V, the adjacency matrix is a square |V| ×
|V| matrix A such that its element:
- Aij = 1, when there is an edge from vertex i to vertex j, and
- Aij = 0, when there is no edge.
Graph Representation
Adjacency List Representation: An adjacency list representation for the graph associates
each vertex in the graph with the collection of its neighboring vertices or edges, i.e., every
vertex stores a list of adjacent vertices.
Hamiltonian Graph
• A connected graph G is called
Hamiltonian graph if there is a cycle
which includes every vertex of G and
the cycle is called Hamiltonian cycle.
Hamiltonian walk in graph G is a walk
that passes through each vertex
exactly once.
Euler Graph
• Euler Graph - A connected graph G is
called an Euler graph, if there is a
closed trail which includes every edge
of the graph G.
• Euler Path - An Euler path is a path
that uses every edge of a graph
exactly once. An Euler path starts and
ends at different vertices.
• Euler Circuit - An Euler circuit is a
circuit that uses every edge of a graph
exactly once. An Euler circuit always
starts and ends at the same vertex.
Planar Graph
• A graph is said to be planar if it can be
drawn in a plane so that no edge
cross.
• A graph is said to be non planar if it
cannot be drawn in a plane so that no
edge cross.
Graph Traversal
Graph traversal is a technique used to search for a vertex in a graph. It is also used to
decide the order of vertices to be visited in the search process.
• A graph traversal finds the edges to be used in the search process without creating
loops. This means that, with graph traversal, we can visit all the vertices of the graph
without getting into a looping path. There are two graph traversal techniques:
• DFS (Depth First Search): DFS traversal of a graph produces a spanning tree as final
result. Spanning Tree is a graph without loops. We use Stack data structure with
maximum size of total number of vertices in the graph to implement DFS traversal.
• BFS (Breadth First Search): BFS traversal of a graph produces a spanning tree as final
result. Spanning Tree is a graph without loops. We use Queue data structure with
maximum size of total number of vertices in the graph to implement BFS traversal.
DFS (Depth First Search) Traversal
• Step 1: Define a Stack of size total number of vertices in the graph.
• Step 2: Select any vertex as the starting point for traversal.
Visit that vertex and push it on to the Stack.
• Step 3: Visit any one of the adjacent vertices of the vertex,
that is at top of the stack and is not visited, and
push it on to the stack.
• Step 4: Repeat step 3 until there are no new vertices to visit
from each vertex on top of the stack.
• Step 5: When there is no new vertex to visit, use
backtracking and pop one vertex from the stack.
• Step 6: Repeat steps 3, 4, and 5 until stack becomes Empty.
• Step 7: When stack becomes Empty, produce the final
spanning-tree by removing unused edges from the graph.
DFS (Depth First Search) Traversal
DFS (Depth First Search) Traversal
DFS (Depth First Search) Traversal
DFS (Depth First Search) Traversal
BFS (Breadth First Search) Traversal
We use the following steps to implement BFS traversal...
Step 1 - Define a Queue of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it
into the Queue.
Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of
the Queue and insert them into the Queue.
Step 4 - When there is no new vertex to be visited from the vertex which is at front
of the Queue then delete that vertex.
Step 5 - Repeat steps 3 and 4 until queue becomes empty.
Step 6 - When queue becomes empty, then produce final spanning tree by removing
unused edges from the graph
BFS (Breadth First Search) Traversal
BFS (Breadth First Search) Traversal
BFS (Breadth First Search) Traversal
Shortest Path Problem
• Shortest path problem is a problem of finding the shortest path(s) between vertices of a
given graph. Shortest path between two vertices is a path that has the least cost as
compared to all other existing paths.
• Shortest path algorithms are a family of algorithms used for solving the shortest path
problem.
o Single-pair shortest path problem
o Single-source shortest path problem
o Single-destination shortest path problem
o All pairs shortest path problem
• Shortest path algorithms have a wide range of applications such as in-
- Google Maps
- Road Networks
- Logistics Research
- Routing in Computer Networks
Dijkstra Algorithm
• Dijkstra Algorithm is a very famous greedy algorithm. It is used for solving the single
source shortest path problem. It computes the shortest path from one particular source
node to all other remaining nodes of the graph.
• Dijkstra algorithm works only for connected graphs.
• Dijkstra algorithm works only for those graphs that do not contain any negative weight
edge.
• The actual Dijkstra algorithm does not output the shortest paths.
• It only provides the value or cost of the shortest paths.
• By making minor modifications in the actual algorithm, the shortest paths can be easily
obtained.
• Dijkstra algorithm works for directed as well as undirected graphs.
Dijkstra Algorithm
• Dijkstra Algorithm is a very famous greedy algorithm. It is used for solving the single
source shortest path problem. It computes the shortest path from one particular source
node to all other remaining nodes of the graph.
• Dijkstra algorithm works only for connected graphs.
• Dijkstra algorithm works only for those graphs that do not contain any negative weight
edge.
• The actual Dijkstra algorithm does not output the shortest paths.
• It only provides the value or cost of the shortest paths.
• By making minor modifications in the actual algorithm, the shortest paths can be easily
obtained.
• Dijkstra algorithm works for directed as well as undirected graphs.
Thank You
