Subject: Data Structure and Algorithms

NON-LINEAR DATA STRUCTURE

by
Dr. Swapnil Gundewar
DEPARTMENT OF AIDS/AIML/CSD/CSME/CSE

FACULTY OF ENGINEERING
 Course outcomes
Topic CO
Introduction to data structure 1
Characteristics of Algorithms 2
Algorithm Specifications 3
Performance Analysis & Measurement of Algorithm 3
Time and space analysis of Algorithms 3
Average, best and worst case analysis 3
Dynamic Programming 4
 SPECIFIC LEARNING OBJECTIVES

S/No Learning objectives Level Criteria Condition

Understand the basic concepts of non- At least
1 Must know -
linear data structure one

Learn the types of trees and stacks and At least

2 Must know -
graphs two

Understand various operations performed

3 Must know all -
on non-linear data structure.
 Non-Linear Data Structure

•Non-linear data structures are those where data items are not
arranged in a sequential manner, unlike linear data structures.

•In these data structures, elements are stored in a hierarchical or

a network-based structure that does not follow a sequential
order.

•These data structures allow efficient searching, insertion, and

deletion of elements from the structure.
Ex. Trees and Graphs
 Properties of Non Linear Data Structures
1. Hierarchical Organization: Non-linear data structures organize elements in a hierarchical manner, meaning that
data is structured in levels or layers. This organization allows for the representation of complex relationships
between elements.

2. Parent-Child Relationship: In structures like trees, nodes have parent-child relationships, where each node
(except the root) has a parent, and can have zero or more children.

3. Connectivity: In graphs, elements (vertices) are connected by edges, which can represent relationships such
as paths, dependencies, or network connections.

4. Cyclic vs. Acyclic: Non-linear data structures can be cyclic or acyclic. Cyclic structures contain cycles (loops),
while acyclic structures do not.

5 Complexity: Non-linear data structures generally have more complex time and space complexities for various
operations compared to linear data structures due to their hierarchical and interconnected nature.
 Tree Data Structure
⮚ A tree is a non linear data structure in which data is stored in a
hierarchical structure.
⮚ It is a collection of nodes connected by edges.
⮚ Each node has a parent node and zero or more child nodes.
⮚ The node that is present at the top of the hierarchy is called the root
node.
⮚ Trees are widely used in computer science and are an essential part
of many algorithms and data structures.
 Terminologies related to Trees
1. Node: A basic unit of a tree that contains data and may have links to other nodes (its children).

2. Root: The topmost node of a tree, which has no parent. There is only one root node in a tree.

3. Edge: A connection between two nodes in a tree. Each edge connects a parent node to a child node.

4. Parent: A node that has one or more child nodes connected to it.

5. Child: A node that is connected to another node (its parent) above it in the hierarchy.

6. Leaf (or External Node): A node that does not have any children. It is also called a terminal node.

7. Internal Node: A node that has at least one child. These nodes are also called non-terminal nodes.

8. Sibling Nodes: that share the same parent node.

 1. 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.
 2. 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.
 3. Parent Node

• 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".
 4. 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 tree, any parent
node can have any number of child nodes. In a tree, all the nodes
except root are child nodes.
 5. 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.
 6. 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.
 7. 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.
 8. 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'
 9. 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).
 10. 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'.
 11. Depth

• In a tree data structure, the total number of egdes 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'.
 12. 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.
 13. 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 Data structure

• 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.
 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
 2. Complete 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 and 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.
 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.
 Binary Tree Representations
• A binary tree data structure is represented using two methods.
Those methods are as follows...
1.Array Representation
2.Linked List Representation
 Array Representation of Binary Tree

To represent a binary tree of depth 'n' using array representation,

we need one dimensional array with a maximum size of 2n + 1.

Linked List Representation of Binary Tree

We use a double linked list to represent a binary tree. In a double

linked list, every node consists of three fields. First field for storing
left child address, second for storing actual data and third for storing
right child address.
 Binary Search Tree
