INTRODUCTION TO DATA STRUCTURE AND ALGORITHM

Computer science is a field of study that deals with solving a variety of problems by using computers. The
problem to be solved could be as simple as performing the addition of two numbers, or as complex as designing
a robot capable of making decisions in a real-time environment. To solve a given problem by using computer,
you need to design an algorithm for it. The nature of an algorithm often depends closely on the nature of the
data on which the algorithm works. Therefore, the study of algorithms also involves the study of the data
structures that algorithms work on.
ROLE OF ALGORITHM AND DATA STRUCTURE IN PROBLEM SOLVING
Problem solving is an essential part of every scientific discipline. In today’s world, computers are widely used
to solve problems pertaining to various domains, such as banking, commerce, medicine, manufacturing, and
transport.
To solve a given problem by using a computer, you need to write a program for it. A program consists of two
components, algorithm and data structure.
Many different algorithms can be used to solve the same problem. Similarly, various types of data structures
can be used to represent a problem in a computer.
To solve the problem in an efficient manner, you need to select a combination of algorithms and data structures
that provide maximum efficiency.
ROLE OF ALGORITHM
The word algorithm is derived from the name of the Persian mathematician Al Khwarizmi.
Algorithms can be defined as a step-by-step procedure for solving a problem. It helps the user arrive at the
correct result in a finite number of steps. Consider the following step-by-step procedure to display the first 10
natural numbers:-
1. Set the value of counter to 1
2. Display counter
3. Increment counter by 1
4. If counter <=10, go to step 2
The preceding step-by-step procedure is an algorithm because it produces the correct result in a finite number of
steps.
AN ALGORITHM HAS FIVE IMPORTANT PROPERTIES: -

 Finiteness: An algorithm terminates after a finite number of steps.

 Definiteness: Each step in an algorithm is unambiguous. This means that the action specified by the
step cannot be interpreted in multiple ways and can be performed without any confusion.
 Input: An algorithm accepts zero or more inputs.
 Output: An algorithm produces at least one output.
 Effectiveness: An algorithm consists of basic instructions that are realizable. This means that the
instructions can be performed by using the given inputs in a finite amount of time.

1
ROLE OF DATA STRUCTURE
Multiple algorithms can be designed to solve a particular problem. However, the algorithm may differ in how
efficiently they can solve the problem. In such a situation, an algorithm that provides the maximum efficiency
should be used for solving the problem. Efficiency here means that the algorithm should work in minimal time
and use minimal memory.
One of the basic techniques for improving the efficiency of algorithms is to structure the data that they operate
on in such a way that the resulting operations can be efficiently performed.
The way in which the various data elements are organized in memory with respect to each other is called a data
structure. Data can be organized in many different ways; therefore, you can create as many data structures as
you want. However, there are some standard data structures that have proved useful over the years. These
include arrays, linked lists, stacks, queues, trees and graphs.
All these data structures are designed to hold a collection of data items. However, the differences lies in the
way the data items are arranged with respect to each other and the operations that they allow. Because of the
different ways in which the data items are arranged with respect to each other, some data structures prove to be
more efficient that others to solve a given problem.
Suppose you have to write an algorithm that enables printer to service the requests of multiple users on a first-
come-first-served (FCFS) basis. In this case, using a data structure that stores and retrieves the requests in the
order of their arrival would be much more efficient than a data structure that stores and retrieves the requests in
a random order.
In addition to improving the efficiency of an algorithm, the use of appropriate data structures also allows you to
overcome some other programming challenges, such as:-

 Simplifying complex problems

 Creating standard, reusable code components
 Creating programs that are easy to understand and maintain

Consider an example where you have to find the maximum value in a set of 50 numbers, In this scenario, you
can either use 50 variables or a data structure, such as an array of size 50, to store the numbers. When 50
different variables are used to store the numbers, the algorithm to determine the maximum value among the
numbers can be written as:
1. Accept 50 numbers and store them in num1, num2, num3, .. num50
2. Set max = num1
3. If num2 > max then: max = num2
4. If num3 > max then: max = num3
:
5. If num50 > max then max = num50
6. Display max

On the other hand, when an array of size 50 is used, the algorithm can be written as:-
1. Set max = num [0]
2. Repeat step3 varying i from 1 to 49
2
3. If num[i] > max then: max = num[i]
4. Display max
From the preceding two algorithms, it can be seen that the algorithm using an array manipulates memory much
more efficiently than the algorithm using 50 variables. Also, the algorithm using an array involves few steps
and is therefore, easier to understand and implement as compared to the algorithm that uses 50 variables.
Data structures also enable the creation of reusable code components. Suppose you have created a class to
implement a data structure that stores and retrieves requests in the order of their arrival. Once the class is
created, the same class can be used in several different applications that need to service the requests of multiple
users on a FCFS basis.
This means that a data structure once implemented can be used as a standard component to provide a standard
solution to a specific set of problems. The use of standard components helps simplify the maintenance process.
This is because the standard components are time tested and therefore, do not need much maintenance.
DESIGNING ALGORITHM AND MEASURING THEIR EFFICIENCY
Designing an algorithm for a given problem is a difficult intellectual exercise. This is because there is no
systematic method for designing an algorithm. Moreover, there may exist more than one algorithm to solve a
problem, writing an effective algorithm for a new problem or writing a better algorithm for an already existing
one is an art as well as science because it requires both creativity and insight.
TECHNIQUE FOR DESIGNING ALGORITHM
Although there is no systematic method for designing an algorithm, there are some well-known techniques that
have proved to be quite useful in designing algorithms. Two commonly used techniques for designing
algorithms are:-
 DIVIDE AND CONQUER APPROACH

The divide and conquer approach is an algorithm design technique that involves breaking down the problem
recursively into sub problems until the sub problems become so small that they can directly be solved. The
solutions to the sub problems are then combined to give a solution to the original problem.
Divide and conquer is a powerful approach for solving conceptually difficult problems. It simply requires you
to find a way of:-
1. Breaking the problem into sub problems
2. Solving the trivial cases.
3. Combining the solutions of the sub problems to solve the original problem.

Divide and conquer often provides a natural way to design efficient algorithms.

Consider an example where you have to find the minimum value in a list of numbers. The lists are as shown in
the figure:-

To find the minimum value, you can divide the list into two halves, as shown in the following figure: -

3
Again, divide each of the two lists into two halves as shown in the following figure: -

Now, there are only two elements in each list. At this stage, compare the two elements in each lists to find the
minimum of the two. The minimum values from each of the four lists is shown in the following figures.

Again, compare the first two minimum values to determine their minimum. Also compare the last two minimum
values to determine their minimum. The two minimum values thus obtained are shown in the following figure:
-

Again, compare the two final minimum values to obtain the overall minimum value, which is 1 in the preceding
example.

 GREEDY APPROACH

The greedy approach is an algorithm design technique that selects the best possible option at any given time.
Algorithms based on the greedy approach are used for solving optimization problems, where you need to
maximize profits or minimize costs under a given set of conditions. Some examples of optimization problems
are:-
 Finding the shortest distance from an originating city to a set of destination cities, given the distances
between the pairs of cities.
 Finding the minimum number of currency notes required for an amount, where an arbitrary number of
notes for each denomination are available.
 Selecting items with maximum value from a given set of items, where the total weight of the selected
items cannot exceed a given value.

Consider an example, where you have to fill a bag of capacity 10kg by selecting items, (from a set of items)
whose weights and values are given in the following table.

Item Weight (in kg) Value (in$/kg) Total Value (in $)

A 2 200 400
B 3 150 450
C 4 200 800
D 1 50 50
4
 E 5 100 500

Weights and Values of Items

A greedy algorithms acts greedy, and therefore selects the item with the maximum total value at each stage.
Therefore, first of all, item C with total value of $800 and weight 4 kg will be selected. Next, item E with total
value $500 and weight 5 kg will be selected. The next item with the highest value is item B with a total value of
$450 and weight 3 kg. However, if this item is selected, the total weight of the selected items will be 12 kg (4 +
5 + 3), which is more than the capacity of the bag.
Therefore, we discard item B and search for the item with the next highest value. The item with the next higher
value is item A having a total value of $400 and a total weight of 2 kg. However, the item also cannot be
selected because if it is selected, the total weight of the selected items will be 11 kg (4 + 5 + 2). Now, there is
only one item left, that is, item D with a total value of $50 and a weight of 1 kg. This item can be selected as it
makes the total weight equal to 10 kg.