• In a binary tree, every node can have a maximum of two children but there is no
need to maintain the order of nodes basing on their values. In a binary tree, the
elements are arranged in the order they arrive at the tree from top to bottom and
left to right.
• To enhance the performance of binary tree, we use a special type of binary tree
known as Binary Search Tree.
• Binary Search Tree is a binary tree in which every node contains only smaller values
in its left subtree and only larger values in its right subtree.
Construct a Binary Search Tree by inserting the following sequence of numbers...

1. 10,12,5,4,20,8,7,15 and 13
To construct a Binary Search Tree (BST) from the given sequence of numbers (10, 12, 5, 4, 20, 8, 7, 15,
and 13), we will insert each number one by one following the BST properties: for any given node, the left
subtree contains only nodes with values less than the node’s value, and the right subtree contains only
nodes with values greater than the node’s value.
1. Insert 10:The tree is empty, so 10 becomes the root.

2. Insert 12:12 > 10, so 12 goes to the right of 10.

3. Insert 5:5 < 10, so 5 goes to the left of 10.

4. Insert 4:4 < 10 and 4 < 5, so 4 goes to the left of 5.

5. Insert 20:20 > 10 and 20 > 12, so 20 goes to the right of 12.

6. Insert 8:8 < 10 and 8 > 5, so 8 goes to the right of 5.

7. Insert 7:7 < 10, 7 > 5, and 7 < 8, so 7 goes to the left of 8.

8. Insert 15:15 > 10, 15 > 12, but 15 < 20, so 15 goes to the left of 20.

9. Insert 13:13 > 10, 13 > 12, but 13 < 20 and 13 < 15, so 13 goes to the left of 15.
• Example for Practice: 25, 15, 50, 10, 22, 35, 70, 4, 12, 18.

• 2. 30, 20, 40, 10, 25, 35, 50, 5, 15, 28, 38.
 Tree Traversal Techniques

Unlike linear data structures (Array, Linked List, Queues,

Stacks, etc) which have only one logical way to traverse them,
trees can be traversed in different ways.

A Tree Data Structure can be traversed in following ways:

1.Depth First Search or DFS
1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal
 1. Inorder Traversal
Algorithm Inorder(tree)
1.Traverse the left subtree, i.e., call Inorder(left->subtree)
2.Visit the root.
3.Traverse the right subtree, i.e., call Inorder(right->subtree)
 Preorder Traversal

Algorithm Preorder(tree)
1.Visit the root.
2.Traverse the left subtree, i.e., call Preorder(left->subtree)
3.Traverse the right subtree, i.e., call Preorder(right->subtree)
 Postorder Traversal

Algorithm Postorder(tree)
1.Traverse the left subtree, i.e., call Postorder(left->subtree)
2.Traverse the right subtree, i.e., call Postorder(right->subtree)
3.Visit the root
Convert a Generic Tree(N-array Tree) to Binary
Tree
 Rules
⮚ The root of the Binary Tree is the Root of the Generic Tree.
⮚ The left child of a node in the Generic Tree is the Left child of that node in the
Binary Tree.
⮚ The right sibling of any node in the Generic Tree is the Right child of that node in
the Binary Tree.
For Practice
 AVL Tree Data structure
• AVL tree is a height-balanced binary search tree. That means, an AVL tree is also a
binary search tree but it is a balanced tree.
• A binary tree is said to be balanced if, the difference between the heights of left and
right subtrees of every node in the tree is either -1, 0 or +1.
• In other words, a binary tree is said to be balanced if the height of left and right
children of every node differ by either -1, 0 or +1.
• In an AVL tree, every node maintains an extra information known as balance factor.
• An AVL tree is a balanced binary search tree. In an AVL tree, balance factor of every
node is either -1, 0 or +1.
• Balance factor = height Of Left Subtree – height Of Right Subtree
 AVL Tree Rotations