The selected items and their total weights are listed in the following table.
Item Weight (in kg) Total value (in $)
C 4 800
E 5 500
D 1 50
Total 10 1350
Items selected using Greedy Approach

For most problems, greedy algorithms usually fail to find the globally optimal solution. This is because they
usually don’t operate exhaustively on all data. They can make commitments to certain choices too early, which
prevent them from finding the best overall solution later.
This can be seen from the preceding example, where the use of a greedy algorithm selects item with a total
value of $1350 only. However, if the items were selected in the sequence depicted by the following table, the
total value would have been much greater, with the weight being 10 kg only.
Item Weight (in kg ) Total value (in $)
C 4 800
B 3 450
A 2 400
D 1 50
Total 10 1700
Optimal selection of Items

In the preceding example you can observe that the greedy approach commits to item E very early. This prevents
it from determining the best overall solution later. Nevertheless, greedy approach is useful because its quick and
easy to implement. Moreover, it often gives good approximation to the optimal value.
DESIGNING ALGORITHM USING RECURSION
Recursion refers to the technique of defining a process in terms of itself. It is used to solve complex
programming problems that are repetitive in nature.

5
The basic idea behind recursion is to break a problem into smaller versions of itself, and then build up a solution
for the entire problem. This may sound similar to the divide and conquer technique. However, recursions not
similar to the divide and conquer technique.
Divide and conquer is a theoretical concept that may be implemented in a computer program with the help of
recursion.
Recursion is implemented in a program by using a recursive procedure or function. A recursive procedure is a
function which invokes itself.
Consider a function f(n), which is the sum of the first n natural numbers. This function can be defined in several
different ways.
In mathematics, the function will be defined as: f(n) = 1 + 2 + 3 + …. + n
However, the same function can be defined in a recursive manner as: f(n) = f(n – 1) + n
Where n >1; and f(1) = 1
In this case, the recursive definition of the function f(n) calls the same function, but with its arguments reduced
by one. The recursion will end n = 1, in which case f(1) = 1 has been defined.
To understand this concept, consider a factorial function. A factorial function is defined as:-
n! = 1 x 2 x 3 x 4 x .. x n
This same factorial function can be redefined as:-
n! = (n – 1)! x n
Where n > 1; and 0! = 1
This definition of n! is recursive because it refers to itself when it uses (n – 1)!.
The value of n! is explicitly given where n = 0; and the value of n! for arbitrary n is defined in terms of the
smaller value of n, which is closer to the base value 0.
If you have to calculate 3! By using recursion. you first define 3! in terms of 2!:-
3! = (3 x 2!)
Now, you will define 2! in terms of 1!: 3! = (3 x (2 x 1!))
Now, 1! will be defined in terms of 0!: 3! = (3 x (2 x (1 x 0!)))
As, 0! is defined as 1, the expression becomes: 3! = (3 x (2 x (1 x 1)))
3! = (3 x (2 x 1))
3! = (3 x 2)
3! = 6
This recursive algorithm for determining the factorial of a number n can be written as:-

ALGORITHM: FACTORIAL(N)
1. If n = 0, then: //Terminating condition
a. Return (1)
2. Return (n x Factorial (n – 1))
Please note that every recursive algorithm should have a terminating condition. Otherwise, the algorithm will
keep on calling itself infinitely.

6
The main advantage of recursion is that it is useful in writing clear, short, and simple programs. One of the most
common and interesting problems that can be solved using recursion is the Tower of Hanoi problem.
TOWER OF HANOI
Tower of Hanoi is a classical problem, which consists of n different sized disks and three pins over which these
disks can be mounted. All the disks are placed on the first pin with the largest disk at the bottom and the
remaining disks in decreasing order of their size as shown in the following figure:-

The objective of the game is to move all disks from the first pin to the third pin in the least number of moves by
using the second pin as an intermediary.
To play this game, you need to follow rules: -

 Only one disk can be moved at a time

 A larger disk cannot be placed over a smaller one

Let n be the number of the discs. If n = 3, it will require seven moves to transfer all discs from pin one to pin
three, as shown in the table below.
Steps Moves
1 move top disc from pin 1 to pin 3
2 move top disc from pin 1 to pin 2
3 move top disc from pin 3 to pin 2
4 move top disc from pin 1 to pin 3
5 move top disc from pin 2 to pin 1
6 move top disc from pin 2 to pin 3
7 move top disc from pin 1 to pin 3
When n = 2, we should move the top disc from pin 1 to pin 2, move the top disc from pin 1 to pin 3, and then
move the top disc from pin 2 to pin 3.
The solution for n = 1 will be to move the disc from pin 1 to pin 3.
In general, to move n discs from pin 1 to pin 3 using pin 2 as an intermediary, you first need to move the top n –
1 discs from pin 1 to pin 2 using pin 3 as intermediary.

The following algorithm can be used to move the top n discs from the first pin START to final pin FINISH
through the temporary pin TEMP:-

Move (n, START, TEMP, FINISH)

7
1. When n = 1:
a. MOVE a disc from START to FINISH
b. Return
2. Move the top n -1 discs from START to TEMP using FINISH as an intermediary [MOVE (n - 1, START,
FINISH, TEMP)]
3. Move the top disc from START to FINISH
4. Move the top n – 1 discs from TEMP to FINISH using START as an intermediary [MOVE (n - 1, TEMP,
START, FINISH)]
In general, this solution requires 2n-1 moves for n discs.

What is Data Structure

A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so
that it can be accessed and updated efficiently.
A data structure is not only used for organizing the data. It is also used for processing, retrieving, and storing data.
There are different basic and advanced types of data structures that are used in almost every program or software
system that has been developed. So, we must have good knowledge about data structures.
Data Structures are the programmatic way of storing data so that data can be used efficiently. Almost every
enterprise application uses various types of data structures in one or the other way.
Data structures are an integral part of computers used for the arrangement of data in memory. They are essential
and responsible for organizing, processing, accessing, and storing data efficiently. But this is not all. Various types
of data structures have their own characteristics, features, applications, advantages, and disadvantages.

Why to Learn Data Structure

As applications are getting complex and data rich, there are three common problems that applications face now-
a-days.
 Data Search − Consider an inventory of 1 million (10 6) items of a store. If the application is to search
an item, it has to search an item in 1 million (10 6) items every time slowing down the search. As data
grows, search will become slower.
 Processor speed − Processor speed although being very high, falls limited if the data grows to billion
records.
 Multiple requests − As thousands of users can search data simultaneously on a web server, even the
fast server fails while searching the data.
To solve the above-mentioned problems, data structures come to rescue. Data can be organized in a data
structure in such a way that all items may not be required to be searched, and the required data can be searched
almost instantly.

Applications of Data Structure and Algorithms

8
Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get
the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can
be implemented in more than one programming language.
From the data structure point of view, following are some important categories of algorithms −
 Search − Algorithm to search an item in a data structure.
 Sort − Algorithm to sort items in a certain order.
 Insert − Algorithm to insert item in a data structure.
 Update − Algorithm to update an existing item in a data structure.
 Delete − Algorithm to delete an existing item from a data structure.
The following computer problems can be solved using Data Structures −
 Fibonacci number series
 Knapsack problem
 Tower of Hanoi
 All pair shortest path by Floyd-Warshall
 Shortest path by Dijkstra
 Project scheduling

How Data Structure varies from Data Type:

Data Type Data Structure

The data type is the form of a variable to which

a value can be assigned. It defines that the Data structure is a collection of different kinds of data.
particular variable will assign the values of the That entire data can be represented using an object and
given data type only. can be used throughout the program.

It can hold value but not data. Therefore, it is

dataless. It can hold multiple types of data within a single object.

The implementation of a data type is known as Data structure implementation is known as concrete
abstract implementation. implementation.