• In AVL tree, after performing operations like insertion and deletion we need to check
the balance factor of every node in the tree. If every node satisfies the balance factor
condition then we conclude the operation otherwise we must make it balanced.
Whenever the tree becomes imbalanced due to any operation we use rotation
operations to make the tree balanced.
• Rotation is the process of moving nodes either to left or to right to make the tree
balanced.
 Single Left Rotation (LL Rotation)

• In LL Rotation, every node moves one position to left from the current position. To
understand LL Rotation, let us consider the following insertion operation in AVL
Tree...
 Single Right Rotation (RR Rotation)

• In RR Rotation, every node moves one position to right from the

current position. To understand RR Rotation, let us consider the
following insertion operation in AVL Tree...
 Left Right Rotation (LR Rotation)
• A left-right rotation is a combination in which first left rotation takes
place after that right rotation executes
 Right Left Rotation (RL Rotation)

• A right-left rotation is a combination in which first right rotation

takes place after that left rotation executes.
L L Rotation R R Rotation LR Rotation RL Rotation
1 1 1 1

2 2 2
2
3 3 3
3

2 2 3 3

1 3 3 1
2 1 1 2
Prepare AVL tree by inserting the nodes in given order.
35,50,40,25,30,60,78,20,28
40

301 60
60

25 35 50 78

20 28
Construct an AVL Tree by inserting numbers from 1 to 8.
 Heap Data Structure
A Heap is a complete binary tree data structure that satisfies the heap property: for every
node, the value of its children is less than or equal to its own value. Heaps are usually used to
implement priority queues, where the smallest (or largest) element is always at the root of the
tree.
 B-Tree
• Data structure that can handle massive amounts of data with ease.
• When it comes to storing and searching large amounts of data, traditional binary
search trees can become impractical due to their poor performance and high
memory usage.
• B-Trees, also known as B-Tree or Balanced Tree, are a type of self-balancing tree that
was specifically designed to overcome these limitations.
 Applications of Tree Data Structure
⮚ Store hierarchical data, like folder structure, organization structure,
XML/HTML data.
⮚ Binary Search Tree is a tree that allows fast search, insert, delete on a sorted
data. It also allows finding closest item
⮚ As a workflow for compositing digital images for visual effects.
⮚ Decision trees.
⮚ Organization chart of a large organization.
⮚ In XML parser.
⮚ Machine learning algorithm.
⮚ For indexing in database.
⮚ IN server like DNS (Domain Name Server)
⮚ In Computer Graphics.
 Graphs

• Graph is a non-linear data structure.

• It contains a set of points known as nodes (or vertices) and a set of links known as
edges
• Graph is a collection of nodes and edges in which nodes are connected with edges
• Generally, a graph G is represented as G = ( V , E ), where V is set of vertices and E is
set of edges.
• Example
• The following is a graph with 5 vertices and 6 edges.
• This graph G can be defined as G = ( V , E )
• Where V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.
 Graph Terminology
• Vertex
Individual data element of a graph is called as Vertex. Vertex is also known as node. In above example
graph, A, B, C, D & E are known as vertices.
• Edge
An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented as
(startingVertex, endingVertex). For example, in above graph the link between vertices A and B is
represented as (A,B). In above example graph, there are 7 edges (i.e., (A,B), (A,C), (A,D), (B,D), (B,E),
(C,D), (D,E)).
• Edges are three types.
Undirected Edge - An undirected egde is a bidirectional edge. If there is undirected edge between
vertices A and B then edge (A , B) is equal to edge (B , A).
Directed Edge - A directed egde is a unidirectional edge. If there is directed edge between vertices A and
B then edge (A , B) is not equal to edge (B , A).
Weighted Edge - A weighted egde is a edge with value (cost) on it.
Undirected Graph
• A graph with only undirected edges is said to be undirected graph.

Directed Graph
• A graph with only directed edges is said to be directed graph.

Mixed Graph
• A graph with both undirected and directed edges is said to be mixed graph.