There is no time complexity in the case of data In data structure objects, time complexity plays an
types. important role.

In the case of data types, the value of data is not While in the case of data structures, the data and its
stored because it only represents the type of data value acquire the space in the computer’s main memory.
that can be stored. Also, a data structure can hold different kinds and types

9
 Data Type Data Structure

of data within one single object.

Data type examples are int, float, double, etc. Data structure examples are stack, queue, tree, etc.

Classification of Data Structure:

Data structure has many different uses in our daily life. There are many different data structures that are used
to solve different mathematical and logical problems. By using data structure, one can organize and process a
very large amount of data in a relatively short period. Let’s look at different data structures that are used in
different situations.

Classification of Data Structure

Linear data structure: Data structure in which data elements are arranged sequentially or
linearly, where each element is attached to its previous and next adjacent elements, is called a
linear data structure.
Examples of linear data structures are array, stack, queue, linked list, etc.
 Static data structure: Static data structure has a fixed memory size. It is easier to
access the elements in a static data structure.
An example of this data structure is an array.
 Dynamic data structure: In the dynamic data structure, the size is not fixed. It can be
randomly updated during the runtime which may be considered efficient concerning the
memory (space) complexity of the code.
Examples of this data structure are queue, stack, etc.
 Non-linear data structure: Data structures where data elements are not placed sequentially or
linearly are called non-linear data structures. In a non-linear data structure, we can’t traverse all
the elements in a single run only.
Examples of non-linear data structures are trees and graphs.
Need of Data Structure :

10
The structure of the data and the synthesis of the algorithm are relative to each other. Data presentation must
be easy to understand so the developer, as well as the user, can make an efficient implementation of the
operation.
Data structures provide an easy way of organizing, retrieving, managing, and storing data.
Here is a list of the needs for data.
1. Data structure modification is easy.
2. It requires less time.
3. Save storage memory space.
4. Data representation is easy.
5. Easy access to the large database.

Arrays:

An array is a linear data structure and it is a collection of items stored at contiguous memory locations. The
idea is to store multiple items of the same type together in one place. It allows the processing of a large
amount of data in a relatively short period. The first element of the array is indexed by a subscript of 0. There
are different operations possible in an array, like Searching, Sorting, Inserting, Traversing, Reversing, and
Deleting.

Array Data Structure

Characteristics of an Array:

An array has various characteristics which are as follows:

 Arrays use an index-based data structure which helps to identify each of the elements in an array
easily using the index.
 If a user wants to store multiple values of the same data type, then the array can be utilized
efficiently.
 An array can also handle complex data structures by storing data in a two-dimensional array.
 An array is also used to implement other data structures like Stacks, Queues, Heaps, Hash tables,
etc.
 The search process in an array can be done very easily.

Applications of Array:

Different applications of an array are as follows:

11
  An array is used in solving matrix problems.
 Database records are also implemented by an array.
 It helps in implementing a sorting algorithm.
 It is also used to implement other data structures like Stacks, Queues, Heaps, Hash tables, etc.
 An array can be used for CPU scheduling.
 Can be applied as a lookup table in computers.
 Arrays can be used in speech processing where every speech signal is an array.
 The screen of the computer is also displayed by an array. Here we use a multidimensional array.
 The array is used in many management systems like a library, students, parliament, etc.
 The array is used in the online ticket booking system. Contacts on a cell phone are displayed by
this array.
 In games like online chess, where the player can store his past moves as well as current moves. It
indicates a hint of position.
 To save images in a specific dimension in the android Like 360*1200

Real-Life Applications of Array:

 An array is frequently used to store data for mathematical computations.

 It is used in image processing.
 It is also used in record management.
 Book pages are also real-life examples of an array.
 It is used in ordering boxes as well.

Linked list:

A linked list is a linear data structure in which elements are not stored at contiguous memory locations. The
elements in a linked list are linked using pointers as shown in the below image:
Types of linked lists:
 Singly-linked list
 Doubly linked list
 Circular linked list
 Doubly circular linked list

Linked List

Characteristics of a Linked list:

12
A linked list has various characteristics which are as follows:
 A linked list uses extra memory to store links.
 During the initialization of the linked list, there is no need to know the size of the elements.
 Linked lists are used to implement stacks, queues, graphs, etc.
 The first node of the linked list is called the Head.
 The next pointer of the last node always points to NULL.
 In a linked list, insertion and deletion are possible easily.
 Each node of the linked list consists of a pointer/link which is the address of the next node.
 Linked lists can shrink or grow at any point in time easily.

Applications of the Linked list:

Different applications of linked lists are as follows:

 Linked lists are used to implement stacks, queues, graphs, etc.
 Linked lists are used to perform arithmetic operations on long integers.
 It is used for the representation of sparse matrices.
 It is used in the linked allocation of files.
 It helps in memory management.
 It is used in the representation of Polynomial Manipulation where each polynomial term represents
a node in the linked list.
 Linked lists are used to display image containers. Users can visit past, current, and next images.
 They are used to store the history of the visited page.
 They are used to perform undo operations.
 Linked are used in software development where they indicate the correct syntax of a tag.
 Linked lists are used to display social media feeds.

Real-Life Applications of a Linked list:

 A linked list is used in Round-Robin scheduling to keep track of the turn in multiplayer games.
 It is used in image viewer. The previous and next images are linked, and hence can be accessed by
the previous and next buttons.
 In a music playlist, songs are linked to the previous and next songs.

Stack:

Stack is a linear data structure that follows a particular order in which the operations are performed. The order
is LIFO (Last in first out). Entering and retrieving data is possible from only one end. The entering and
retrieving of data is also called push and pop operation in a stack. There are different operations possible in a
stack like reversing a stack using recursion, Sorting, Deleting the middle element of a stack, etc.

13
Characteristics of a Stack:

Stack has various different characteristics which are as follows:

 Stack is used in many different algorithms like Tower of Hanoi, tree traversal, recursion, etc.
 Stack is implemented through an array or linked list.
 It follows the Last In First Out operation i.e., an element that is inserted first will pop in last and
vice versa.
 The insertion and deletion are performed at one end i.e. from the top of the stack.
 In stack, if the allocated space for the stack is full, and still anyone attempts to add more elements,
it will lead to stack overflow.

Applications of Stack:

Different applications of Stack are as follows:

 The stack data structure is used in the evaluation and conversion of arithmetic expressions.
 Stack is used in Recursion.
 It is used for parenthesis checking.
 While reversing a string, the stack is used as well.
 Stack is used in memory management.
 It is also used for processing function calls.
 The stack is used to convert expressions from infix to postfix.
 The stack is used to perform undo as well as redo operations in word processors.
 The stack is used in virtual machines like JVM.
 The stack is used in the media players. Useful to play the next and previous song.
 The stack is used in recursion operations.

Real-Life Applications of Stack:

 Real life example of a stack is the layer of eating plates arranged one above the other. When you
remove a plate from the pile, you can take the plate to the top of the pile. But this is exactly the
plate that was added most recently to the pile. If you want the plate at the bottom of the pile, you
must remove all the plates on top of it to reach it.
 Browsers use stack data structures to keep track of previously visited sites.

14
  Call log in mobile also uses stack data structure.

Queue:
Queue is a linear data structure that follows a particular order in which the operations are performed. The
order is First In First Out (FIFO) i.e. the data item stored first will be accessed first. In this, entering and
retrieving data is not done from only one end. An example of a queue is any queue of consumers for a
resource where the consumer that came first is served first. Different operations are performed on a Queue
like Reversing a Queue (with or without using recursion), Reversing the first K elements of a Queue, etc. A
few basic operations performed In Queue are enqueue, dequeue, front, rear, etc.

Characteristics of a Queue:
The queue has various different characteristics which are as follows:

 The queue is a FIFO (First In First Out) structure.

 To remove the last element of the Queue, all the elements inserted before the new element in the
queue must be removed.
 A queue is an ordered list of elements of similar data types.