End vertices or Endpoints

• The two vertices joined by edge are called end vertices (or endpoints) of that edge.

Origin
• If a edge is directed, its first endpoint is said to be the origin of it.
Destination
• If a edge is directed, its first endpoint is said to be the origin of it and the other endpoint
is said to be the destination of that edge.

Adjacent
• If there is an edge between vertices A and B then both A and B are said to be adjacent.
In other words, vertices A and B are said to be adjacent if there is an edge between
them.

Incident
• Edge is said to be incident on a vertex if the vertex is one of the endpoints of that edge.
Degree
• Total number of edges connected to a vertex is said to be degree of that vertex.

Indegree
• Total number of incoming edges connected to a vertex is said to be indegree of that
vertex.

Outdegree
• Total number of outgoing edges connected to a vertex is said to be outdegree of that
vertex.
 Graph Representations

Graph data structure is represented using following representations...

• Adjacency Matrix
• Incidence Matrix
• Adjacency List
 Adjacency Matrix

• In this representation, the graph is represented using a matrix of size total number of
vertices by a total number of vertices. That means a graph with 4 vertices is
represented using a matrix of size 4X4. In this matrix, both rows and columns
represent vertices. This matrix is filled with either 1 or 0. Here, 1 represents that
there is an edge from row vertex to column vertex and 0 represents that there is no
edge from row vertex to column vertex.
 Incidence Matrix
• In this representation, the graph is represented using a matrix of size total number of
vertices by a total number of edges. That means graph with 4 vertices and 6 edges is
represented using a matrix of size 4X6. In this matrix, rows represent vertices and
columns represents edges. This matrix is filled with 0 or 1 or -1. Here, 0 represents
that the row edge is not connected to column vertex, 1 represents that the row edge
is connected as the outgoing edge to column vertex and -1 represents that the row
edge is connected as the incoming edge to column vertex.
Adjacency List
 Types of Graphs

• 1. Finite Graphs
A graph is said to be finite if it has a finite number of vertices and a finite number of
edges. A finite graph is a graph with a finite number of vertices and edges. In other
words, both the number of vertices and the number of edges in a finite graph are
limited and can be counted.
 2. Infinite Graph

• A graph is said to be infinite if it has an infinite number of

vertices as well as an infinite number of edges.
 3. Trivial Graph:

• A graph is said to be trivial if a finite graph contains only one vertex and no edge. A
trivial graph is a graph with only one vertex and no edges. It is also known as a
singleton graph or a single vertex graph.
 4. Null Graph:

• A graph of order n and size zero is a graph where there are only isolated vertices with
no edges connecting any pair of vertices. A null graph is a graph with no edges. In
other words, it is a graph with only vertices and no connections between them.
 5. Pseudo Graph:

• A graph G with a self-loop and some multiple edges is called a pseudo graph. A
pseudograph is a type of graph that allows for the existence of self-loops (edges that
connect a vertex to itself) and multiple edges (more than one edge connecting two
vertices).
 Graph Traversal

• The process of visiting and exploring the graph for processing is called as Graph
Traversal.

• Breadth First Search (BFS)---Queue

• Depth First Search (DFS)-----Stack
Depth First Search (DFS)-----
 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.

• 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
 Summary
⮚ Types of non-linear data structure,
⮚ Trees, Graphs
⮚ Operations on the trees and graphs
⮚ Depth First Search
⮚ Breadth First Search
 Expected Questions

BAQ
1.Define non-linear data structure.
2.Enlist types of non-linear data structure.

SAQ
3.Illustrate the types of non-linear data structures.
4.Illustrate concept of tree data structure.

LAQ
5.Explain types of tree data structure.
6.Explain graph data structure.
7.Explain depth first search.
 References
1. Data structure using C and C++-AM Tanenbaum, Y
Langsam&amp; MJ Augustein,Prentice Hall India.
2. Data structures & Program Design in C -Robert Kruse, Bruse
Leung,Pearson Education.