Applications of Queue:
Different applications of Queue are as follows:

 Queue is used for handling website traffic.

 It helps to maintain the playlist in media players.
 Queue is used in operating systems for handling interrupts.
 It helps in serving requests on a single shared resource, like a printer, CPU task scheduling, etc.
 It is used in the asynchronous transfer of data e.g. pipes, file IO, and sockets.
 Queues are used for job scheduling in the operating system.
 In social media to upload multiple photos or videos queue is used.
 To send an e-mail queue data structure is used.
 To handle website traffic at a time queues are used.

15
  In Windows operating system, to switch multiple applications.
Real-Life Applications of Queue:
 A real-world example of a queue is a single-lane one-way road, where the vehicle that enters first
will exit first.
 A more real-world example can be seen in the queue at the ticket windows.
 A cashier line in a store is also an example of a queue.
 People on an escalator
Tree:

A tree is a non-linear and hierarchal data structure where the elements are arranged in a tree-like structure. In
a tree, the topmost node is called the root node. Each node contains some data, and data can be of any type. It
consists of a central node, structural nodes, and sub-nodes which are connected via edges. Different tree data
structures allow quicker and easier access to the data as it is a non-linear data structure. A tree has various
terminologies like Node, Root, Edge, Height of a tree, Degree of a tree, etc.
There are different types of Tree-like
 Binary Tree,
 Binary Search Tree,
 AVL Tree,
 B-Tree, etc.

Tree

Characteristics of a Tree:

The tree has various different characteristics which are as follows:

 A tree is also known as a Recursive data structure.
 In a tree, the Height of the root can be defined as the longest path from the root node to the leaf
node.
 In a tree, one can also calculate the depth from the top to any node. The root node has a depth of 0.

16
Applications of Tree:

Different applications of Tree are as follows:

 Heap is a tree data structure that is implemented using arrays and used to implement priority
queues.
 B-Tree and B+ Tree are used to implement indexing in databases.
 Syntax Tree helps in scanning, parsing, generation of code, and evaluation of arithmetic
expressions in Compiler design.
 K-D Tree is a space partitioning tree used to organize points in K-dimensional space.
 Spanning trees are used in routers in computer networks.

Real-Life Applications of Tree:

 In real life, tree data structure helps in Game Development.

 It also helps in indexing in databases.
 A Decision Tree is an efficient machine-learning tool, commonly used in decision analysis. It has a
flowchart-like structure that helps to understand data.
 Domain Name Server also uses a tree data structure.
 The most common use case of a tree is any social networking site.

Graph

A graph is a non-linear data structure that consists of vertices (or nodes) and edges. It consists of a finite set
of vertices and set of edges that connect a pair of nodes. The graph is used to solve the most challenging and
complex programming problems. It has different terminologies which are Path, Degree, Adjacent vertices,
Connected components, etc.

Graph

Characteristics of Graph:

The graph has various different characteristics which are as follows:

17
  The maximum distance from a vertex to all the other vertices is considered the Eccentricity of that
vertex.
 The vertex having minimum Eccentricity is considered the central point of the graph.
 The minimum value of Eccentricity from all vertices is considered the radius of a connected graph.

Applications of Graph:

Different applications of Graphs are as follows:

 The graph is used to represent the flow of computation.
 It is used in modeling graphs.
 The operating system uses Resource Allocation Graph.
 Also used in the World Wide Web where the web pages represent the nodes.

Real-Life Applications of Graph:

 One of the most common real-world examples of a graph is Google Maps where cities are located
as vertices and paths connecting those vertices are located as edges of the graph.
 A social network is also one real-world example of a graph where every person on the network is a
node, and all of their friendships on the network are the edges of the graph.
 A graph is also used to study molecules in physics and chemistry.

Advantages of data structure:

1. Improved data organization and storage efficiency.

2. Faster data retrieval and manipulation.
3. Facilitates the design of algorithms for solving complex problems.
4. Eases the task of updating and maintaining the data.
5. Provides a better understanding of the relationships between data elements.

Disadvantage of Data Structure:

1. Increased computational and memory overhead.

2. Difficulty in designing and implementing complex data structures.
3. Limited scalability and flexibility.
4. Complexity in debugging and testing.
5. Difficulty in modifying existing data structures.

18