https://www.guru99.

com/design-analysis-algorithms-
tutorial.html
https://www.codingninjas.com/studio/library/design-
and-algorithm-analysis

What is the design and analysis of algorithms?

Design and Analysis of Algorithms help in the investigation of feasible options before
the coding step. By examining algorithms, you can determine the space and time
complexity involved. The interaction of algorithms and design provides a comprehensive
overview of the code that will be written to address the challenge. By enhancing both
time and space efficiency, this approach contributes to a more streamlined solution.
In the branch of computer science and IT writing good algorithms with best cases is an
important skill. Learning different algorithms will help increase your logic-building and
ability to solve complex problems, giving you a better understanding of the problem.
Choosing the suitable algorithm for the problem helps in saving time and provides you
with a readable solution.
Algorithm is important?
 To forecast the behavior of an algorithm without putting it into action on a specific
computer

 It is far more convenient to have basic metrics for an algorithm's efficiency than to
develop the algorithm and assess its efficiency each time a specific parameter in
the underlying computer system changes

 It is hard to foresee an algorithm's exact behavior. There are far too many variables
to consider

 As a result, the analysis is simply an approximation; it is not perfect

 More significantly, by comparing several algorithms, we can identify which one is

ideal for our needs

Prerequisites of Learning Design and Analysis of

Algorithms
Before you learn about the designs and analysis of algorithms, it is important to have
basic knowledge of any programming language.
You must have basic knowledge of mathematics concepts and Data structures(DSA).
It is good to have an understanding of Automata and formal language.
Basic knowledge of algorithms will help you to understand DAA easily.
What is an Algorithm?
Algorithms are sequences of instructions that you write to solve a complex problem.
You write these instructions by performing different calculations, data processing, and
scenarios.
These are independent of any programming language, and you can write the code in
your preferred language. The algorithms are nothing but the steps that guide you to
solve the problem with the definitions of the use of time and space resources. You can
get information about the time and space complexity through algorithms before writing
the actual code.
The algorithms help in saving a lot of time as you don't need to code the programs and
then find the complexities.
The best solution can find out when you write the algorithms for the specific problem.
It is the best way to represent any problem with the best and most efficient solutions.

How to Write an Algorithm?

There is no hard and fast rule when writing an algorithm. There are a few points you just
have to consider when you write an algorithm.
 Describe the problem clearly. Be simple and clear with the description of the
problem.

 Determine the input and output of the algorithm. Do not make the algorithm runs
infinite.

 Briefly describe the start and end points of the algorithm.

 Description of the steps to achieve the target.

 Review the algorithm.

Characteristics of Algorithms
 Algorithms must have an endpoint. It should not run for infinity. There must be a
finite amount of time for which the algorithm must run

 You must give an algorithm an individual name

 Definition of input and output should be well defined. You must give sample input
other than 0 and output for better understanding
 There must be a defined instruction for solving the problem. The algorithm should
not have an unnecessary number of instructions

 You must give clear and concise instructions without making them difficult to
understand

 The instruction must be independent of the programming language. The algorithm

should be dependent on one single language

 Algorithm helps in faster processing, so it must be adequate and correct, which

helps in getting greater efficiency

Need for Algorithms

 There is an important need to have algorithms in computer science

 Get a clear understanding of the problem

 To find the optimal solution for the problem

 Provides scalability. Divide the problem into smaller steps as it gives a better
understanding of the problem

 Understanding the design principles and algorithms

 Use the best technologies to get the most efficient and best solution

 Without implementation getting complete information about the problem is

 To understand the comparison between different algorithms and find the best time
complexity with the best space resource

Factors of Algorithm
It is important to consider some factors when you write an algorithm.
 Understandable: It is important that when you write an algorithm, it must be easily
understandable and easy to read and understand

 Simplify: The algorithm should have simplicity. You must write an algorithm that is
simple and concise
 Short and Crisp: You must consider this factor when writing an algorithm. The
algorithm should be short and must have complete information about the problem

 Description: The algorithm should have complete information about the problem
and describe the problem in complete detail

 Modular: You should be able to break down the problem into smaller sections. The
algorithm should be specially designed so that it can be easily understood

 Precision: Algorithms are expected to be precise and correct. The input should
give the desired output. Algorithms should be correct and work according to the
need

Development of Problem
There are different stages when a problem is documented.
1. Definition and development of a model

2. Specify and design the algorithm

3. Analyzing and correcting the algorithm

4. Selection of correct algorithm

5. Writing the implementation and performing the program testing

6. Finally, document the problem with the solution.

Types of Design and Algorithm Analysis

Whenever you analyze an algorithm, you consider the following cases.

Best Case: We find the best case of an algorithm, i.e., the condition when the algorithm
gets executed in the minimum number of operations. We find the lower bound of the
algorithm when the algorithm performs successfully. For example: When we perform a
linear search algorithm in any data structure, if we search for an element and the
element is present in the first position, that case is referred to as the best case.
Worst Case: We find the worst case of an algorithm, i.e., the condition when the
algorithm gets excited in the maximum number of operations. In the worst case, we get
an algorithm's higher bound running time. For example: When we perform a linear
search algorithm in any data structure if we search for an element that is not present in
that data structure, that case is referred to as the worst case.
Average Case: We find the average case of an algorithm, i.e., the condition when the
algorithm gets excited in a few numbers of operations. For example: When we perform
a linear search algorithm in any data structure, if we search for an element and the
element is present in the middle position, that case is referred to as the average case.
Also read - Kadane's Algorithm

Analysis Methods
There are different analysis methods. The most common are given below.

Asymptotic Analysis
In asymptotic analysis, there are three main asymptotic notations.
 Big O Notation: This notation represents the worst case. It only calculates the
upper bound of time when the algorithm is implemented

 Omega Notation: This notation represents the best case. It only calculates the
lower bound of time when the algorithm is implemented

 Theta Notation: It is used for analyzing the average case. It calculates the time
complexity using the upper and lower bounds
Must Read Lower Bound in C++

Types of Algorithms
There are different types of algorithms, and the most commonly used algorithms are
discussed below:

Sorting Algorithms
We perform sorting operations on data to sort the data in ascending or descending
order. It helps in arranging the data in any format. Different problems can be solved
using sorting algorithms, some as bubble sort, merge sort, quick sport, selection sort,
and insertion sort are a few such sorting algorithms.
int main()
{
int [] array={1,5,6,7,8};
int search=6;
boolean flag = false;
for(int i = 0; i < arr.length ; i++)
{
if(array[i] == search)
{
flag=true;
}
}
if(flag == true)
System.out.println("Number found");
else
System.out.println("Number not found");
}

Output
Number found

Time Complexity= O(n)

Brute Force Algorithms

To solve a problem, we first need to have a solution, and for this, we first find the
solution for the problem. We do this by brute force algorithm without considering the
time and space complexity once we get the solution by brute force algorithm and later
try to optimize the solution.

Recursive Algorithms
Recursive algorithms are the most important algorithm in computer science. In this
algorithm, a function gives a call to itself. It recursively calls its function to solve the
problem. You don't have to worry about the subproblems; only consider a case and
write the algorithm accordingly. While writing this algorithm, you must consider the time
management factor as recursion calls recursive stack.
Let's try to understand this algorithm by an example.
int factorial(int number)
{
if(number<=1){
return 1;
}
else{
return number * factorial(number-1);
}
}

Learn more recursion.

Divide and Conquer Algorithm
It is another important algorithm that is mostly used in solving maximum problems. As
the name implies, first, you divide the problem into sub-problems and combine those
sub-problems to get the solution. In this, you first break down the problems into sub-
parts and finally combine those sub-parts to get the solution for the problem. Many
problems are solved using this algorithm. Some applications are binary search, median
finding, matrix multiplication, merge, quick sort, etc.
Learn Divide and Conquer

Backtracking Algorithm
The better version of the brute force approach. In this algorithm, we first start with a
solution, and if the solution is successful in solving the problem, we print the same
solution, but in case the first move does not provide the solution, then you backtrack
and try to solve it with another move. This backtracking process is called as
backtracking algorithm. There are many applications of this algorithm. Some of them
are the N - Queens problem, the KnapSack algorithm, generating binary strings, etc.
Learn Introduction To Backtracking

Dynamic Programming Algorithm

The most efficient algorithm in computer science. In this algorithm, we analyze the past
and apply that in the future. This algorithm considers and provides the solution with the
best time and space complexity. There are two versions in which you use the dynamic
algorithm. Bottom-up approach: In this approach, you solve the last subproblem and
then shift to the upper problem. The results of these subproblems help you solve the
problem's upper part.
Top-down approach: In this approach, you start solving the problem from the top
portion. You apply those solutions to the lower part of the problem by getting the results
from the top issues.
The are many applications of this algorithm. Some of them are the bellman ford
algorithm's longest common subsequence, bellman ford algorithm, chain, subset sum,
longest common substring, etc.

Greedy Algorithm
In this algorithm, you find the solution that is best for the present. You don't worry about
the future and look for another optimal solution. The algorithm works in a top-down
approach and might not be the best solution as it chooses the solution that works locally
and is chosen globally. It has two properties i.e., Greedy choice property and optimal
structure. The are many applications of this algorithm. Huffman coding, K centers
problems, Graph coloring, fractional knapsack problems, minimum spanning trees, etc.
Learn Greedy algorithms
 Prims and Kruskal Algorithm
Advantages of Algorithms
There are many advantages of writing algorithms. Some of them are discussed below.
 Understanding the problem is easy. The steps and sequence help in better
understanding the problem

 The algorithm helps in determining the solution without writing the implementation

 The problems are broken down into smaller sub-problems which helps the
programmer easily convert the solution into the code

 It is independent of the programming language

 An Algorithm act as a blueprint of a program

 The programmer can understand the algorithm and find the optimal solution without
writing the actual program and coding it

Check out this problem - Minimum Coin Change Problem

Disadvantages of Algorithm
 Writing an algorithm is time-consuming

 Describing loops in algorithms is hard

 Describing big problems is difficult to solve and writing algorithms for that kind of
problem is more difficult

Frequently Asked Questions

What is the design and analysis of algorithms?
In the design and analysis of algorithms, we study algorithms and the design
implementation of algorithms. Algorithms play an important role in solving issues. It
gives us a clear and concise picture of how to tackle the problem with the best possible
solution.

Why are there types of algorithms?

There are different types of algorithms. Every algorithm differs in terms of space and
time complexity. The resources used in one algorithm may not be efficient in another
algorithm. Therefore there is a need for different types of algorithms that can help us in
the identification of a better solution.
Name some types of algorithms.
Some commonly used algorithms that help us in most applications are the sorting
algorithm, Brute Force Algorithm, Recursive Algorithm, Divide and conquer Algorithm,
backtracking Algorithm, Greedy Algorithm, and Dynamic Programming Algorithm.

Why do we study Algorithms?

Algorithms play an important role when we define a problem with a solution. The
sequence of steps helps us to get a clear picture of the problem, which further helps us
to find an optimized and efficient solution. It is the program's blueprint, and we can
analyze it before implementing it.

What do you refer to as DAA?

DAA commonly refers to the Design and Analysis of Algorithms. Learning this is an
important skill in computer science. Solving a problem without having the proper
algorithm cause error, and it takes a lot of time for implementation and then making the
changes later on. Design and analysis help to get a clear picture of the problem.

Table of Content
 Introduction of Algorithms
 Asymptotic Analysis
 Worst, Best and Average Case
 How to Analyse Loops for Complexity Analysis of Algorithms?
 How to combine the time complexities of consecutive loops?
 Algorithms Cheat Sheet for Complexity Analysis:
 Runtime Analysis of Algorithms:
 Little o and Little omega notations
 What does ‘Space Complexity’ mean?
 Previous Year GATE Questions

Introduction of Algorithms
The word Algorithm means “A set of rules to be followed in calculations or
other problem-solving operations” Or “A procedure for solving a mathematical
problem in a finite number of steps that frequently involves recursive
operations “.
Therefore Algorithm refers to a sequence of finite steps to solve a particular
problem. Algorithms can be simple and complex depending on what you
want to achieve.
Types of Algorithms:
1. Brute Force Algorithm
2. Recursive Algorithm
3. Backtracking Algorithm
4. Searching Algorithm
5. Sorting Algorithm
6. Hashing Algorithm
7. Divide and Conquer Algorithm
8. Greedy Algorithm
9. Dynamic Programming Algorithm
10. Randomized Algorithm

Asymptotic Notations
In mathematics, asymptotic analysis, also known as asymptotics, is a
method of describing the limiting behavior of a function. In
computing, asymptotic analysis of an algorithm refers to defining the
mathematical boundation of its run-time performance based on the input size.
For example, the running time of one operation is computed as f(n), and maybe
for another operation, it is computed as g(n2). This means the first operation
running time will increase linearly with the increase in n and the running time of
the second operation will increase exponentially when n increases. Similarly,
the running time of both operations will be nearly the same if n is small in value.
Usually, the analysis of an algorithm is done based on three cases :
1. Best Case (Omega Notation (Ω))
2. Average Case (Theta Notation (Θ))
3. Worst Case (O Notation(O))
Asymptoti Symbo Definitio
c Notation l n Graph Representation

f(n) =
Ω(g(n)), If
there are
positive
constants
n0 and c
Ω such that,
to the right
of n0 the
f(n) always
lies on or
Omega above
Notation c*g(n).

f(n) =
Θ(g(n)), If
there are
positive
constants
n0 and c
such that,
Θ to the right
of n0 the
f(n) always
lies on or
above
c1*g(n)
Theta and below
Notation c2*g(n).
Asymptoti Symbo Definitio
c Notation l n Graph Representation

f(n) =
O(g(n)), If
there are
positive
constants
n0 and c
O such that,
to the right
of n0 the
f(n) always
lies on or
Big-O below
Notation c*g(n).

Asymptotic Analysis
Given two algorithms for a task, how do we find out which one is better?
One naive way of doing this is – to implement both the algorithms and run the
two programs on your computer for different inputs and see which one takes
less time. There are many problems with this approach for the analysis of
algorithms.
 It might be possible that for some inputs, the first algorithm performs better
than the second. And for some inputs second performs better.
 It might also be possible that for some inputs, the first algorithm performs
better on one machine, and the second works better on another machine for
some other inputs.
Asymptotic Analysis is the big idea that handles the above issues in analyzing
algorithms. In Asymptotic Analysis, we evaluate the performance of an
algorithm in terms of input size (we don’t measure the actual running time).
We calculate, how the time (or space) taken by an algorithm increases with the
input size.

Measurement of Complexity of an Algorithm (Worst, Best

and Average Case)
Based on the above three notations of Time Complexity there are three cases
to analyze an algorithm:
1. Worst Case Analysis (Mostly used): Denoted by Big-O notation
In the worst-case analysis, we calculate the upper bound on the running time of
an algorithm. We must know the case that causes a maximum number of
operations to be executed. For Linear Search, the worst case happens when
the element to be searched (x) is not present in the array. When x is not
present, the search() function compares it with all the elements of arr[] one by
one. Therefore, the worst-case time complexity of the linear search would
be O(n).
2. Best Case Analysis (Very Rarely used): Denoted by Omega
notation
In the best-case analysis, we calculate the lower bound on the running time of
an algorithm. We must know the case that causes a minimum number of
operations to be executed. In the linear search problem, the best case occurs
when x is present at the first location. The number of operations in the best
case is constant (not dependent on n). So time complexity in the best case
would be Ω(1)
3. Average Case Analysis (Rarely used): Denoted by Theta notation
In average case analysis, we take all possible inputs and calculate the
computing time for all of the inputs. Sum all the calculated values and divide the
sum by the total number of inputs. We must know (or predict) the distribution of
cases. For the linear search problem, let us assume that all cases are uniformly
distributed (including the case of x not being present in the array). So we sum
all the cases and divide the sum by (n+1). Following is the value of average-
case time complexity.

How to Analyse Loops for Complexity Analysis of

Algorithms?
Constant Time Complexity O(1):
The time complexity of a function (or set of statements) is considered as O(1) if
it doesn’t contain a loop, recursion, and call to any other non-constant time
function. i.e. set of non-recursive and non-loop statements
In computer science, O(1) refers to constant time complexity, which means that
the running time of an algorithm remains constant and does not depend on the
size of the input. This means that the execution time of an O(1) algorithm will
always take the same amount of time regardless of the input size. An example
of an O(1) algorithm is accessing an element in an array using an index.

Linear Time Complexity O(n):

The Time Complexity of a loop is considered as O(n) if the loop variables are
incremented/decremented by a constant amount. For example following
functions have O(n) time complexity. Linear time complexity, denoted as O(n),
is a measure of the growth of the running time of an algorithm proportional to
the size of the input. In an O(n) algorithm, the running time increases linearly
with the size of the input. For example, searching for an element in an unsorted
array or iterating through an array and performing a constant amount of work for
each element would be O(n) operations. In simple words, for an input of size n,
the algorithm takes n steps to complete the operation.

Quadratic Time Complexity O(n c):

The time complexity is defined as an algorithm whose performance is directly
proportional to the squared size of the input data, as in nested loops it is equal
to the number of times the innermost statement is executed. For example, the
following sample loops have O(n 2) time complexity
Quadratic time complexity, denoted as O(n^2), refers to an algorithm whose
running time increases proportional to the square of the size of the input. In
other words, for an input of size n, the algorithm takes n * n steps to complete
the operation. An example of an O(n^2) algorithm is a nested loop that iterates
over the entire input for each element, performing a constant amount of work for
each iteration. This results in a total of n * n iterations, making the running time
quadratic in the size of the input.

Logarithmic Time Complexity O(Log n) :

The time Complexity of a loop is considered as O(Logn) if the loop variables are
divided/multiplied by a constant amount. And also for recursive calls in the
recursive function, the Time Complexity is considered as O(Logn).

Logarithmic Time Complexity O(Log Log n):

The Time Complexity of a loop is considered as O(LogLogn) if the loop
variables are reduced/increased exponentially by a constant amount.

Algorithms Cheat Sheet for Complexity Analysis:

Algorithm Best Case Average Case Worst Case

Selection Sort O(n^2) O(n^2) O(n^2)

Bubble Sort O(n) O(n^2) O(n^2)

Algorithm Best Case Average Case Worst Case

Insertion Sort O(n) O(n^2) O(n^2)

Tree Sort O(nlogn) O(nlogn) O(n^2)

Radix Sort O(dn) O(dn) O(dn)

Merge Sort O(nlogn) O(nlogn) O(nlogn)

Heap Sort O(nlogn) O(nlogn) O(nlogn)

Quick Sort O(nlogn) O(nlogn) O(n^2)

Bucket Sort O(n+k) O(n+k) O(n^2)

Counting Sort O(n+k) O(n+k) O(n+k)

Runtime Analysis of Algorithms:

In general cases, we mainly used to measure and compare the worst-case
theoretical running time complexities of algorithms for the performance
analysis.
The fastest possible running time for any algorithm is O(1), commonly referred
to as Constant Running Time. In this case, the algorithm always takes the same
amount of time to execute, regardless of the input size. This is the ideal runtime
for an algorithm, but it’s rarely achievable.
In actual cases, the performance (Runtime) of an algorithm depends on n, that
is the size of the input or the number of operations is required for each input
item.
The algorithms can be classified as follows from the best-to-worst performance
(Running Time Complexity):
 A logarithmic algorithm – O(logn)
Runtime grows logarithmically in proportion to n.
 A linear algorithm – O(n)
Runtime grows directly in proportion to n.
 A superlinear algorithm – O(nlogn)
Runtime grows in proportion to n.

 A polynomial algorithm – O(n c)

Runtime grows quicker than previous all based on n.
 A exponential algorithm – O(c n)
Runtime grows even faster than polynomial algorithm based on n.
 A factorial algorithm – O(n!)
Runtime grows the fastest and becomes quickly unusable for even
small values of n.
Little o and Little omega notations :
Little-o: Big-O is used as a tight upper bound on the growth of an algorithm’s
effort (this effort is described by the function f(n)), even though, as written, it
can also be a loose upper bound. “Little-o” (o()) notation is used to describe an
upper bound that cannot be tight.
Definition: Let f(n) and g(n) be functions that map positive integers to positive
real numbers. We say that f(n) is o(g(n)) if for any real constant c > 0, there
exists an integer constant n0 > 1 such that 0 < f(n) < c*g(n).
Thus, little o() means loose upper-bound of f(n). Little o is a rough estimate
of the maximum order of growth whereas Big-O may be the actual order of
growth.
little-omega:
The relationship between Big Omega (Ω) and Little Omega (ω) is similar to that
of Big-O and Little o except that now we are looking at the lower bounds. Little
Omega (ω) is a rough estimate of the order of the growth whereas Big Omega
(Ω) may represent exact order of growth. We use ω notation to denote a lower
bound that is not asymptotically tight.
Definition : Let f(n) and g(n) be functions that map positive integers to positive
real numbers. We say that f(n) is ω(g(n)) if for any real constant c > 0, there
exists an integer constant n0 > 1 such that f(n) > c * g(n) > 0 for every integer n
> n0.
f(n) has a higher growth rate than g(n) so main difference between Big Omega
(Ω) and little omega (ω) lies in their definitions.In the case of Big Omega
f(n)=Ω(g(n)) and the bound is 0<=cg(n)<=f(n), but in case of little omega, it is
true for 0<=c*g(n)<f(n).

What does ‘Space Complexity’ mean ?

The term Space Complexity is misused for Auxiliary Space at many places.
Following are the correct definitions of Auxiliary Space and Space Complexity.
Auxiliary Space is the extra space or temporary space used by an
algorithm. The space Complexity of an algorithm is the total space taken by the
algorithm with respect to the input size. Space complexity includes both
Auxiliary space and space used by input.
For example, if we want to compare standard sorting algorithms on the basis of
space, then Auxiliary Space would be a better criterion than Space Complexity.
Merge Sort uses O(n) auxiliary space, Insertion sort, and Heap Sort use O(1)
auxiliary space. The space complexity of all these sorting algorithms is O(n)
though.
Space complexity is a parallel concept to time complexity. If we need to create
an array of size n, this will require O(n) space. If we create a two-dimensional
array of size n*n, this will require O(n 2) space.
In recursive calls stack space also counts.
Example :
int add (int n){
if (n <= 0){
return 0;
}
return n + add (n-1);
}
Here each call add a level to the stack :
1. add(4)
2. -> add(3)
3. -> add(2)
4. -> add(1)
5. -> add(0)
Each of these calls is added to call stack and takes up actual memory.
So it takes O(n) space.
However, just because you have n calls total doesn’t mean it takes O(n) space.
Look at the below function :
int addSequence (int n){
int sum = 0;
for (int i = 0; i < n; i++){
sum += pairSum(i, i+1);
}
return sum;
}
int pairSum(int x, int y){
return x + y;
}
There will be roughly O(n) calls to pairSum. However, those
calls do not exist simultaneously on the call stack,
so you only need O(1) space.
Previous Year GATE Questions:
1. What is the worst-case time complexity of inserting n elements into an
empty linked list, if the linked list needs to be maintained in sorted order?
More than one answer may be correct. [GATE CSE 2020]
(A) Θ(n)
(B) Θ(n log n)
(C) Θ(n2)
(D) Θ(1)
Solution: Correct answer is (C)
2. What is the worst-case time complexity of inserting n 2 elements into an
AVL tree with n elements initially? [GATE CSE 2020]
(A) Θ(n4)
(B) Θ(n2)
(C) Θ(n2 log n)
(D) Θ(n3)
Solution: Correct answer is (C)
3. Which of the given options provides the increasing order of asymptotic
complexity of functions f1, f2, f3 and f4? [GATE CSE 2011]
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)
(A) f3, f2, f4, f1
(B) f3, f2, f1, f4
(C) f2, f3, f1, f4
(D) f2, f3, f4, f1
Answer: (A)
Explanation: nLogn is the slowest growing function, then comes n^(3/2),
then n^(Logn). Finally, 2^n is the fastest growing function.
4. Which one of the following statements is TRUE for all positive
functions f(n)? [GATE CSE 2022]
(A) f(n2) = θ(f(n)2), when f(n) is a polynomial
(B) f(n2) = o(f(n)2)
(C) f(n2) = O(f(n)2), when f(n) is an exponential function
(D) f(n2) = Ω(f(n)2)
Solution: Correct answer is (A)
5.The tightest lower bound on the number of comparisons, in the worst
case, for comparison-based sorting is of the order of [GATE CSE 2004]
(A) n
(B) n2
(C) n log n
(D) n log2 n
Solution: Correct answer is (C)
6. Consider the following functions from positives integers to real numbers
10, √n, n, log2n, 100/n.
The CORRECT arrangement of the above functions in increasing order of
asymptotic complexity is:
(A) log2n, 100/n, 10, √n, n
(B) 100/n, 10, log2n, √n, n
(C) 10, 100/n ,√n, log2n, n
(D) 100/n, log2n, 10 ,√n, n
Answer: (B)
Explanation: For the large number, value of inverse of number is less than a
constant and value of constant is less than value of square root.
10 is constant, not affected by value of n.
√n Square root and log2n is logarithmic. So log 2n is definitely less than √n
n has linear growth and 100/n grows inversely with value of n. For bigger value
of n, we can consider it 0, so 100/n is least and n is max.
7. Consider the following three claims
1. (n + k)m = Θ(nm), where k and m are constants
2. 2n + 1 = O(2n)
3. 22n + 1 = O(2n)
Which of these claims are correct ?
(A) 1 and 2
(B) 1 and 3
(C) 2 and 3
(D) 1, 2, and 3
Answer: (A)
Explanation: (n + k)m and Θ(nm) are asymptotically same as theta notation
can always be written by taking the leading order term in a polynomial
expression.
2n + 1 and O(2n) are also asymptotically same as 2 n + 1 can be written as 2 *
2n and constant multiplication/addition doesn’t matter in theta notation.
22n + 1 and O(2n) are not same as constant is in power.
8. Consider the following three functions.
f1 = 10n
f2 = nlogn
f3 = n√n
Which one of the following options arranges the functions in the increasing
order of asymptotic growth rate?
(A) f3,f2,f1
(B) f2,f1,f3
(C) f1,f2,f3
(D) f2,f3,f1
Answer: (D)
Explanation: On comparing power of these given functions :
f1 has n in power.
f2 has logn in power.
f3 has √n in power.
Hence, f2, f3, f1 is in increasing order.
Note that you can take the log of each function then compare.
In this chapter, let us discuss the time complexity of algorithms and the factors that
influence it.

Time complexity

Time complexity of an algorithm, in general, is simply defined as the time taken by

an algorithm to implement each statement in the code. It is not the execution time
of an algorithm. This entity can be influenced by various factors like the input size,
the methods used and the procedure. An algorithm is said to be the most efficient
when the output is produced in the minimal time possible.

The most common way to find the time complexity for an algorithm is to deduce
the algorithm into a recurrence relation. Let us look into it further below.

Solving Recurrence Relations

A recurrence relation is an equation (or an inequality) that is defined by the smaller

inputs of itself. These relations are solved based on Mathematical Induction. In
both of these processes, a condition allows the problem to be broken into smaller
pieces that execute the same equation with lower valued inputs.

These recurrence relations can be solved using multiple methods; they are −

 Substitution Method
 Recurrence Tree Method
 Iteration Method
 Master Theorem

Substitution Method

The substitution method is a trial and error method; where the values that we might
think could be the solution to the relation are substituted and check whether the
equation is valid. If it is valid, the solution is found. Otherwise, another value is
checked.

Procedure

The steps to solve recurrences using the substitution method are −

 Guess the form of solution based on the trial and error method
 Use Mathematical Induction to prove the solution is correct for all the cases.

Example

Let us look into an example to solve a recurrence using the substitution method,

T(n) = 2T(n/2) + n

Here, we assume that the time complexity for the equation is O(nlogn). So
according the mathematical induction phenomenon, the time complexity for T(n/2)
will be O(n/2logn/2); substitute the value into the given equation, and we need to
prove that T(n) must be greater than or equal to nlogn.

≤ 2n/2Log(n/2) + n
= nLogn - nLog2 + n
= nLogn - n + n
≤ nLogn

Recurrence Tree Method

In the recurrence tree method, we draw a recurrence tree until the program cannot
be divided into smaller parts further. Then we calculate the time taken in each level
of the recurrence tree.

Procedure

 Draw the recurrence tree for the program

 Calculate the time complexity in every level and sum them up to find the
total time complexity.

Example

Consider the binary search algorithm and construct a recursion tree for it −
Since the algorithm follows divide and conquer technique, the recursion tree is
drawn until it reaches the smallest input level T(n2k)T(n2k).

T(n2k)=T(1)T(n2k)=T(1)
n=2kn=2k

Applying logarithm on both sides of the equation,

logn=log2klogn=log2k
k=log2nk=log2n

Therefore, the time complexity of a binary search algorithm is O(log n).

Master's Method

Master's method or Master's theorem is applied on decreasing or dividing

recurrence relations to find the time complexity. It uses a set of formulae to deduce
the time complexity of an algorithm.

What is Recurrence Relations?

A recurrence relation is a mathematical expression that defines a sequence in
terms of its previous terms. In the context of algorithmic analysis, it is often
used to model the time complexity of recursive algorithms.
What is Linear Recurrence Relation?
In a linear recurrence relation, each term in the sequence is a linear
combination of previous terms.
General form:

where, c1, c2, …, ck are constants and F(n) is a function.

How to Solve Recurrence Relations?
The analysis of the complexity of a recurrence relation involves finding the
asymptotic upper bound on the running time of a recursive algorithm. This is
usually done by finding a closed-form expression for the number of operations
performed by the algorithm as a function of the input size, and then determining
the order of growth of the expression as the input size becomes large.
Various methods to analyze the complexity of a recurrence relation are:
1. Substitution Method:
We make a guess for the solution and then we use mathematical induction to
prove the guess is correct or incorrect.
For example consider the recurrence T(n) = 2T(n/2) + n
We guess the solution as T(n) = O(nLogn). Now we use induction to prove our
guess.
We need to prove that T(n) <= cnLogn. We can assume that it is true for values
smaller than n.
T(n) = 2T(n/2) + n
<= 2cn/2Log(n/2) + n
= cnLogn – cnLog2 + n
= cnLogn – cn + n
<= cnLogn

2. Recurrence Tree Method:

In this method, we draw a recurrence tree and calculate the time taken by every
level of the tree. Finally, we sum the work done at all levels. To draw the
recurrence tree, we start from the given recurrence and keep drawing till we find
a pattern among levels. The pattern is typically arithmetic or geometric series.

For example, consider the recurrence relation

T(n) = T(n/4) + T(n/2) + cn 2
cn2
/ \
T(n/4) T(n/2)
If we further break down the expression T(n/4) and T(n/2),
we get the following recursion tree.
cn2
/ \
c(n2)/16 c(n2)/4
/ \ / \
T(n/16) T(n/8) T(n/8) T(n/4)
Breaking down further gives us following
cn2
/ \
c(n2)/16 c(n2)/4
/ \ / \
c(n2)/256 c(n2)/64 c(n2)/64 c(n2)/16
/ \ / \ / \ / \
To know the value of T(n), we need to calculate the sum of tree
nodes level by level. If we sum the above tree level by level,
we get the following series T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ….
The above series is a geometrical progression with a ratio of 5/16.
To get an upper bound, we can sum the infinite series. We get the sum as
(n2)/(1 – 5/16) which is O(n 2)

3. Master Method:
Master Method is a direct way to get the solution. The master method works
only for the following type of recurrences or for recurrences that can be
transformed into the following type.

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

There are the following three cases:
 If f(n) = O(n c) where c < Logba then T(n) = Θ(n Logba)
 If f(n) = Θ(n c) where c = Logba then T(n) = Θ(n cLog n)
 If f(n) = Ω(nc) where c > Logba then T(n) = Θ(f(n))
How does this work?
The master method is mainly derived from the recurrence tree method. If we
draw the recurrence tree of T(n) = aT(n/b) + f(n), we can see that the work done
at the root is f(n), and work done at all leaves is Θ(n c) where c is Logba. And the
height of the recurrence tree is Log bn
In the recurrence tree method, we calculate the total work done. If the work
done at leaves is polynomially more, then leaves are the dominant part, and our
result becomes the work done at leaves (Case 1). If work done at leaves and
root is asymptotically the same, then our result becomes height multiplied by
work done at any level (Case 2). If work done at the root is asymptotically more,
then our result becomes work done at the root (Case 3).
Examples of some standard algorithms whose time complexity can be
evaluated using the Master Method
 Merge Sort: T(n) = 2T(n/2) + Θ(n). It falls in case 2 as c is 1 and Log ba] is
also 1. So the solution is Θ(n Logn)
 Binary Search: T(n) = T(n/2) + Θ(1). It also falls in case 2 as c is 0 and Log ba
is also 0. So the solution is Θ(Logn)
Notes:
 It is not necessary that a recurrence of the form T(n) = aT(n/b) + f(n) can be
solved using Master Theorem. The given three cases have some gaps
between them. For example, the recurrence T(n) = 2T(n/2) + n/Logn cannot
be solved using master method.
 Case 2 can be extended for f(n) = Θ(n cLogkn)
If f(n) = Θ(ncLogkn) for some constant k >= 0 and c = Log ba, then T(n) =
Θ(ncLogk+1n)
Advanced master theorem for divide and
conquer recurrences:
The Master Theorem is a tool used to solve recurrence relations that arise in
the analysis of divide-and-conquer algorithms. The Master Theorem provides a
systematic way of solving recurrence relations of the form:
T(n) = aT(n/b) + f(n)
1. where a, b, and f(n) are positive functions and n is the size of the problem.
The Master Theorem provides conditions for the solution of the recurrence to
be in the form of O(n^k) for some constant k, and it gives a formula for
determining the value of k.
2. The advanced version of the Master Theorem provides a more general form
of the theorem that can handle recurrence relations that are more complex
than the basic form. The advanced version of the Master Theorem can
handle recurrences with multiple terms and more complex functions.
3. It is important to note that the Master Theorem is not applicable to all
recurrence relations, and it may not always provide an exact solution to a
given recurrence. However, it is a useful tool for analyzing the time
complexity of divide-and-conquer algorithms and provides a good starting
point for solving more complex recurrences.
Master Theorem is used to determine running time of algorithms (divide and
conquer algorithms) in terms of asymptotic notations.
Consider a problem that is solved using recursion.
function f(input x size n)
if(n < k)
solve x directly and return
else
divide x into a subproblems of size n/b
call f recursively to solve each subproblem
Combine the results of all sub-problems
The above algorithm divides the problem into a subproblems, each of size n/b
and solve them recursively to compute the problem and the extra work done for
problem is given by f(n), i.e., the time to create the subproblems and combine
their results in the above procedure.
So, according to master theorem the runtime of the above algorithm can be
expressed as:
T(n) = aT(n/b) + f(n)
where n = size of the problem
a = number of subproblems in the recursion and a >= 1
n/b = size of each subproblem
f(n) = cost of work done outside the recursive calls like dividing into
subproblems and cost of combining them to get the solution.
Not all recurrence relations can be solved with the use of the master theorem
i.e. if
 T(n) is not monotone, ex: T(n) = sin n
 f(n) is not a polynomial, ex: T(n) = 2T(n/2) + 2 n
This theorem is an advance version of master theorem that can be used to
determine running time of divide and conquer algorithms if the recurrence is of
the following form :-

where n = size of the problem

a = number of subproblems in the recursion and a >= 1
n/b = size of each subproblem
b > 1, k >= 0 and p is a real number.
Then,
1. if a > bk, then T(n) = θ(nlogba)
2. if a = bk, then
(a) if p > -1, then T(n) = θ(n logba logp+1n)
(b) if p = -1, then T(n) = θ(n logba loglogn)
(c) if p < -1, then T(n) = θ(n logba)

3. if a < bk, then

(a) if p >= 0, then T(n) = θ(n k logpn)
(b) if p < 0, then T(n) = θ(n k)

Time Complexity Analysis –

 Example-1: Binary Search – T(n) = T(n/2) + O(1)

a = 1, b = 2, k = 0 and p = 0
bk = 1. So, a = bk and p > -1 [Case 2.(a)]
T(n) = θ(nlogba logp+1n)
T(n) = θ(logn)
 Example-2: Merge Sort – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
bk = 2. So, a = bk and p > -1 [Case 2.(a)]
T(n) = θ(nlogba logp+1n)
T(n) = θ(nlogn)
 Example-3: T(n) = 3T(n/2) + n2
a = 3, b = 2, k = 2, p = 0
bk = 4. So, a < bk and p = 0 [Case 3.(a)]
T(n) = θ(nk logpn)
T(n) = θ(n2)

 Example-4: T(n) = 3T(n/2) + log2n

a = 3, b = 2, k = 0, p = 2
bk = 1. So, a > bk [Case 1]
T(n) = θ(nlogba )
T(n) = θ(nlog23)
 Example-5: T(n) = 2T(n/2) + nlog 2n
a = 2, b = 2, k = 1, p = 2
bk = 2. So, a = bk [Case 2.(a)]
T(n) = θ(nlogbalogp+1n )
T(n) = θ(nlog22log3n)
T(n) = θ(nlog3n)
 Example-6: T(n) = 2nT(n/2) + nn
This recurrence can’t be solved using above method since function is not of
form T(n) = aT(n/b) + θ(n k logpn)
Different types of recurrence relations and their solutions :
Type 1: Divide and conquer recurrence relations
Following are some of the examples of recurrence relations based on divide
and conquer.
T(n) = 2T(n/2) + cn
T(n) = 2T(n/2) + √n
These types of recurrence relations can be easily solved using Master Method.
For recurrence relation T(n) = 2T(n/2) + cn, the values of a = 2, b = 2 and k =1.
Here logb(a) = log2(2) = 1 = k. Therefore, the complexity will be Θ(nlog2(n)).
Similarly for recurrence relation T(n) = 2T(n/2) + √n, the values of a = 2, b = 2
and k =1/2. Here logb(a) = log2(2) = 1 > k. Therefore, the complexity will be
Θ(n).
Type 2: Linear recurrence relations
Following are some of the examples of recurrence relations based on linear
recurrence relation.
T(n) = T(n-1) + n for n>0 and T(0) = 1
These types of recurrence relations can be easily solved using substitution
method.
For example,
T(n) = T(n-1) + n
= T(n-2) + (n-1) + n
= T(n-k) + (n-(k-1))….. (n-1) + n
Substituting k = n, we get
T(n) = T(0) + 1 + 2+….. +n = n(n+1)/2 = O(n^2)
Type 3: Value substitution before solving –
Sometimes, recurrence relations can’t be directly solved using techniques like
substitution, recurrence tree or master method. Therefore, we need to convert
the recurrence relation into appropriate form before solving. For example,
T(n) = T(√n) + 1
To solve this type of recurrence, substitute n = 2^m as:
T(2^m) = T(2^m /2) + 1
Let T(2^m) = S(m),
S(m) = S(m/2) + 1
Solving by master method, we get
S(m) = Θ(logm)
As n = 2^m or m = log2(n),
T(n) = T(2^m) = S(m) = Θ(logm) = Θ(loglogn)

Previously Asked GATE Questions on Recurrence

Relations:
Que – 1. What is the time complexity of Tower of Hanoi problem?
(A) T(n) = O(sqrt(n))
(D) T(n) = O(n^2)
(C) T(n) = O(2^n)
(D) None
Solution: For Tower of Hanoi, T(n) = 2T(n-1) + c for n>1 and T(1) = 1. Solving
this,
T(n) = 2T(n-1) + c
= 2(2T(n-2)+ c) + c = 2^2*T(n-2) + (c + 2c)
= 2^k*T(n-k) + (c + 2c + .. kc)
Substituting k = (n-1), we get
T(n) = 2^(n-1)*T(1) + (c + 2c + (n-1)c) = O(2^n)
Que – 2. Consider the following recurrence:
T(n) = 2 * T(ceil (sqrt(n) ) ) + 1, T(1) = 1
Which one of the following is true?
(A) T(n) = (loglogn)
(B) T(n) = (logn)
(C) T(n) = (sqrt(n))
(D) T(n) = (n)
Solution: To solve this type of recurrence, substitute n = 2^m as:
T(2^m) = 2T(2^m /2) + 1
Let T(2^m) = S(m),
S(m) = 2S(m/2) + 1
Solving by master method, we get
S(m) = Θ(m)
As n = 2^m or m = log2n,
T(n) = T(2^m) = S(m) = Θ(m) = Θ(logn)
Que – 3. What is the value of following recurrence.
T(n) = T(n/4) + T(n/2) + cn 2
T(1) = c
T(0) = 0
Where c is a positive constant
(A) O(n3)
(B) O(n2)
(C) O(n2 Logn)
(D) O(nLogn)
Answer: (B)
Que – 4. What is the value of following recurrence.
T(n) = 5T(n/5) + ,
T(1) = 1,
T(0) = 0
(A) Theta (n)
(B) Theta (n^2)
(C) Theta (sqrt(n))
(D) Theta (nLogn)
Answer: (A)
Que – 5. Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which one of the following is false. ( GATE CS 2005)
a) T(n) = O(n^2)
b) T(n) = θ(nLogn)
c) T(n) = Ω(n^2)
d) T(n) = O(nLogn)
(A) A
(B) B
(C) C
(D) D
Answer: (C)
Que – 6. The running time of an algorithm is represented by the following
recurrence relation:
if n <= 3 then T(n) = n
else T(n) = T(n/3) + cn
Which one of the following represents the time complexity of the algorithm?
(A) θ(n)
(B) θ(n log n)
(C) θ(n^2)
(D) θ(n^2log n)
Answer: (A)
Que – 7. The running time of the following algorithm
Procedure A(n)
If n <= 2 return(1) else return A( );
is best described by
(A) O(n)
(B) O(log n)
(C) O(1og log n)
(D) O(1)
Answer: (C)
Que – 8. The time complexity of the following C function is (assume n > 0
(GATE CS 2004)
int recursive (mt n)
{
if (n == 1)
return (1);
else
return (recursive (n-1) + recursive (n-1));
}
(A) 0(n)
(B) 0(nlogn)
(C) 0(n^2)
(D) 0(2^n)
Answer: (D)
Que – 9. Which one of the following correctly determines the solution of
the recurrence relation with T(1) = 1? (GATE-CS-2014-(Set-2))
T(n) = 2T(n/2) + Logn
(A) Θ(n)
(B) Θ(nLogn)
(C) Θ(n*n)
(D) Θ(log n)
Answer: (A)
Que – 10. Consider the recurrence relation a 1 = 8, an = 6n2 + 2n + an-1. Let
a99 = k x 104. The value of K is _____. (GATE-CS-2016 (Set 1))
Note : This question was asked as Numerical Answer Type.
(A) 190
(B) 296
(C) 198
(D) 200
Answer: (C)

Array Notes for GATE Exam [2024]





Arrays are fundamental data structures in computer science

Table of Content
 Introduction to Arrays
 Basic terminologies of the array
 Representation of Array
 Types of arrays
 Finding Adress of an Element in Array
 Calculating the address of any element In the 1-D array
 Calculate the address of any element in the 2-D array
 Calculate the address of any element in the 3-D Array
 Previously Asked GATE Questions on Arrays
Introduction to Arrays:
An array is a collection of items of the same variable type that are
stored at contiguous memory locations. It’s one of the most popular
and simple data structures and is often used to implement other data
structures. Each item in an array is indexed starting with 0.

Basic terminologies of the array:

 Array Index: In an array, elements are identified by their indexes.
Array index starts from 0.
 Array element: Elements are items stored in an array and can be
accessed by their index.
 Array Length: The length of an array is determined by the number
of elements it can contain.
Representation of Array:
The representation of an array can be defined by its declaration. A
declaration means allocating memory for an array of a given size.

Representation of Array

Arrays can be declared in various ways in different languages. For

better illustration, below are some language-specific array
declarations.

int arr[5]; // This array will store integer type element

char arr[10]; // This array will store char type element

float arr[20]; // This array will store float type element

Learn Data Structures & Algorithms with GeeksforGeeks

However, the above declaration is static or compile-time memory

allocation, which means that the array element’s memory is allocated
when a program is compiled. Here only a fixed size (i,e. the size that is
mentioned in square brackets []) of memory will be allocated for
storage, but don’t you think it will not be the same situation as we
know the size of the array every time, there might be a case where we
don’t know the size of the array. If we declare a larger size and store a
lesser number of elements will result in a wastage of memory or either
be a case where we declare a lesser size then we won’t get enough
memory to store the rest of the elements. In such cases, static
memory allocation is not preferred.
Types of arrays:
There are mainly three types of arrays:
1. One Dimensional Array
2. Two Dimensional Array
3. Three-Dimensional Array
1. One Dimensional Array:
 It is a list of the variable of similar data types.
 It allows random access and all the elements can be accessed with
the help of their index.
 The size of the array is fixed.
 For a dynamically sized array, vector can be used in C++
Representation of 1D array:

Representation of the 1D array

2. Two Dimensional Array:

 It is a list of lists of the variable of the same data type.
 It also allows random access and all the elements can be accessed
with the help of their index.
 It can also be seen as a collection of 1D arrays. It is also known as
the Matrix.
 Its dimension can be increased from 2 to 3 and 4 so on.
 They all are referred to as a multi-dimension array.
 The most common multidimensional array is a 2D array.
Representation of 2 D array:
Representation of 2D Array

3. Three-Dimensional Array:
A Three Dimensional Array or 3D array in C is a collection of two-
dimensional arrays. It can be visualized as multiple 2D arrays stacked
on top of each other.

Representation of 3D array

Declaration of Three-Dimensional Array:

We can declare a 3D array with x 2D arrays each having y rows
and z columns using the syntax shown below.
Syntax:
data_type array_name[x][y][z];
 data_type: Type of data to be stored in each element.
 array_name: name of the array
 x: Number of 2D arrays.
 y: Number of rows in each 2D array.
 z: Number of columns in each 2D array.

Finding Address of an Element in Array

When it comes to organizing and accessing elements in a multi-
dimensional array, two prevalent methods are Row Major
Order and Column Major Order.
1. Row Major Order
Row major ordering assigns successive elements, moving across the
rows and then down the next row, to successive memory locations. In
simple language, the elements of an array are stored in a Row-Wise
fashion.
To find the address of the element using row-major order uses the
following formula:
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in an array(in byte),
LR = Lower Limit of row/start row index of the matrix(If not given
assume it as zero),
LC = Lower Limit of column/start column index of the matrix(If not
given assume it as zero),
N = Number of column given in the matrix.
2. Column Major Order
If elements of an array are stored in a column-major fashion means
moving across the column and then to the next column then it’s in
column-major order. To find the address of the element using column-
major order use the following formula:
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))
I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LR = Lower Limit of row/start row index of matrix(If not given assume
it as zero),
LC = Lower Limit of column/start column index of matrix(If not given
assume it as zero),
M = Number of rows given in the matrix.

Calculating the address of any element In the

1-D array:
A 1-dimensional array (or single-dimension array) is a type of linear
array. Accessing its elements involves a single subscript that can
either represent a row or column index.
Example:

1D array

To find the address of an element in an array the

following formula is used:
Address of A[I] = B + W * (I – LB)
I = Subset of element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LB = Lower Limit/Lower Bound of subscript(If not specified assume
zero).
Example: Given the base address of an array A[1300 …………
1900] as 1020 and the size of each element is 2 bytes in the memory,
find the address of A[1700].
Solution:
Given:
Base address B = 1020
Lower Limit/Lower Bound of subscript LB = 1300
Storage size of one element store in any array W = 2 Byte
Subset of element whose address to be found I = 1700
Formula used:
Address of A[I] = B + W * (I – LB)
Solution:
Address of A[1700] = 1020 + 2 * (1700 – 1300)
= 1020 + 2 * (400)
= 1020 + 800
Address of A[1700] = 1820

Calculate the address of any element in the

2-D array:
The 2-dimensional array can be defined as an array of arrays. The 2-
Dimensional arrays are organized as matrices which can be
represented as the collection of rows and columns as array[M][N]
where M is the number of rows and N is the number of columns.
Example:

2-D Array

Finding address of an element using Row Major Order:

Given an array, arr[1………10][1………15] with base value 100 and
the size of each element is 1 Byte in memory. Find the address
of arr[8][6] with the help of row-major order.
Solution:
Given:
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of column given in the matrix N = Upper Bound – Lower Bound
+1
= 15 – 1 + 1
= 15
Formula:
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
Solution:
Address of A[8][6] = 100 + 1 * ((8 – 1) * 15 + (6 – 1))
= 100 + 1 * ((7) * 15 + (5))
= 100 + 1 * (110)
Address of A[I][J] = 210
Finding address of an element using Column Major Order:
Given an array arr[1………10][1………15] with a base value
of 100 and the size of each element is 1 Byte in memory find the
address of arr[8][6] with the help of column-major order.
Solution:
Given:
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of Rows given in the matrix M = Upper Bound – Lower Bound
+1
= 10 – 1 + 1
= 10
Formula: used
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))
Address of A[8][6] = 100 + 1 * ((6 – 1) * 10 + (8 – 1))
= 100 + 1 * ((5) * 10 + (7))
= 100 + 1 * (57)
Address of A[I][J] = 157
From the above examples, it can be observed that for the same
position two different address locations are obtained that’s because in
row-major order movement is done across the rows and then down to
the next row, and in column-major order, first move down to the first
column and then next column. So both the answers are right.
Calculate the address of any element in the
3-D Array:
A 3-Dimensional array is a collection of 2-Dimensional arrays. It is
specified by using three subscripts:
1. Block size
2. Row size
3. Column size
More dimensions in an array mean more data can be stored in that
array.
Example:

3-D Array

To find the address of any element in 3-Dimensional arrays there are

the following two ways:
 Row Major Order
 Column Major Order
Row Major Order:
To find the address of the element using row-major order, use the
following formula:
Address of A[i][j][k] = B + W *(M * N * (i-x) + N *(j-y) + (k-z))
Here:
B = Base Address (start address)
W = Weight (storage size of one element stored in the array)
M = Row (total number of rows)
N = Column (total number of columns)
P = Width (total number of cells depth-wise)
x = Lower Bound of Row
y = Lower Bound of Column
z = Lower Bound of Width
Example: Given an array, arr[1:9, -4:1, 5:10] with a base value
of 400 and the size of each element is 2 Bytes in memory find the
address of element arr[5][-1][8] with the help of row-major order?
Solution:
Given:
Block Subset of an element whose address to be found I = 5
Row Subset of an element whose address to be found J = -1
Column Subset of an element whose address to be found K = 8
Base address B = 400
Storage size of one element store in any array(in Byte) W = 2
Lower Limit of blocks in matrix x = 1
Lower Limit of row/start row index of matrix y = -4
Lower Limit of column/start column index of matrix z = 5
M(row) = Upper Bound – Lower Bound + 1 = 1 – (-4) + 1 = 6
N(Column)= Upper Bound – Lower Bound + 1 = 10 – 5 + 1 = 6

Formula used:
Address of[I][J][K] =B + W (M * N(i-x) + N *(j-y) + (k-z))
Solution:
Address of arr[5][-1][8] = 400 + 2 * {[6 * 6 * (5 – 1)] + 6 * [(-1 + 4)]}
+ [8 – 5]
= 400 + 2 * (6*6*4)+(6*3)+3
= 400 + 2 * (165)
= 730
Column Major Order:
To find the address of the element using column-major order, use the
following formula:1
Address of A[i][j][k]= B + W(M * N(i – x) + M *(k – z) + (j – y))
Here:
B = Base Address (start address)
W = Weight (storage size of one element stored in the array)
M = Row (total number of rows)
N = Column (total number of columns)
P = Width (total number of cells depth-wise)
x = Lower Bound of block (first subscipt)
y = Lower Bound of Row
z = Lower Bound of Column
Example: Given an array arr[1:8, -5:5, -10:5] with a base value
of 400 and the size of each element is 4 Bytes in memory find the
address of element arr[3][3][3] with the help of column-major order ?
Solution:
Given:
Row Subset of an element whose address to be found I = 3
Column Subset of an element whose address to be found J = 3
Block Subset of an element whose address to be found K = 3
Base address B = 400
Storage size of one element store in any array(in Byte) W = 4
Lower Limit of blocks in matrix x = 1
Lower Limit of row/start row index of matrix y = -5
Lower Limit of column/start column index of matrix z = -10
M (row)= Upper Bound – Lower Bound + 1 = 5 +5 + 1 = 11
N (column)= Upper Bound – Lower Bound + 1 = 5 + 10 + 1 = 16
Formula used:
Address of[i][j][k] = B + W(M * N(i – x) + M * (j-y) + (k – z))
Solution:
Address of arr[3][3][3] = 400 + 4 * ((11*16*(3-1)+11*(3-(-5)+(3-(-10)))
= 400 + 4 * ((176*2 + 11*8 + 13)
= 400 + 4 * (453)
= 400 + 1812
= 2212

Previously Asked GATE Questions on Arrays:

Question 1: A program P reads in 500 integers in the range [0..100]
representing the scores of 500 students. It then prints the frequency of
each score above 50. What would be the best way for P to store the
frequencies?
(a) An array of 50 numbers.
(b) An array of 100 numbers.
(c) An array of 500 numbers.
(d) A dynamically allocated array of 550 numbers
Answer: (a)
Explanation: An array of 50 numbers is correct.
Question 2: What will the output of the below code?
 C++
#include <iostream>

using namespace std;

int main()

int arr[2] = { 1, 2 };

cout << 0 [arr] << ", " << 1 [arr] << endl;

return 0;

(a) 1, 2
(b) Syntax error
(c) Run time error
(d) None
Answer: (a)
Explanation: 0[arr]] is a different way to represent array element,
which represents the first element of the array.
similarly, 1[arr] is a different way to represent array element, which
represents the second element of the array.
Question 3: The minimum number of comparisons required to
determine if an integer appears more than n/2 times in a sorted array
of n integers is
(a) O(n)
(b) O(log(n))
(c) O(nlog(n))
(d) O(1)
Answer: (b)
Explanation: If you answered Theta(1), then think of examples {1, 2,
2, 2, 4, 4}, {1, 1, 2, 2, 2, 2, 3, 3} The Best way to find out whether an
integer appears more than n/2 times in a sorted array(Ascending
Order) of n integers, would be binary search approach.
1. The First occurrence of an element can be found out in O(log(n))
time using divide and conquer technique,lets say it is i.
2. The Last occurrence of an element can be found out in O(log(n))
time using divide and conquer technique,lets say it is j.
3. Now number of occurrence of that element(count) is (j-i+1). Overall
time complexity = log n +log n +1 = O(log(n)).
Question 4: Let A be a square matrix of size n x n. Consider the
following program. What is the expected output?
C = 100
for i = 1 to n do
for j = 1 to n do
{
Temp = A[i][j] + C
A[i][j] = A[j][i]
A[j][i] = Temp - C
}
for i = 1 to n do
for j = 1 to n do
Output(A[i][j]);

Answer: 1
Explanation: If we take look at the inner statements of first loops, we
can notice that the statements swap A[i][j] and A[j][i] for all i and j.
Since the loop runs for all elements, every element A[l][m] would be
swapped twice, once for i = l and j = m and then for i = m and j = l.
Swapping twice means the matrix doesn’t change.
Question 5: An algorithm performs (logN)1/2 find operations, N insert
operations, (logN)1/2 delete operations, and (logN)1/2 decrease-key
operations on a set of data items with keys drawn from a linearly
ordered set. For a delete operation, a pointer is provided to the record
that must be deleted. For the decrease-key operation, a pointer is
provided to the record that has its key decreased. Which one of the
following data structures is the most suited for the algorithm to use, if
the goal is to achieve the best total asymptotic complexity considering
all the operations?
(a) Unsorted array
(b) Min-heap
(c) Sorted array
(d) Sorted doubly linked list
Answer: (a)
Explanation: The time complexity of insert in unsorted array is O(1),
O(Logn) in Min-Heap, O(n) in sorted array and sorted DLL.
 For unsorted array, we can always insert an element at end and do
insert in O(1) time
 For Min Heap, insertion takes O(Log n) time. Refer Binary Heap
operations for details.
 For sorted array, insert takes O(n) time as we may have to move all
elements worst case.
 For sorted doubly linked list, insert takes O(n) time to find position
of element to be inserted.
Question 6: Consider an array consisting of –ve and +ve numbers.
What would be the worst case time complexity of an algorithm to
segregate the numbers having same sign altogether i.e all +ve on one
side and then all -ve on the other ?
(a) O(N)
(b) O(Nlog(N))
(c) O(N*N)
(d) O(Nlog(log(N)))
Answer: (c)
Explanation: Here we can use the partition algorithm of quick
sort for segregation and answer will be O(N*N). Choose the first
element as pivot whatever may be its sign we don’t care and keep an
extra index at pivot position.
Question 7: Let A[1…n] be an array of n distinct numbers. If i <
j and A[i] > A[j], then the pair (i, j) is called an inversion of A. What is
the expected number of inversions in any permutation on n elements ?
(a) n(n-1)/2
(b) n(n-1)/4
(c) n(n+1)/4
(d) 2nlog(n)
Answer: (b)
Explanation: There are n(n-1)/2 pairs such that i < j. For a pair (a i,
aj), probability of being inversion is 1/2. Therefore expected value of
inversions = 1/2 * (n(n-1)/2) = n(n-1)/4.
Question 8: Consider the following array declaration in the ‘C’
language:
int array 1[] = {2, 3};
int array2[3]={9};
What will be the output of the following print statement?
printf(“%d, %d”, array1 [1], array2 [2]);
(a) 2, 0
(b) 3, 0
(c) 2, 9
(d) 4, 9
Answer: (b)
Question 9: Consider the following C program.
#include < stdio.h >
int main () {
int a [4] [5] = {{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20}};
printf (“%d\n”, *(*(a+**a+2) +3));
return (0);
}
The output of the program is _______.
Answer: 19
Question 10: Which operations can not be done in O(1) for an array of
sorted data.
(a) Print the nth largest element
(b) Print the nth smallest element
(c) Delete element
(d) None of the above
Answer: (c)
Explanation: If we have to delete x and its index is last, it would take
O(n).

Table of Content
 What is Linked List?
 Singly Linked List
 Doubly Linked List
 Circular Linked List
 Applications of Linked List
 Advantages of Linked Lists
 Disadvantages of Linked Lists
 Previous Year GATE Questions on Linked List:

What is Linked List?

A linked list is a linear data structure, in which the elements are not
stored at contiguous memory locations. Linked list consists of nodes
where each node contains a data field and a reference(link) to the next
node in the list.
The elements in a linked list are linked using pointers as shown in the
below image:

Linked-List-Data-Structure

Singly Linked List:

A singly linked list is a linear data structure in which the elements
are not stored in contiguous memory locations and each element is
connected only to its next element using a pointer.
The elements in a linked list are linked using pointers to the next node
as shown in the below image:

Singly Linked List

Operations on Singly Linked List:

 Insertion at the beginning of the Linked List: To insert a node
at the beginning of the Linked List, we change the next pointer of
the new node to the current head and make the new node as the
current head. Time Complexity: O(1)
 Insertion at the end or after a given node: To insert a node
after a given node, we need to update the next pointer of the new
node to the next pointer of the given node and update the next
pointer of the given node to the new node. Time
Complexity: O(N) as in the worst case we may traverse through all
the nodes of the linked list.
 Searching an element: We can search a node by traversing
through the linked list and comparing the nodes one by one. Time
Complexity: O(N)
 Find length of the Linked List: We can find the length of the
linked list by traversing through the linked list and maintaining the
count of nodes. Time Complexity: O(N)
 Reverse a Linked List: We can reverse a linked list using three
pointers curr, prev, and next to keep track of nodes to update
reverse links. Time Complexity: O(N)
 Deletion at the beginning of the Linked List: To delete a node
from the beginning of the Linked List, we can change the head to
the next of the current head and delete the previous head. Time
Complexity: O(1)
 Deletion at the end or after a given node: To delete a node
after a given node, we need to update the next pointer of the given
node to point to the node which is present after the node to be
deleted. Time Complexity: O(N) as in the worst case we may
traverse through all the nodes of the linked list.
Doubly Linked List:
A doubly linked list (DLL) is a special type of linked list in which
each node contains a pointer to the previous node as well as the next
node of the linked list.
The elements in a linked list are linked using pointers to the next node
as well as to the previous node as shown in the below image:
Doubly Linked List

All operations of Circular Singly Linked List are same as of Singly

Linked List, except that we need to update the previous pointers along
with the next pointers whenever we insert or delete a node.
Circular Linked List:
The circular linked list is a linked list where all nodes are connected
to form a circle. In a circular linked list, the first node and the last node
are connected to each other which forms a circle. There is no NULL at
the end.
The elements in a linked list are linked using pointers to the next node
with the last node pointing to the head of the linked list as shown in
the below image:

Circular Singly Linked List

All operations of Circular Singly Linked List are same as of Singly

Linked List.
There are two types of Circular Linked List:
 Circular singly linked list: In a circular Singly linked list, the last
node of the list contains a pointer to the first node of the list. We
traverse the circular singly linked list until we reach the same node
where we started. The circular singly linked list has no beginning or
end. No null value is present in the next part of any of the nodes.
 Circular Doubly linked list: Circular Doubly Linked List has
properties of both doubly linked list and circular linked list in which
two consecutive elements are linked or connected by the previous
and next pointer and the last node points to the first node by the
next pointer and also the first node points to the last node by the
previous pointer.
Circular Doubly Linked List

Note: Unlike other types of Linked Lists, Circular Doubly Linked List
takes O(1) time for insertion or deletion at the end of the Linked List.
Applications of Linked List:
 Image viewer – Previous and next images are linked and can be
accessed by the next and previous buttons.
 Previous and next page in a web browser – We can access the
previous and next URL searched in a web browser by pressing the
back and next buttons since they are linked as a linked list.
 Music Player – Songs in the music player are linked to the previous
and next songs. So you can play songs either from starting or
ending of the list.
 GPS navigation systems– Linked lists can be used to store and
manage a list of locations and routes, allowing users to easily
navigate to their desired destination.
Advantages of Linked Lists:
 Dynamic Size: Linked lists can grow or shrink dynamically, as
memory allocation is done at runtime.
 Insertion and Deletion: Adding or removing elements from a
linked list is efficient, especially for large lists.
 Flexibility: Linked lists can be easily reorganized and modified
without requiring a contiguous block of memory.
Disadvantages of Linked Lists:
 Random Access: Unlike arrays, linked lists do not allow direct
access to elements by index. Traversal is required to reach a
specific node.
 Extra Memory: Linked lists require additional memory for storing
the pointers, compared to arrays.
Gate Archives on Linked List:
Q1. Consider the problem of reversing a singly linked list. To take an
example, given the linked list below,

the reversed linked list should look like

Which one of the following statements is TRUE about the time

complexity of algorithms that solve the above problem in O(1) space?
(A) The best algorithm for the problem takes Θ(N) time in the worst
case
(B) The best algorithm for the problem takes Θ(N * logN) time in the
worst case.
(C) The best algorithm for the problem takes Θ(N*N) time in the worst
case
(D) It is not possible to reverse a singly linked list in O(1) space.
Answer: (A)
Explanation: The given linked list is a reverse linked list and the best
algorithm in reverse linked list takes time in the worst case. So, option
A is the correct answer.
Q2. What is the worst-case time complexity of inserting n elements
into an empty linked list, if the linked list needs to be maintained in
sorted order?
(A) Θ(n)
(B) Θ(n log n)
(C) Θ(n2)
(D) Θ(1)
Answer: (C)
Explanation: If we want to insert n elements into an empty linked list
that needs to be maintained in sorted order, the worst-case time
complexity would be O(n^2). This is because we would need to
traverse the list for each element we want to insert, to find the correct
position for the element in the sorted list.
Q3. What does the following function do for a given Linked List with
first node as head?
void fun1(struct node* head)
{
if(head == NULL)
return;

fun1(head->next);
printf("%d ", head->data);
}

(A) Prints all nodes of linked list

(B) Prints all nodes of linked list in reverse order
(C) Prints alternate nodes of Linked List
(D) Prints alternate nodes in reverse order
Answer: (B)
Explanation: It first checks if the head is NULL, and if it is, it returns
without doing anything. Otherwise, it calls the fun1 function
recursively with the next node in the linked list (head->next). This
continues until the last node is reached, which is the node
whose next pointer is NULL. At this point, the function starts
returning, and as it returns it prints the value of each node in the
linked list starting from the last node, working its way backwards to
the first node. This is achieved through the printf statement which
prints the value of head->data.
Q4. Which of the following points is/are true about Linked List data
structure when it is compared with array?
(A) Arrays have better cache locality that can make them better in
terms of performance.
(B) It is easy to insert and delete elements in Linked List
(C) Random access is not allowed in a typical implementation of
Linked Lists
(D) The size of array has to be pre-decided, linked lists can change
their size any time.
(E) All of the above
Answer: (E)
Explanation: The following points are true when comparing Linked
List data structure with an array:
 Insertion and deletion: Linked lists allow for efficient insertion and
deletion operations at any point in the list, as they involve simply
adjusting pointers, while in an array, these operations can be
expensive as all the elements after the insertion or deletion point
need to be shifted.
 Memory allocation: Linked lists use dynamic memory allocation, so
they can grow or shrink as needed, while arrays have a fixed size
and need to be allocated a contiguous block of memory upfront.
 Access time: Arrays provide constant-time access to any element in
the array (assuming the index is known), while accessing an
element in a linked list takes linear time proportional to the number
of elements in the list, as the list needs to be traversed from the
beginning to find the desired element.
 Random access: Arrays support random access, which means that
we can directly access any element in the array with its index, while
linked lists do not support random access and we need to traverse
the list to find a specific element.
Q5. Consider the following function that takes reference to head of a
Doubly Linked List as parameter. Assume that a node of doubly linked
list has previous pointer as prev and next pointer as next.
C

void fun(struct node **head_ref)

struct node *temp = NULL;

struct node *current = *head_ref;

while (current != NULL)

temp = current->prev;

current->prev = current->next;

current->next = temp;
current = current->prev;

if(temp != NULL )

*head_ref = temp->prev;

Assume that reference of head of following doubly linked list is passed

to above function 1 <–> 2 <–> 3 <–> 4 <–> 5 <–>6. What should be
the modified linked list after the function call?
(A) 2 <–> 1 <–> 4 <–> 3 <–> 6 <–>5
(B) 5 <–> 4 <–> 3 <–> 2 <–> 1 <–>6
(C) 6 <–> 5 <–> 4 <–> 3 <–> 2 <–> 1
(D) 6 <–> 5 <–> 4 <–> 3 <–> 1 <–> 2
Answer: (C)
Explanation: This function fun takes a double pointer to the head of a
doubly linked list as its argument and reverses the order of the nodes
in the list.
Q6. Which of the following sorting algorithms can be used to sort a
random linked list with minimum time complexity?
(A) Insertion Sort
(B) Quick Sort
(C) Heap Sort
(D) Merge Sort
Answer: (D)
Explanation: Both Merge sort and Insertion sort can be used for
linked lists. The slow random-access performance of a linked list
makes other algorithms (such as quicksort) perform poorly, and others
(such as heapsort) completely impossible. Since worst case time
complexity of Merge Sort is O(nLogn) and Insertion sort is O(n^2),
merge sort is preferred. See following for implementation of merge
sort using Linked List.
Q7. The following function reverse() is supposed to reverse a singly
linked list. There is one line missing at the end of the function.
C

/* Link list node */

struct node

int data;

struct node* next;

};

/* head_ref is a double pointer which points to head (or start) pointer

of linked list */

static void reverse(struct node** head_ref)

struct node* prev = NULL;

struct node* current = *head_ref;

struct node* next;

while (current != NULL)

next = current->next;

current->next = prev;

prev = current;
current = next;

/*ADD A STATEMENT HERE*/

What should be added in place of “/*ADD A STATEMENT HERE*/”, so

that the function correctly reverses a linked list.
(A) *head_ref = prev;
(B) *head_ref = current;
(C) *head_ref = next;
(D) *head_ref = NULL;
Answer: (A)
Explanation: The statement to update the head pointer could be as
follows
*head_ref = prev;
This statement sets the value of *head_ref (which is a double pointer)
to the value of prev, which is the new head of the reversed list.
Q8. What is the output of following function in which start is pointing
to the first node of the following linked list 1->2->3->4->5->6 ?
C

void fun(struct node* start)

if(start == NULL)

return;

printf("%d ", start->data);

if(start->next != NULL )

fun(start->next->next);

printf("%d ", start->data);

(A) 1 4 6 6 4 1
(B) 1 3 5 1 3 5
(C) 1 2 3 5
(D) 1 3 5 5 2 3 1
Answer: (B)
Explanation: The function prints the data of the current node and
then recursively calls itself with the second next node (i.e., start-
>next->next).
So, it prints the data of every alternate node of the linked list i.e 1 3 5,
and then, since the next->next of 5 is null, it returns and prints the
data of the current node, so it then prints 5 3 1.
Therefore, for the given linked list 1->2->3->4->5->6, the function
would print 1 3 5 5 3 1.
Q9. The following C function takes a simply-linked list as input
argument. It modifies the list by moving the last element to the front of
the list and returns the modified list. Some part of the code is left
blank. Choose the correct alternative to replace the blank line.
C

typedef struct node {

int value;

struct node* next;

} Node;
Node* move_to_front(Node* head)

Node *p, *q;

if ((head == NULL: || (head->next == NULL))

return head;

q = NULL; p = head;

while (p-> next !=NULL)

q = p;

p = p->next;

_______________________________

return head;

(A) q = NULL; p->next = head; head = p;

(B) q->next = NULL; head = p; p->next = head;
(C) head = p; p->next = q; q->next = NULL;
(D) q->next = NULL; p->next = head; head = p;
Answer: (D)
Explanation: To move the last element to the front of the list, we
need to do the following steps:
1. Make the second last node as the last node (i.e., set its next pointer
to NULL).
2. Set the next pointer of the current last node (which is now the
second last node) to the original head node.
3. Make the current last node as the new head node.
Q10. The following function takes a single-linked list of integers as a
parameter and rearranges the elements of the list. The function is
called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given
order. What will be the contents of the list after the function completes
execution?
Java

class Node {

int value;

Node next;

void rearrange(Node list) {

Node p, q;

int temp;

if (list == null || list.next == null) {

return;

p = list;

q = list.next;

while (q != null) {

temp = p.value;

p.value = q.value;
q.value = temp;

p = q.next;

q = p != null ? p.next : null;

(A) 1 4 6 6 4 1
(B) 1 3 5 1 3 5
(C) 1 2 3 5
(D) 1 3 5 5 2 3 1
Answer: (B)
Explanation: The function rearrange() exchanges data of every node
with its next node. It starts exchanging data from the first node itself.
For eg. 3,5,7,9,11

A Queue is defined as a linear data structure that is open at both ends and the
operations are performed in First In First Out (FIFO) order. Queue is a list in
which all additions to the list are made at one end, and all deletions from the list
are made at the other end. The element, which is first pushed into the order,
the operation is first performed on that.
FIFO Property in Queue

Table of Content
 Implementing Queues using Arrays:
 Implementing Queues using Linked List:
 Implementation of Queue using Stack:
 Circular Queue:
 Priority Queue:
 Double Ended Queue:
 GATE Archives – Previous Years Questions on Queue:
Implementing Queues using Arrays:
To implement a queue using an array,
 Create an array arr of size n and
 Take two variables front and rear both of which will be initialized to 0 which
means the queue is currently empty.
 Element
 rear is the index up to which the elements are stored in the array
and
 front is the index of the first element of the array.
Now, some of the implementations of queue operations are as follows:
 Enqueue: Addition of an element to the queue. Adding an element will be
performed after checking whether the queue is full or not. If rear < n which
indicates that the array is not full then store the element at arr[rear] and
increment rear by 1 but if rear == n then it is said to be
an Overflow condition as the array is full. Enqueue has O(1) time
complexity.
 Dequeue: Removal of an element from the queue. An element can only be
deleted when there is at least an element to delete i.e. rear > 0. Now, the
element at arr[front] can be deleted but all the remaining elements have to
shift to the left by one position in order for the dequeue operation to delete
the second element from the left on another dequeue operation. Dequeue
has O(N) time complexity.
 Front: Get the front element from the queue i.e. arr[front] if the queue is not
empty. Accessing the front of the queue has O(1) time complexity.
 Display: Print all elements of the queue. If the queue is non-empty, traverse
and print all the elements from the index front to rear. Displaying all the
elements has O(N) time complexity.
 Overall Space Complexity: O(N)

Implementing Queues using Linked List:

To implement a queue using a Linked List,
 Maintain two pointers, front and rear. The front points to the first item of the
queue and rear points to the last item.
 enQueue(): This operation adds a new node after the rear and
moves the rear to the next node.
 deQueue(): This operation removes the front node and moves the
front to the next node.
Now, some of the implementations of queue operations are as follows:
 Create a class QNode with data members integer data and QNode*
next (pointer to the next node)
 Create a class Queue with data members QNode front and rear
 Enqueue Operation with parameter x:
 Initialize QNode* temp with data = x
 If the rear is set to NULL then set the front and rear to temp and
return (Base Case)
 Else set rear next to temp and then move rear to temp
 Enqueue has O(1) time complexity.
 Dequeue Operation:
 If the front is set to NULL return (Base Case)
 Initialize QNode temp with front and set front to its next
 If the front is equal to NULL then set the rear to NULL
 Delete temp from the memory.
 Dequeue has O(1) time complexity.
 Overall Space Complexity: O(N)

Implementation of Queue using Stack:

A queue can be implemented using two stacks. Let queue to be implemented
be q and stacks used to implement q be stack1 and stack2. q can be
implemented in three ways:

Method 1 (By making enQueue operation costly): This method makes sure
that oldest entered element is always at the top of stack 1, so that deQueue
operation just pops from stack1. To put the element at top of stack1, stack2 is
used.
enQueue(q, x):
 While stack1 is not empty, push everything from stack1 to stack2.
 Push x to stack1 (assuming size of stacks is unlimited).
 Push everything back to stack1.
 Time complexity will be O(N).
deQueue(q):
 If stack1 is empty, then error
 Pop an item from stack1 and return it.
 Time complexity will be O(1).
Method 2 (By making deQueue operation costly): In this method, in en-
queue operation, the new element is entered at the top of stack1. In de-queue
operation, if stack2 is empty then all the elements are moved to stack2 and
finally top of stack2 is returned.

enQueue(q, x):
 Push x to stack1 (assuming size of stacks is unlimited).
 Time complexity will be O(1)
deQueue(q):
 If both stacks are empty then error.
 If stack2 is empty, while stack1 is not empty, push everything from stack1 to
stack2.
 Pop the element from stack2 and return it.
 Time complexity will be O(N)
Method 2 is definitely better than method 1. Method 1 moves all the elements
twice in enQueue operation, while method 2 (in deQueue operation) moves the
elements once and moves elements only if stack2 empty. So, the amortized
complexity of the dequeue operation becomes Θ(1)
Method 3 (Using one user stack and one function call stack): Method 2
can be modified where recursion (or Function Call Stack) is used to implement
queue using only one user defined stack.
enQueue(x):
 Push x to stack1.
 Time complexity will be O(1)
deQueue():
 If stack1 is empty, then error.
 If stack1 has only one element, then return it.
 Recursively pop everything from the stack1, store the popped item in
variable res, push the res back to stack1 and return res.
 Time Complexity will be O(N).
Circular Queue:
A Circular Queue is an extended version of a normal queue where the last
element of the queue is connected to the first element of the queue forming a
circle. The operations are performed based on FIFO (First In First Out)
principle. It is also called ‘Ring Buffer’.

Operations on Circular Queue:

 Front: Get the front item from the queue. Accessing the front element
has O(1) time complexity.
 Rear: Get the last item from the queue. Accessing the rear element
has O(1) time complexity.
 enQueue(value): This function is used to insert an element into the circular
queue. In a circular queue, the new element is always inserted at the rear
position.
 Check whether the queue is full – [i.e., the rear end is in just before
the front end in a circular manner].
 If it is full then display Queue is full, else insert an element at the
end of the queue.
 The time complexity is O(1).
 deQueue(): This function is used to delete an element from the circular
queue. In a circular queue, the element is always deleted from the front
position.
 Check whether the queue is Empty.
 If it is empty, then display Queue is empty, else get the last element
and remove it from the queue.
 The Time Complexity is O(1).
Applications of Circular Queue:
 In a page replacement algorithm, a circular list of pages is maintained and
when a page needs to be replaced, the page in the front of the queue will be
chosen.
 Computer systems supply a holding area for maintaining communication
between two processes or two programs. This memory area is also known
as a ring buffer.
 CPU Scheduling: In the Round-Robin scheduling algorithm, a circular
queue is utilized to maintain processes that are in a ready state.
Priority Queue:
A priority queue is a type of queue that arranges elements based on
their priority values. Elements with higher priority values are typically
retrieved before elements with lower priority values.
If we add an element with a high priority value to a priority queue, it may be
inserted near the front of the queue, while an element with a low priority value
may be inserted near the back.
Types of Priority Queue:
 Descending Order Priority Queue Max Heap: Higher Priority values are
given more priority as compared to Lower Priority values.
 Ascending Order Priority Queue or Min Heap: Lower Priority values are
given more priority as compared to Higher Priority values.
Properties of Priority Queue:
 Every item has a priority associated with it.
 An element with high priority is dequeued before an element with low priority.
 If two elements have the same priority, they are served according to their
order in the queue.
In the below priority queue, an element with a maximum ASCII value will have
the highest priority. The elements with higher priority are served first.
Operations on Priority Queue:
 Insertion in a Priority Queue: When a new element is inserted in a priority
queue, it is placed after the last element and is swapped with the parent
node if the order is incorrect. The swapping process continues until all the
elements are placed in the correct position. The time complexity is O(logN),
where N is the number of elements in the priority queue.
 Deletion in a Priority Queue: It will remove the element which has
maximum priority first. This removal creates an empty slot, which will be
further filled with new insertion. Then, it compares the newly inserted
element with all the elements inside the queue to maintain the heap
invariant. The time complexity is O(logN), where N is the number of
elements in the priority queue.
 Peek in a Priority Queue: This operation helps to return the maximum
element from Max Heap or the minimum element from Min Heap without
deleting the node from the priority queue. The time complexity is O(1).
Applications of Priority Queue:
 Dijkstra’s Shortest Path Algorithm using priority queue : When the graph is
stored in the form of adjacency list or matrix, priority queue can be used to
extract minimum efficiently when implementing Dijkstra’s algorithm.
 Prim’s algorithm : It is used to implement Prim’s Algorithm to store keys of
nodes and extract minimum key node at every step.
 The priority queue (also known as the fringe) is used to keep track of
unexplored routes, the one for which a lower bound on the total path length
is smallest is given highest priority.
 Heap Sort: Heap sort is typically implemented using Heap which is an
implementation of Priority Queue.
 Operating systems : It is also used in Operating System for load
balancing (load balancing on server ), interrupt handling.
Double Ended Queue:
Deque or Double Ended Queue is a generalized version of Queue data
structure that allows insert and delete at both ends.
Operations on Double Ended Queue:
 Front: Get the front item from the deque. Accessing the front element
has O(1) time complexity.
 Rear: Get the last item from the deque. Accessing the rear element
has O(1) time complexity.
 push_front(x): Inserts the element x at beginning of the deque. Time
Complexity is O(1).
 push_back(x): Inserts the element x at the back of the deque. Time
Complexity is O(1).
 pop_front(): Removes the first element from the deque. Time Complexity
is O(1).
 pop_back(): Removes the last element from the deque. Time Complexity
is O(1).
Applications of Double Ended Queue:
 Used in Job scheduling algorithms.
 In a web browser’s history, recently visited URLs are added to the front of
the deque and the URL at the back of the deque is removed after some
specified number of operations of insertions at the front.
 Storing a software application’s list of undo and redo operations.
 In caching systems to cache frequently accessed data. Deques can be used
to store cached data and efficiently support operations such as adding or
removing data from both ends of the deque.
GATE Archives – Previous Years Questions on
Queue:
Q1. Following is C like pseudo-code of a function that takes a Queue as an
argument, and uses a stack S to do processing.
 C

void fun(Queue *Q)

Stack S; // Say it creates an empty stack S

// Run while Q is not empty

while (!isEmpty(Q))

// deQueue an item from Q and push the dequeued item to S

push(&S, deQueue(Q));

// Run while Stack S is not empty

while (!isEmpty(&S))

// Pop an item from S and enqueue the popped item to Q

enQueue(Q, pop(&S));

What does the above function do in general?

(A) Removes the last from Q
(B) Keeps the Q same as it was before the call
(C) Makes Q empty
(D) Reverses the Q
Answer: (D)
Explanation: The function takes a queue Q as an argument. It dequeues all
items of Q and pushes them to a stack S. Then pops all items of S and
enqueues the items back to Q. Since the stack is LIFO order, all items of the
queue are reversed.
Hence option (D) is the correct answer.
Q2. Which one of the following is an application of Queue Data Structure?
(A) When a resource is shared among multiple consumers.
(B) When data is transferred asynchronously (data not necessarily received at
same rate as sent) between two processes
(C) Load Balancing
(D) All of the above
Answer: (D)
Explanation:
(A) When a resource is shared among multiple consumers: In scenarios
where a resource (such as a printer, CPU time, or database connection) needs
to be shared among multiple consumers or processes, a queue data structure
can be used. Each consumer can enqueue their requests for the resource, and
the resource can be allocated to them in the order of their requests by
dequeuing from the queue. This ensures fair access to the shared resource and
prevents conflicts or resource contention.
(B) When data is transferred asynchronously between two
processes: When data is transferred asynchronously between two processes
or systems, a queue can be used as a buffer or intermediary storage. One
process enqueues the data to be sent, while the other process dequeues and
processes the received data. The queue allows for decoupling the rate of data
production from data consumption, ensuring smooth and efficient
communication between the processes.
(C) Load Balancing: Load balancing is the practice of distributing workloads
across multiple resources to optimize performance and utilization. A queue data
structure can be used in load-balancing algorithms to manage incoming
requests or tasks. The requests are enqueued in the queue, and the load
balancer can dequeue and assign them to available resources based on
various criteria (e.g., round-robin, least connections). This helps distribute the
workload evenly across the resources, preventing overload and maximizing
throughput.
Q3. How many stacks are needed to implement a queue. Consider the situation
where no other data structure like arrays, linked list is available to you.
(A) 1
(B) 2
(C) 3
(D) 4
Answer: (B)
Explanation: A queue can be implemented using two stacks. Refer this for
more reference: https://www.geeksforgeeks.org/queue-using-stacks/
Hence Option(B) is the correct answer.
Q4. How many queues are needed to implement a stack. Consider the situation
where no other data structure like arrays, linked list is available to you.
(A) 1
(B) 2
(C) 3
(D) 4
Answer: (B)
Explanation: A stack can be implemented using two queues. Refer this for
more reference: https://www.geeksforgeeks.org/implement-stack-using-queue/
Hence Option(B) is the correct answer.
Q5. Which of the following is true about linked list implementation of queue?
(A) In push operation, if new nodes are inserted at the beginning of linked list,
then in pop operation, nodes must be removed from end.
(B) In push operation, if new nodes are inserted at the end, then in pop
operation, nodes must be removed from the beginning.
(C) Both of the above
(D) None of the above
Answer: (C)
Explanation: To keep the First In First Out order, a queue can be
implemented using a linked list in any of the given two ways.
Hence option (C) is the correct answer.
Q6. Suppose a circular queue of capacity (n – 1) elements is implemented with
an array of n elements. Assume that the insertion and deletion operation are
carried out using REAR and FRONT as array index variables, respectively.
Initially, REAR = FRONT = 0. The conditions to detect queue full and queue
empty are
(A) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
(B) Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
(C) Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
(D) Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT
Answer: (A)
Explanation: Suppose we start filling the queue.
Let the maxQueueSize ( Capacity of the Queue) is 4.So the size of the array
which is used to implement this circular queue is 5, which is n. In the beginning
when the queue is empty, FRONT and REAR point to 0 index in the array.
REAR represents insertion at the REAR index. FRONT represents deletion
from the FRONT index.
enqueue(“a”); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 1)
enqueue(“b”); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 2)
enqueue(“c”); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 3)
enqueue(“d”); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 4)
Now the queue size is 4 which is equal to the maxQueueSize. Hence overflow
condition is reached.
Now, we can check for the conditions.
When Queue Full :
( REAR+1)%n = (4+1)%5 = 0
FRONT is also 0. Hence ( REAR + 1 ) %n is equal to FRONT.
When Queue Empty :
REAR was equal to FRONT when empty ( because in the starting before filling
the queue FRONT = REAR = 0 )
Hence Option A is correct.

Q7. Consider the following pseudo code. Assume that IntQueue is an integer
queue. What does the function fun do?
 C

void fun(int n)

IntQueue q = new IntQueue();

q.enqueue(0);

q.enqueue(1);

for (int i = 0; i < n; i++) {

int a = q.dequeue();

int b = q.dequeue();

q.enqueue(b);

q.enqueue(a + b);

print(a);

}
}

(A) Prints numbers from 0 to n-1

(B) Prints numbers from n-1 to 0
(C) Prints first n Fibonacci numbers
(D) Prints first n Fibonacci numbers in reverse order.
Answer: (C)
Explanation: The function prints first n Fibonacci Numbers. Note that 0 and 1
are initially there in q. In every iteration of the loop sum of the two queue items
is enqueued and the front item is dequeued.
Hence option (C) is the correct answer.
Q8. Which of the following is NOT a common operation in a queue data
structure?
(A) Enqueue
(B) Dequeue
(C) Peak
(D) Shuffle
Answer: (D)
Explanation: Shuffle is NOT a common operation in a queue data structure.
Hence Option (D) is the correct answer.
Q9. Suppose a stack implementation supports an instruction REVERSE, which
reverses the order of elements on the stack, in addition to the PUSH and POP
instructions. Which one of the following statements is TRUE with respect to this
modified stack?
(A) A queue cannot be implemented using this stack.
(B) A queue can be implemented where ENQUEUE takes a single instruction
and DEQUEUE takes a sequence of two instructions.
(C) A queue can be implemented where ENQUEUE takes a sequence of three
instructions and DEQUEUE takes a single instruction.
(D) A queue can be implemented where both ENQUEUE and DEQUEUE take a
single instruction each.
Answer: (C)
Explanation: To DEQUEUE an item, simply POP. To ENQUEUE an item, we
can do following 3 operations 1) REVERSE 2) PUSH 3) REVERSE
Hence Option (C) is the correct answer.
Q10. A queue is implemented using an array such that ENQUEUE and
DEQUEUE operations are performed efficiently. Which one of the following
statements is CORRECT (n refers to the number of items in the queue)?
(A) Both operations can be performed in O(1) time
(B) At most one operation can be performed in O(1) time but the worst case
time for the other operation will be Ω(n)
(C) The worst case time complexity for both operations will be Ω(n)
(D) Worst case time complexity for both operations will be Ω(log n)
Answer: (A)
Explanation: We can use circular array to implement both in O(1) time. Hence
Option (D) is the correct answer.
Table of Content
 Introduction to Stack:
 LIFO (Last In First Out) in Stack:
 Basic Operations on Stack
 Implementation of Stack using Singly Linked List:
 Applications, Advantages and Disadvantages of Stack:
 Infix to Postfix Operation in Stack:
 Postfix Evaluation using Stack:
 Towers of Hanoi using Stack:
 Fibonaaci Series using Stack:
 Previously Asked GATE Questions on Stack:

Introduction to Stack:
A stack is a linear data structure in which the insertion of a new element and
removal of an existing element takes place at the same end represented as the
top of the stack.
To implement the stack, it is required to maintain the pointer to the top of the
stack, which is the last element to be inserted because we can access the
elements only on the top of the stack.

LIFO (Last In First Out) in Stack :

This strategy states that the element that is inserted last will come out first. You
can take a pile of plates kept on top of each other as a real-life example. The
plate which we put last is on the top and since we remove the plate that is at
the top, we can say that the plate that was put last comes out first.

Basic Operations on Stack

In order to make manipulations in a stack, certain operations are provided to us.
 push() to insert an element into the stack
 pop() to remove an element from the stack
 top() Returns the top element of the stack.
 isEmpty() returns true if the stack is empty else false.
 size() returns the size of the stack.

Stack

Time Complexity of Stack Operations:

Operations Complexity

push() O(1)

pop() O(1)

isEmpty() O(1)
Operations Complexity

size() O(1)

Implementation of Stack using Singly Linked List :

To implement a stack using the singly linked list concept, all the singly linked
list operations should be performed based on Stack operations LIFO(last in first
out) and with the help of that knowledge, we are going to implement a stack
using a singly linked list.
So we need to follow a simple rule in the implementation of a stack which is last
in first out and all the operations can be performed with the help of a top
variable. Let us learn how to perform Pop, Push, Peek, and Display operations
in the following article:
In the stack Implementation, a stack contains a top pointer. which is the “head”
of the stack where pushing and popping items happens at the head of the list.
The first node has a null in the link field and second node-link has the first node
address in the link field and so on and the last node address is in the “top”
pointer.
The main advantage of using a linked list over arrays is that it is possible to
implement a stack that can shrink or grow as much as needed. Using an array
will put a restriction on the maximum capacity of the array which can lead to
stack overflow. Here each new node will be dynamically allocated. so overflow
is not possible.
Push Operation:
 Initialise a node
 Update the value of that node by data i.e. node->data = data
 Now link this node to the top of the linked list
 And update top pointer to the current node

Pop Operation:
 First Check whether there is any node present in the linked list or not, if not
then return
 Otherwise make pointer let say temp to the top node and move forward the
top node by 1 step
 Now free this temp node

Peek Operation:
 Check if there is any node present or not, if not then return.
 Otherwise return the value of top node of the linked list

Display Operation:
 Take a temp node and initialize it with top pointer
 Now start traversing temp till it encounters NULL
 Simultaneously print the value of the temp node

Applications, Advantages and Disadvantages of Stack :

Application of Stack Data Structure:
 Function calls and recursion: When a function is called, the current state
of the program is pushed onto the stack. When the function returns, the state
is popped from the stack to resume the previous function’s execution.
 Undo/Redo operations: The undo-redo feature in various applications uses
stacks to keep track of the previous actions. Each time an action is
performed, it is pushed onto the stack. To undo the action, the top element
of the stack is popped, and the reverse operation is performed.
 Expression evaluation: Stack data structure is used to evaluate
expressions in infix, postfix, and prefix notations. Operators and operands
are pushed onto the stack, and operations are performed based on the
stack’s top elements.
 Browser history: Web browsers use stacks to keep track of the web pages
you visit. Each time you visit a new page, the URL is pushed onto the stack,
and when you hit the back button, the previous URL is popped from the
stack.
 Balanced Parentheses: Stack data structure is used to check if
parentheses are balanced or not. An opening parenthesis is pushed onto the
stack, and a closing parenthesis is popped from the stack. If the stack is
empty at the end of the expression, the parentheses are balanced.
 Backtracking Algorithms: The backtracking algorithm uses stacks to keep
track of the states of the problem-solving process. The current state is
pushed onto the stack, and when the algorithm backtracks, the previous
state is popped from the stack.
Advantages of Stack:
 Easy implementation: Stack data structure is easy to implement using
arrays or linked lists, and its operations are simple to understand and
implement.
 Efficient memory utilization: Stack uses a contiguous block of memory,
making it more efficient in memory utilization as compared to other data
structures.
 Fast access time: Stack data structure provides fast access time for adding
and removing elements as the elements are added and removed from the
top of the stack.
 Helps in function calls: Stack data structure is used to store function calls
and their states, which helps in the efficient implementation of recursive
function calls.
 Supports backtracking: Stack data structure supports backtracking
algorithms, which are used in problem-solving to explore all possible
solutions by storing the previous states.
 Used in Compiler Design: Stack data structure is used in compiler design
for parsing and syntax analysis of programming languages.
 Enables undo/redo operations: Stack data structure is used to enable
undo and redo operations in various applications like text editors, graphic
design tools, and software development environments.
Disadvantages of Stack:
 Limited capacity: Stack data structure has a limited capacity as it can only
hold a fixed number of elements. If the stack becomes full, adding new
elements may result in stack overflow, leading to the loss of data.
 No random access: Stack data structure does not allow for random access
to its elements, and it only allows for adding and removing elements from the
top of the stack. To access an element in the middle of the stack, all the
elements above it must be removed.
 Memory management: Stack data structure uses a contiguous block of
memory, which can result in memory fragmentation if elements are added
and removed frequently.
 Not suitable for certain applications: Stack data structure is not suitable
for applications that require accessing elements in the middle of the stack,
like searching or sorting algorithms.
 Stack overflow and underflow: Stack data structure can result in stack
overflow if too many elements are pushed onto the stack, and it can result in
stack underflow if too many elements are popped from the stack.
 Recursive function calls limitations: While stack data structure supports
recursive function calls, too many recursive function calls can lead to stack
overflow, resulting in the termination of the program.
Infix to Postfix Operation in Stack :
To convert infix expression to postfix expression, use the stack data structure.
Scan the infix expression from left to right. Whenever we get an operand, add it
to the postfix expression and if we get an operator or parenthesis add it to the
stack by maintaining their precedence.
Below are the steps to implement the above idea:
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, put it in the postfix expression.
3. Otherwise, do the following
 If the precedence and associativity of the scanned operator are greater
than the precedence and associativity of the operator in the stack [or the
stack is empty or the stack contains a ‘(‘ ], then push it in the stack. [‘^‘
operator is right associative and other operators like ‘+‘,’–‘,’*‘ and ‘/‘ are
left-associative].
 Check especially for a condition when the operator at the top of
the stack and the scanned operator both are ‘^‘. In this
condition, the precedence of the scanned operator is higher due
to its right associativity. So it will be pushed into the operator
stack.
 In all the other cases when the top of the operator stack is the
same as the scanned operator, then pop the operator from the
stack because of left associativity due to which the scanned
operator has less precedence.
 Else, Pop all the operators from the stack which are greater than or equal
to in precedence than that of the scanned operator.
 After doing that Push the scanned operator to the stack. (If you
encounter parenthesis while popping then stop there and push
the scanned operator in the stack.)
4. If the scanned character is a ‘(‘, push it to the stack.
5. If the scanned character is a ‘)’, pop the stack and output it until a ‘(‘ is
encountered, and discard both the parenthesis.
6. Repeat steps 2-5 until the infix expression is scanned.
7. Once the scanning is over, Pop the stack and add the operators in the
postfix expression until it is not empty.
8. Finally, print the postfix expression.
Postfix Evaluation using Stack:
To evaluate a postfix expression we can use a stack.
Iterate the expression from left to right and keep on storing the operands into a
stack. Once an operator is received, pop the two topmost elements and
evaluate them and push the result in the stack again.

Towers of Hanoi using Stack:

Tower of Hanoi is a mathematical puzzle where we have three rods (A, B,
and C) and N disks. Initially, all the disks are stacked in decreasing value of
diameter i.e., the smallest disk is placed on the top and they are on rod A. The
objective of the puzzle is to move the entire stack to another rod (here
considered C), obeying the following simple rules:
 Only one disk can be moved at a time.
 Each move consists of taking the upper disk from one of the stacks and
placing it on top of another stack i.e. a disk can only be moved if it is the
uppermost disk on a stack.
 No disk may be placed on top of a smaller disk.
Examples:
Input: 3
Output: Disk 1 moved from A to C
Disk 2 moved from A to B
Disk 1 moved from C to B
Disk 3 moved from A to C
Disk 1 moved from B to A
Disk 2 moved from B to C
Disk 1 moved from A to C
Tower of Hanoi using Recursion:
The idea is to use the helper node to reach the destination using recursion.
Below is the pattern for this problem:
 Shift ‘N-1’ disks from ‘A’ to ‘B’, using C.
 Shift last disk from ‘A’ to ‘C’.
 Shift ‘N-1’ disks from ‘B’ to ‘C’, using A.
Tower of Hanoi

Follow the steps below to solve the problem:

 Create a function towerOfHanoi where pass the N (current number of
disk), from_rod, to_rod, aux_rod.
 Make a function call for N – 1 th disk.
 Then print the current the disk along with from_rod and to_rod
 Again make a function call for N – 1 th disk.
Time complexity: O(2N), There are two possibilities for every disk. Therefore, 2
* 2 * 2 * . . . * 2(N times) is 2 N
Auxiliary Space: O(N), Function call stack space
Fibonaaci Series using Stack:
The Fibonacci numbers are the numbers in the following integer sequence: 0,
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..
Fibonacci Series.

Example:
Input : n = 9
Output : 34
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by
the recurrence relation:

Previously Asked GATE Questions on Stack:

Question 1:
The end of a stack, traditionally known as the position where PUSH and POP
operations performed, is known as:
1. FIFO
2. LIFO
3. FRONT
4. TOP
Answer: Option 4 : TOP
Explanation:The top of the stack refers to the end of the stack where
operations are performed. This is where elements are added (pushed) and
removed (popped). When an element is added to an empty stack, it becomes
the top element. When additional elements are pushed onto the stack, they
become the new top elements.
Question 2:
What is the equivalent infix expression of the following postfix expression?
M, N, O, +, *, P, /, Q, R, S, T, /, +, *, –
1. N*(M+Q)/Q-P*(S+R/T)
2. (((M*(N+O))/P)-(Q*(R+(S/T))))
3. O * (M + N)/P – Q * (R + S/T)
4. M * (N + O)/Q – P * (R/S + T)
Answer: Option 2 : (((M * (N + O)) / P) – (Q * (R + (S / T))))
Explanation:
Let’s apply this algorithm to the given postfix expression – M, N, O, +, *, P, /, Q,
R, S, T, /, +, *, –
Step 1 – Push M, N, O onto the stack Stack – O, N, M
Step 2 – Pop O, N, M and concatenate them with + and * Stack – (M*(N+O))
Step 3 – Push P onto the stack Stack – P, (M*(N+O))
Step 4 – Pop P and concatenate it with / Stack – ((M*(N+O))/P)
Step 5 – Push Q, R, S, T onto the stack Stack – T, S, R, Q, ((M*(N+O))/P)
Step 6 – Pop T, S, R, Q and concatenate them with / and + and * Stack –
((Q*(R+(S/T))), ((M*(N+O))/P)
Step 7 – Pop the final expression from the stack after “-” Infix expression –
(((M*(N+O))/P) – ((Q*(R+(S/T))))
Question 3:
What is the postfix representation of the following infix expression?
(A + B) * C – D * E / F
1. A B + C * D E * F – /
2. A B * C + D E * F / –
3. A B + C – D E * F / *
4. A B + C * D E * F / –
Answer: Option 4 : A B + C * D E * F / –
Explanation:
() has highest precedence
* and / has same precedence while + and – has same precedence
(* and /) and higher precedence than (+, -)
Associativity is left to right:
(A + B) * C – D * E / F
AB+ *C–D*E/F
AB+C* –D*E/F
AB+C* – DE* /F
AB+C* – DE*F/
AB+C*DE*F/–
Question 4:
The result evaluating the postfix expression 10 5 + 60 6 / * 8 − is
1. 284
2. 213
3. 142
4. 71
Answer: Option 3 : 142
Question 5:
The five items P,Q,R,S and T are pushed in a stack, one after the other starting
from P. The stack is popped four times and each element is inserted in a
queue. Then two elements are deleted from the queue and pushed back on the
stack. now one item is popped from the stack. The popped item is:
1. P
2. R
3. Q
4. S
Answer: Option 4 : S
Question 6:
Consider the following postfix expression with single digit operands:
623*/42*+68*–
The top two elements of the stack after second * is evaluated, are:
1. 6, 3
2. 8, 1
3. 8, 2
4. 6, 2
Answer: Option 2 : 8, 1
Question 7:
What is the outcome of the prefix expression +, -, *, 3, 2, /, 8, 4, 1?
1. 12
2. 5
3. 11
4. 4
Answer: Option 2 : 5
Question 8:
A stack is implemented with an array of ‘A [0..N – 1]’ and a variable ‘pos’. The
push and pop operations are defined by the following code.
push(x)
A[pos] ← x
pos ← pos – 1
end push
pop( )
pos ← pos + 1
return A[pos]
end pop
Which of the following will initialize an empty stack with capacity N for the above
implementation?
1. pos ← -1
2. pos ← 0
3. pos ← 1
4. pos ← N – 1
Answer: Option 4 : pos ← N – 1
Question 9:
A stack can be implemented using queue, but then we need to use atleast:
1. 3 queues
2. 2 queues
3. only one queue is sufficient
4. none of the options
Answer: Option 2 : 2 queues
Question 10:
Which of the following applications may use a stack?
(a) Parenthesis balancing program
(b) Process scheduling operating system
(c) Conversion of infix arithmetic expression to postfix form
 (a) and (b)
 (b) and (c)
 (a) and (c)
 (a), (b) and (c)
Answer: Option 3 : (a) and (c)

Introduction to Hashing
Hashing refers to the process of generating a fixed-size output from an input of
variable size using the mathematical formulas known as hash functions. This
technique determines an index or location for the storage of an item in a data
structure.

Need for Hash data structure

Every day, the data on the internet is increasing multifold and it is always a
struggle to store this data efficiently. In day-to-day programming, this amount of
data might not be that big, but still, it needs to be stored, accessed, and
processed easily and efficiently. A very common data structure that is used for
such a purpose is the Array data structure.
Now the question arises if Array was already there, what was the need for a
new data structure! The answer to this is in the word “efficiency“. Though
storing in Array takes O(1) time, searching in it takes at least O(log n) time.
This time appears to be small, but for a large data set, it can cause a lot of
problems and this, in turn, makes the Array data structure inefficient.
So now we are looking for a data structure that can store the data and search in
it in constant time, i.e. in O(1) time. This is how Hashing data structure came
into play. With the introduction of the Hash data structure, it is now possible to
easily store data in constant time and retrieve them in constant time as well.
Components of Hashing
There are majorly three components of hashing:
1. Key: A Key can be anything string or integer which is fed as input in the
hash function the technique that determines an index or location for storage
of an item in a data structure.
2. Hash Function: The hash function receives the input key and returns the
index of an element in an array called a hash table. The index is known as
the hash index.
3. Hash Table: Hash table is a data structure that maps keys to values using a
special function called a hash function. Hash stores the data in an
associative manner in an array where each data value has its own unique
index.

How does Hashing work?

Suppose we have a set of strings {“ab”, “cd”, “efg”} and we would like to store it
in a table.
Our main objective here is to search or update the values stored in the table
quickly in O(1) time and we are not concerned about the ordering of strings in
the table. So the given set of strings can act as a key and the string itself will
act as the value of the string but how to store the value corresponding to the
key?
 Step 1: We know that hash functions (which is some mathematical formula)
are used to calculate the hash value which acts as the index of the data
structure where the value will be stored.

 Step 2: So, let’s assign

 “a” = 1,
 “b”=2, .. etc, to all alphabetical characters.
 Step 3: Therefore, the numerical value by summation of all characters of the
string:
 “ab” = 1 + 2 = 3,
 “cd” = 3 + 4 = 7 ,
 “efg” = 5 + 6 + 7 = 18
 Step 4: Now, assume that we have a table of size 7 to store these strings.
The hash function that is used here is the sum of the characters in key mod
Table size. We can compute the location of the string in the array by taking
the sum(string) mod 7.
 Step 5: So we will then store
 “ab” in 3 mod 7 = 3,
 “cd” in 7 mod 7 = 0, and
 “efg” in 18 mod 7 = 4.

The above technique enables us to calculate the location of a given string by

using a simple hash function and rapidly find the value that is stored in that
location. Therefore the idea of hashing seems like a great way to store (key,
value) pairs of the data in a table.
What is a Hash function?
The hash function creates a mapping between key and value, this is done
through the use of mathematical formulas known as hash functions. The result
of the hash function is referred to as a hash value or hash. The hash value is a
representation of the original string of characters but usually smaller than the
original.
For example: Consider an array as a Map where the key is the index and the
value is the value at that index. So for an array A if we have index i which will
be treated as the key then we can find the value by simply looking at the value
at A[i].
simply looking up A[i].
Types of Hash functions:
There are many hash functions that use numeric or alphanumeric keys. This
article focuses on discussing different hash functions :
1. Division Method.
2. Mid Square Method.
3. Folding Method.
4. Multiplication Method
Properties of a Good hash function
A hash function that maps every item into its own unique slot is known as a
perfect hash function. We can construct a perfect hash function if we know the
items and the collection will never change but the problem is that there is no
systematic way to construct a perfect hash function given an arbitrary collection
of items. Fortunately, we will still gain performance efficiency even if the hash
function isn’t perfect. We can achieve a perfect hash function by increasing the
size of the hash table so that every possible value can be accommodated. As a
result, each item will have a unique slot. Although this approach is feasible for a
small number of items, it is not practical when the number of possibilities is
large.
So, We can construct our hash function to do the same but the things that we
must be careful about while constructing our own hash function.
A good hash function should have the following properties:
1. Efficiently computable.
2. Should uniformly distribute the keys (Each table position is equally likely for
each.
3. Should minimize collisions.
4. Should have a low load factor(number of items in the table divided by the
size of the table).
Complexity of calculating hash value using the hash function
 Time complexity: O(n)
 Space complexity: O(1)
Problem with Hashing
If we consider the above example, the hash function we used is the sum of the
letters, but if we examined the hash function closely then the problem can be
easily visualized that for different strings same hash value is begin generated
by the hash function.
For example: {“ab”, “ba”} both have the same hash value, and string {“cd”,”be”}
also generate the same hash value, etc. This is known as collision and it
creates problem in searching, insertion, deletion, and updating of value.
What is collision?
The hashing process generates a small number for a big key, so there is a
possibility that two keys could produce the same value. The situation where the
newly inserted key maps to an already occupied, and it must be handled using
some collision handling technology.
How to handle Collisions?
There are mainly two methods to handle collision:
1. Separate Chaining
2. Open Addressing

Separate Chaining
The idea is to make each cell of the hash table point to a linked list of records
that have the same hash function value. Chaining is simple but requires
additional memory outside the table.
Example: We have given a hash function and we have to insert some elements
in the hash table using a separate chaining method for collision resolution
technique.
Hash function = key % 5,
Elements = 12, 15, 22, 25 and 37.

Let’s see step by step approach to how to solve the above problem:
 Step 1: First draw the empty hash table which will have a possible range of
hash values from 0 to 4 according to the hash function provided.

 Step 2: Now insert all the keys in the hash table one by one. The first key to
be inserted is 12 which is mapped to bucket number 2 which is calculated by
using the hash function 12%5=2.
 Step 3: Now the next key is 22. It will map to bucket number 2 because
22%5=2. But bucket 2 is already occupied by key 12.

 Step 4: The next key is 15. It will map to slot number 0 because 15%5=0.
 Step 5: Now the next key is 25. Its bucket number will be 25%5=0. But
bucket 0 is already occupied by key 25. So separate chaining method will
again handle the collision by creating a linked list to bucket 0.

Hence In this way, the separate chaining method is used as the collision
resolution technique.
Open Addressing
In open addressing, all elements are stored in the hash table itself. Each table
entry contains either a record or NIL. When searching for an element, we
examine the table slots one by one until the desired element is found or it is
clear that the element is not in the table.
Linear Probing:
In linear probing, the hash table is searched sequentially that starts from the
original location of the hash. If in case the location that we get is already
occupied, then we check for the next location.
Algorithm:
1. Calculate the hash key. i.e. key = data % size
2. Check, if hashTable[key] is empty
 store the value directly by hashTable[key] = data
3. If the hash index already has some value then
 check for next index using key = (key+1) % size
4. Check, if the next index is available hashTable[key] then store the value.
Otherwise try for next index.
5. Do the above process till we find the space.
Example: Let us consider a simple hash function as “key mod 5” and a
sequence of keys that are to be inserted are 50, 70, 76, 85, 93.
 Step 1: First draw the empty hash table which will have a possible range of
hash values from 0 to 4 according to the hash function provided.

 Step 2: Now insert all the keys in the hash table one by one. The first key is
50. It will map to slot number 0 because 50%5=0. So insert it into slot
number 0.
 Step 3: The next key is 70. It will map to slot number 0 because 70%5=0 but
50 is already at slot number 0 so, search for the next empty slot and insert it.

 Step 4: The next key is 76. It will map to slot number 1 because 76%5=1 but
70 is already at slot number 1 so, search for the next empty slot and insert it.
 Step 5: The next key is 93 It will map to slot number 3 because 93%5=3, So
insert it into slot number 3.

Quadratic Probing:
Quadratic probing is an open addressing scheme in computer programming for
resolving hash collisions in hash tables. Quadratic probing operates by taking
the original hash index and adding successive values of an arbitrary quadratic
polynomial until an open slot is found.
An example sequence using quadratic probing is:
H + 12, H + 22, H + 32, H + 42…………………. H + k2
This method is also known as the mid-square method because in this method
we look for i2‘th probe (slot) in i’th iteration and the value of i = 0, 1, . . . n – 1.
We always start from the original hash location. If only the location is occupied
then we check the other slots.
Let hash(x) be the slot index computed using the hash function and n be the
size of the hash table.
If the slot hash(x) % n is full, then we try (hash(x) + 1 2) % n.
If (hash(x) + 12) % n is also full, then we try (hash(x) + 2 2) % n.
If (hash(x) + 22) % n is also full, then we try (hash(x) + 3 2) % n.
This process will be repeated for all the values of i until an empty slot is found
Example: Let us consider table Size = 7, hash function as Hash(x) = x % 7 and
collision resolution strategy to be f(i) = i 2 . Insert = 22, 30, and 50
 Step 1: Create a table of size 7.

 Step 2 – Insert 22 and 30

 Hash(22) = 22 % 7 = 1, Since the cell at index 1 is empty, we can
easily insert 22 at slot 1.
 Hash(30) = 30 % 7 = 2, Since the cell at index 2 is empty, we can
easily insert 30 at slot 2.
 Step 3: Inserting 50
 Hash(50) = 50 % 7 = 1
 In our hash table slot 1 is already occupied. So, we will search for
slot 1+12, i.e. 1+1 = 2,
 Again slot 2 is found occupied, so we will search for cell 1+2 2,
i.e.1+4 = 5,
 Now, cell 5 is not occupied so we will place 50 in slot 5.
Double Hashing:
Double hashing is a collision resolving technique in Open Addressed Hash
tables. Double hashing make use of two hash function,
 The first hash function is h1(k) which takes the key and gives out a location
on the hash table. But if the new location is not occupied or empty then we
can easily place our key.
 But in case the location is occupied (collision) we will use secondary hash-
function h2(k) in combination with the first hash-function h1(k) to find the
new location on the hash table.
This combination of hash functions is of the form
h(k, i) = (h1(k) + i * h2(k)) % n

where
 i is a non-negative integer that indicates a collision number,
 k = element/key which is being hashed
 n = hash table size.
Complexity of the Double hashing algorithm:
Time complexity: O(n)

Example: Insert the keys 27, 43, 692, 72 into the Hash Table of size 7. where
first hash-function is h1(k) = k mod 7 and second hash-function is h2(k) = 1 +
(k mod 5)
 Step 1: Insert 27
 27 % 7 = 6, location 6 is empty so insert 27 into 6 slot.
 Step 2: Insert 43
 43 % 7 = 1, location 1 is empty so insert 43 into 1 slot.

 Step 3: Insert 692

 692 % 7 = 6, but location 6 is already being occupied and this is a
collision
 So we need to resolve this collision using double hashing.
hnew = [h1(692) + i * (h2(692)] % 7
= [6 + 1 * (1 + 692 % 5)] % 7
= 9 % 7
= 2

Now, as 2 is an empty slot,

so we can insert 692 into 2nd slot.

 Step 4: Insert 72
 72 % 7 = 2, but location 2 is already being occupied and this is a
collision.
 So we need to resolve this collision using double hashing.
hnew = [h1(72) + i * (h2(72)] % 7
= [2 + 1 * (1 + 72 % 5)] % 7
= 5 % 7
= 5,

Now, as 5 is an empty slot,

so we can insert 72 into 5th slot.
What is meant by Load Factor in Hashing?
The load factor of the hash table can be defined as the number of items the
hash table contains divided by the size of the hash table. Load factor is the
decisive parameter that is used when we want to rehash the previous hash
function or want to add more elements to the existing hash table.
It helps us in determining the efficiency of the hash function i.e. it tells whether
the hash function which we are using is distributing the keys uniformly or not in
the hash table.
Load Factor = Total elements in hash table/ Size of hash table

What is Rehashing?
As the name suggests, rehashing means hashing again. Basically, when the
load factor increases to more than its predefined value (the default value of the
load factor is 0.75), the complexity increases. So to overcome this, the size of
the array is increased (doubled) and all the values are hashed again and stored
in the new double-sized array to maintain a low load factor and low complexity.

Applications of Hash Data structure

 Hash is used in databases for indexing.
 Hash is used in disk-based data structures.
 In some programming languages like Python, JavaScript hash is used to
implement objects.
Real-Time Applications of Hash Data structure
 Hash is used for cache mapping for fast access to the data.
 Hash can be used for password verification.
 Hash is used in cryptography as a message digest.
 Rabin-Karp algorithm for pattern matching in a string.
 Calculating the number of different substrings of a string.
Advantages of Hash Data structure
 Hash provides better synchronization than other data structures.
 Hash tables are more efficient than search trees or other data structures
 Hash provides constant time for searching, insertion, and deletion operations
on average.
Disadvantages of Hash Data structure
 Hash is inefficient when there are many collisions.
 Hash collisions are practically not avoided for a large set of possible keys.
 Hash does not allow null values.
MCQ of Hashing
Question 1: What is the probability of a collision when hashing n keys into a
hash table of size m, assuming that the hash function produces a uniform
random distribution?
(A) O(1/n)
(B) O(n/m)
(C) O(log n)
(D) O(m/n)
Correct Answer: (C)
Explanation: The probability of a collision occurring is dependent on the
number of items hashed (n) and the size of the hash table (m). As the number
of items increases, the probability of a collision also increases. However, as the
size of the hash table increases, the probability decreases. Therefore, the
probability of a collision can be estimated as O(n/m).
Question 2: How many different insertion sequences of the key values using
the hash function h(k) = k mod 10 and linear probing will result in the hash
table shown below?
(A) 10
(B) 20
(C) 30
(D) 40
Correct Answer: (C)
Explanation: In a valid insertion sequence, the elements 42, 23 and 34 must
appear before 52 and 33, and 46 must appear before 33.
Total number of different sequences = 3! x 5 = 30
In the above expression, 3! is for elements 42, 23 and 34 as they can appear in
any order, and 5 is for element 46 as it can appear at 5 different places.
Question 3: Consider a hash table with 100 slots. Collisions are resolved using
chaining. Assuming simple uniform hashing, what is the probability that the first
3 slots are unfilled after the first 3 insertions?
(A) (97 × 97 × 97)/1003
(B) (99 × 98 × 97)/1003
(C) (97 × 96 × 95)/1003
(D) (97 × 96 × 95)/(3! × 100 3)
Correct Answer: (A)
Explanation: Simple Uniform hashing function is a hypothetical hashing
function that evenly distributes items into the slots of a hash table. Moreover,
each item to be hashed has an equal probability of being placed into a slot,
regardless of the other elements already placed.
Probability that the first 3 slots are unfilled after the first
3 insertions =
(probability that first item doesn't go in any
of the first 3 slots)*
(probability that second item doesn't go in any
of the first 3 slots)*
(probability that third item doesn't go in any
of the first 3 slots)

= (97/100) * (97/100) * (97/100)

Question 4: Which one of the following hash functions on integers will

distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging

(A) h(i) = (12 ∗ i) mod 10

from 0 to 2020?

(B) h(i) = (11 ∗ i2) mod 10

(C) h(i) =i3 mod 10
(D) h(i) =i2 mod 10
Correct Answer: (C)
Explanation: Using the concept of power of cycle:

(a) (0,1,4,9,6,5,6,9,4,1,0) repeated

(b) (0,1,8,7,4,5,6,3,2,9) repeated
(c) (0,1,4,9,6,5,6,9,4,1,0) repeated
(d) (0,2,4,6,8) repeated
So, only h(i) =i3 mod 10 covers all the digits from 0 to 9.
Hence Option (C) is correct.
Question 5: Given a hash table T with 25 slots that stores 2000 elements, the
load factor α for T is __________
(A) 80
(B) 0.0125
(C) 8000
(D) 1.25
Correct Answer: (A)
Explanation: load factor = (no. of elements) / (no. of table slots) = 2000/25 =
80.
Question 6: Which of the following statement(s) is TRUE?
1. A hash function takes a message of arbitrary length and generates a fixed
length code.
2. A hash function takes a message of fixed length and generates a code of
variable length.
3. A hash function may give the same hash value for distinct messages.
(A) 1 Only
(B) 2 and 3 Only
(C) 1 and 3 Only
(D) 2 Only
Correct Answer: (C)
Explanation: Hash function is defined as any function that can be used to map
data of arbitrary size of data to a fixed size data.. The values returned by a
hash function are called hash values, hash codes, digests, or simply hashes :
Statement 1 is correct Yes, it is possible that a Hash Function maps a value to
a same location in the memory that’s why collision occurs and we have different
technique to handle this problem : Statement 3 is correct. eg : we have hash
function, h(x) = x mod 3 Acc to Statement 1, no matter what the value of ‘x’ is
h(x) results in a fixed mapping location. Acc. to Statement 3, h(x) can result in
same mapping mapping location for different value of ‘x’ e.g. if x = 4 or x = 7 ,
h(x) = 1 in both the cases, although collision occurs.
Question 7: Consider a hash function that distributes keys uniformly. The hash
table size is 20. After hashing of how many keys will the probability that any
new key hashed collides with an existing one exceed 0.5.
(A) 5
(B) 6
(C) 7
(D) 10
Correct Answer: (D)
Explanation: For each entry probability of collision is 1/20 {as possible total
spaces =20, and an entry will go into only 1 place}
Say after inserting x values probability becomes 1/2
=> (1/20).x = 1/2
=> X=10
Question 8: Suppose we are given n keys, m has table slots, and two simple
uniform hash functions h 1 and h2. Further suppose our hashing scheme uses
h1 for the odd keys and h 2 for the even keys. What is the expected number of
keys in a slot?
(A) m/n
(B) n/m
(C) 2n/m
(D) n/2m
Correct Answer: (B)
Question 9: Consider a hash table with 9 slots. The hash function is h(k) = k
mod 9. The collisions are resolved by chaining. The following 9 keys are
inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum,
and average chain lengths in the hash table, respectively, are
(A) 3, 0 and 1
(B) 3, 3 and 3
(C) 4, 0 and 1
(D) 3, 0 and 2
Correct Answer: (A)
Question 10: Consider a hash table of size 11 that uses open addressing with
linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of
records with keys
43 36 92 87 11 4 71 13 14 is inserted into an initially empty hash table, the bins
of which are indexed from zero to ten. What is the index of the bin into which
the last record is inserted?
(A) 2
(B) 4
(C) 6
(D) 7
Correct Answer: (D)

Introduction to Tree:
Tree Data Structure is a hierarchical data structure in which a collection of
elements known as nodes are connected to each other via edges such that
there exists exactly one path between any two nodes.
Basic Terminologies In Tree Data Structure:
 Parent Node: The node which is a predecessor of a node is called the
parent node of that node. {B} is the parent node of {D, E}.
 Child Node: The node that is the immediate successor of a node is called
the child node of that node. Examples: {D, E} are the child nodes of {B}.
 Root Node: The topmost node of a tree or the node that does not have any
parent node is called the root node. {A} is the root node of the tree. A non-
empty tree must contain exactly one root node and exactly one path from the
root to all other nodes of the tree.
 Leaf Node or External Node: The nodes which do not have any child nodes
are called leaf nodes. {K, L, M, N, O, P, G} are the leaf nodes of the tree.
 Ancestor of a Node: Any predecessor nodes on the path of the root to that
node are called Ancestors of that node. {A,B} are the ancestor nodes of the
node {E}
 Descendant: Any successor node on the path from the leaf node to that
node. {E,I} are the descendants of the node {B}.
 Sibling: Children of the same parent node are called siblings. {D,E} are
called siblings.
 Level of a node: The count of edges on the path from the root node to that
node. The root node has level 0.
 Internal node: A node with at least one child is called Internal Node.
 Neighbour of a Node: Parent or child nodes of that node are called
neighbors of that node.
 Subtree: Any node of the tree along with its descendant.
Tree Traversal Techniques:

1. Inorder Traversal:
Algorithm Inorder(tree)
 Traverse the left subtree, i.e., call Inorder(left->subtree)
 Visit the root.
 Traverse the right subtree, i.e., call Inorder(right->subtree)
In the case of binary search trees (BST), Inorder traversal gives nodes in non-
decreasing order. To get nodes of BST in non-increasing order, a variation of
Inorder traversal where Inorder traversal is reversed can be used.
2. Preorder Traversal:
Algorithm Preorder(tree)
 Visit the root.
 Traverse the left subtree, i.e., call Preorder(left->subtree)
 Traverse the right subtree, i.e., call Preorder(right->subtree)
Preorder traversal is used to create a copy of the tree. Preorder traversal is also
used to get prefix expressions on an expression tree.
3. Postorder Traversal:
Algorithm Postorder(tree)
 Traverse the left subtree, i.e., call Postorder(left->subtree)
 Traverse the right subtree, i.e., call Postorder(right->subtree)
 Visit the root
Postorder traversal is used to delete the tree. Postorder traversal is also useful
to get the postfix expression of an expression tree
Types of Tree data structures :
Below are types of Tree data structure:
1. Binary Tree
2. Ternary Tree
3. N-ary Tree or Generic Tree
4. Binary Search Tree
5. AVL Tree
6. B-Tree
1. Binary Tree:
In a binary tree, each node can have a maximum of two children linked to it.
Some common types of binary trees include full binary trees, complete binary
trees, balanced binary trees, and degenerate binary trees.
Below are list of different Binary trees:
 Full Binary Tree: A Binary Tree is a full binary tree if every node has 0 or 2
children. The following are examples of a full binary tree. We can also say a
full binary tree is a binary tree in which all nodes except leaf nodes have two
children. A full Binary tree is a special type of binary tree in which every
parent node/internal node has either two or no children. It is also known as a
proper binary tree.
 Degenerate (or pathological) tree: A Tree where every internal node has
one child. Such trees are performance-wise same as linked list. A
degenerate or pathological tree is a tree having a single child either left or
right.
 Skewed Binary Tree : A skewed binary tree is a pathological/degenerate
tree in which the tree is either dominated by the left nodes or the right nodes.
Thus, there are two types of skewed binary tree: left-skewed binary tree and
right-skewed binary tree.
 Complete Binary Tree: A Binary Tree is a Complete Binary Tree if all the
levels are completely filled except possibly the last level and the last level
has all keys as left as possible.
 Perfect Binary Tree A Binary tree is a Perfect Binary Tree in which all the
internal nodes have two children and all leaf nodes are at the same level.
Balanced Binary Tree A binary tree is balanced if the height of the tree is
O(Log n) where n is the number of nodes. For Example, the AVL tree
maintains O(Log n) height by making sure that the difference between the
heights of the left and right subtrees is at most 1.
2. Ternary Tree:
A Ternary Tree is a tree data structure in which each node has at most three
child nodes, usually distinguished as “left”, “mid” and “right”.
3. N-ary Tree or Generic Tree :
Generic trees are a collection of nodes where each node is a data structure that
consists of records and a list of references to its children(duplicate references
are not allowed). Unlike the linked list, each node stores the address of multiple
node.
4. Binary Search Tree:
Binary Search Tree is a node-based binary tree data structure which has the
following properties:
 The left subtree of a node contains only nodes with keys lesser 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.
Operations in an BST:
1. Insertion in BST:
2. Searching in BST:
3. Deletion in BST:
4.1 Insertion in BST:
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:
 Check the value to be inserted (say X) with the value of the current node
(say val) we are in:
 If X is less than val move to the left subtree.
 Otherwise, move to the right subtree.
 Once the leaf node is reached, insert X to its right or left based on the
relation between X and the leaf node’s value.
Time Complexity: O(h) where h is the height of the Binary Search Tree. In the
worst case, we may have to travel from the root to the deepest leaf node. The
height of a skewed tree may become n and the time complexity of insertion
operation may become O(n).
Auxiliary Space: O(1), if we use a iterative approach, and (n), as we use
recursive approach.
4.2 Searching in BST:
For searching a value in BST, consider it as a sorted array. Now we can easily
perform search operation in BST using Binary Search Algorithm . Let’s say we
want to search for the number X, We start at the root. Then:
 We compare the value to be searched with the value of the root.
 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.
 Repeat the above step till no more traversal is possible
 If at any iteration, key is found, return True. Else False.
Time Complexity: O(h), where h is the height of the BST.
Auxiliary Space:The auxiliary space complexity of searching in a binary search
tree is O(1) if we use a iterative approach, and (n), as we use recursive
approach.
4.3 Deletion in BST:
The task to delete a node in this BST, can be broken down into 3 scenarios:
Case 1. Delete a Leaf Node in BST
If the node to be deleted is a leaf node, it can simply be removed from the tree.
The parent node of the deleted node must have its corresponding child pointer
set to NULL to reflect the change in the tree.
Case 2. Delete a Node with Single Child in BST
If the node to be deleted has only one child, the child can be promoted to
replace the deleted node. The parent node of the deleted node must have its
corresponding child pointer updated to point to the promoted child.
Case 3. Delete a Node with Both Children in BST
If the node to be deleted has two children, the replacement node can be found
by either selecting the minimum value from the right subtree or the maximum
value from the left subtree of the node to be deleted. After finding the
replacement node, it can be promoted to replace the deleted node. The left
subtree of the replacement node (if it exists) must be attached to the left child of
the promoted node, and the right subtree of the replacement node (if it exists)
must be attached to the right child of the promoted node. The parent node of
the deleted node must have its corresponding child pointer updated to point to
the promoted node.
Time Complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(n).
6. AVL Tree
An AVL tree defined as a self-balancing Binary Search Tree (BST) where the
difference between heights of left and right subtrees for any node cannot be
more than one.
The difference between the heights of the left subtree and the right subtree for
any node is known as the balance factor of the node.
Rotating the subtrees in an AVL Tree:
An AVL tree may rotate in one of the following four ways to keep itself
balanced:
Left Rotation:
When a node is added into the right subtree of the right subtree, if the tree gets
out of balance, we do a single left rotation.

Right Rotation:
If a node is added to the left subtree of the left subtree, the AVL tree may get
out of balance, we do a single right rotation.
Left-Right Rotation:
A left-right rotation is a combination in which first left rotation takes place after
that right rotation executes.

Right-Left Rotation:
A right-left rotation is a combination in which first right rotation takes place after
that left rotation executes.
Operations in an AVL Tree:
 Insertion
 Deletion
 Searching
Previously Asked GATE Questions on Trees:
Question 1: Let LASTPOST, LASTIN and LASTPRE denote the last vertex
visited in a postorder, inorder and preorder traversal. Respectively, of a
complete binary tree. Which of the following is always true? (GATE CS 2000)
(a) LASTIN = LASTPOST
(b) LASTIN = LASTPRE
(c) LASTPRE = LASTPOST
(d) None of the above
Answer: (d)
Explanation: It is given that the given tree is complete binary tree . For a
complete binary tree, the last visited node will always be same for inorder and
preorder traversal. None of the above is true even for a complete binary tree.
The option (a) is incorrect because the last node visited in Inorder traversal is
right child and last node visited in Postorder traversal is root.
The option (c) is incorrect because the last node visited in Preorder traversal is
right child and last node visited in Postorder traversal is root.
For option (b), see the following counter example.
1
/ \
2 3
/ \ /
4 5 6
Inorder traversal is 4 2 5 1 6 3
Preorder traversal is 1 2 4 5 3 6

Question 2: The most appropriate matching for the following pairs is (GATE CS
2000): :
X: depth first search 1: heap
Y: breadth-first search 2: queue
Z: sorting 3: stack
(a) X—1 Y—2 Z-3
(b) X—3 Y—1 Z-2
(c) X—3 Y—2 Z-1
(d) X—2 Y—3 Z-1
Answer: (c)
Explanation: Stack is used for Depth first Search
Queue is used for Breadth First Search
Heap is used for sorting
Question 3: Consider the following nested representation of binary trees: (X Y
Z) indicates Y and Z are the left and right sub stress, respectively, of node X.
Note that Y and Z may be NULL, or further nested. Which of the following
represents a valid binary tree?
(a) (1 2 (4 5 6 7))
(b) (1 (2 3 4) 5 6) 7)
(c) (1 (2 3 4)(5 6 7))
(d) (1 (2 3 NULL) (4 5))
Answer: (c)
Question 4: Consider the label sequences obtained by the following pairs of
traversals on a labeled binary tree. Which of these pairs identify a tree uniquely
(GATE CS 2004)?
i) preorder and postorder
ii) inorder and postorder
iii) preorder and inorder
iv) level order and postorder
a) (i) only
b) (ii), (iii)
c) (iii) only
d) (iv) only
Answer: (b)
Question 5: The following numbers are inserted into an empty binary search
tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary
search tree (the height is the maximum distance of a leaf node from the root)?
(GATE CS 2004)
a) 2
b) 3
c) 4
d) 6
Answer: (b)
Explanation: Constructed binary search tree will be..
10
/\
1 15
\/\
3 12 16
\
5
Question 6: A data structure is required for storing a set of integers such that
each of the following operations can be done in (log n) time, where n is the
number of elements in the set.
o Deletion of the smallest element
o Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?
(a) A heap can be used but not a balanced binary search tree
(b) A balanced binary search tree can be used but not a heap
(c) Both balanced binary search tree and heap can be used
(d) Neither balanced binary search tree nor heap can be used
Answer: (b)
Explanation: A self-balancing balancing binary search tree containing n items
allows the lookup, insertion, and removal of an item in O(log n) worst-case time.
Since it’s a self-balancing BST, we can easily find out minimum element in
O(logn) time which is always the leftmost element (See Find the node with the
minimum value in a Binary Search Tree ).
Since Heap is a balanced binary tree (or almost complete binary tree), insertion
complexity for heap is O(logn). Also, complexity to get minimum in a min heap
is O(logn) because removal of root node causes a call to heapify (after
removing the first element from the array) to maintain the heap tree property.
But a heap cannot be used for the above purpose as the question says – insert
an element if it is not already present. For a heap, we cannot find out in O(logn)
if an element is present or not. Thanks to the game for providing the correct
solution.
Question 7: The height of a binary tree is the maximum number of edges in
any root to leaf path. The maximum number of nodes in a binary tree of height h
is:
(a) 2^h -1
(b) 2^(h-1) – 1
(c) 2^(h+1) -1
(d) 2*(h+1)
Answer: (c)
Explanation: Maximum number of nodes will be there for a complete tree.
Number of nodes in a complete tree of height h = 1 + 2 + 2^2 + 2*3 + …. 2^h =
2^(h+1) – 1
Question 8: The inorder and preorder traversal of a binary tree are d b e a f c g
and a b d e c f g, respectively. The postorder traversal of the binary tree is:
(a) d e b f g c a
(b) e d b g f c a
(c) e d b f g c a
(d) d e f g b c a
Answer: (a)
Below is the given tree.
a
/\
/\
bc
/\/\
/\/\
defg
Question 9: A complete n-ary tree is a tree in which each node has n children
or no children. Let I be the number of internal nodes and L be the number of
leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?
(a) 3
(b) 4
(c) 5
(d) 6
Answer: (c)
For an n-ary tree where each node has n children or no children, following
relation holds
L = (n-1)*I + 1
Where L is the number of leaf nodes and I is the number of internal nodes.
Let us find out the value of n for the given data.
L = 41 , I = 10
41 = 10*(n-1) + 1
(n-1) = 4
n=5
Question 10: What is the number of binary search trees with 20 nodes with
elements 1, 2, 3,…..20 such that the root of tree is 12 and the root of left
subtree is 7?
(a) 2634240
(b) 1243561
(c) 350016
(d) 2642640
Answer: (d)
Explanation:
Number of nodes in left subtree = 11 {1, 2, 3, 4….11}
Number of nodes in the right subtree = 8 {13, 14, ….20}
Since for the left subtree root is 7
Number of elements in the left part of left subtree = 6 {1, 2, 3..6}
Number of elements in the right part of left subtree = 4 {8, 9, 10, 11}
We know number of Binary Search trees with n nodes = (C(2n,n)/n+1)
Number of BST with 6 nodes = (C(12,6)/7) = 132
Number of BST with 4 nodes = (C(8,4)/5) = 14
Number of BST with 8 nodes = (C(16,8)/9) =1430
Total number of BST = 2642640

What is Graph?
A 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 a Graph
 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.
Breadth First Search or BFS in Graph
The Breadth First Search (BFS) algorithm is used to search a graph data
structure for a node that meets a set of criteria. It starts at the root of the graph
and visits all nodes at the current depth level before moving on to the nodes at
the next depth level.
BFS

Time Complexity: O(V+E), where V is the number of nodes and E is the

number of edges.
Auxiliary Space: O(V)
Depth First Search or DFS in Graph
Depth-first search (DFS) is an algorithm for traversing or
searching tree or graph data structures. The algorithm starts at the root
node (selecting some arbitrary node as the root node in the case of a graph)
and explores as far as possible along each branch before backtracking.
DFS

Time complexity: O(V + E), where V is the number of vertices and E is the
number of edges in the graph.
Auxiliary Space: O(V + E), since an extra visited array of size V is required,
And stack size for iterative call to DFS function.
Types of Graphs
1. Null Graph
A graph is known as a null graph if there are no edges in the graph.
2. Trivial Graph
Graph having only a single vertex, it is also the smallest graph possible.
3. Undirected Graph
A graph in which edges do not have any direction. That is the nodes are
unordered pairs in the definition of every edge.
4. Directed Graph
A graph in which edge has direction. That is the nodes are ordered pairs in the
definition of every edge.
5. Connected Graph
The graph in which from one node we can visit any other node in the graph is
known as a connected graph.
6. Disconnected Graph
The graph in which at least one node is not reachable from a node is known as
a disconnected graph.
7. Regular Graph
The graph in which the degree of every vertex is equal to K is called K regular
graph.
8. Complete Graph
The graph in which from each node there is an edge to each other node.
9. Cycle Graph
The graph in which the graph is a cycle in itself, the degree of each vertex is 2.
10. Cyclic Graph
A graph containing at least one cycle is known as a Cyclic graph.
11. Directed Acyclic Graph
A Directed Graph that does not contain any cycle.
12. Bipartite Graph
A graph in which vertex can be divided into two sets such that vertex in each
set does not contain any edge between them.
13. Weighted Graph
 A graph in which the edges are already specified with suitable weight is
known as a weighted graph.
 Weighted graphs can be further classified as directed weighted graphs and
undirected weighted graphs.
Representations of Graph
Here are the two most common ways to represent a graph :
1. Adjacency Matrix
2. Adjacency List
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.
Representation of Directed Graph to Adjacency Matrix:
The below figure shows a directed graph. Initially, the entire Matrix is initialized
to 0. If there is an edge from source to destination, we insert 1 for that
particular adjMat[destination].
Directed Graph to Adjacency Matrix

Adjacency List
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 Directed Graph to 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.
Directed Graph to Adjacency list

Basic Properties of a Graph

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.
The basic properties of a graph include:
1. Vertices (nodes): The points where edges meet in a graph are known as
vertices or nodes. A vertex can represent a physical object, concept, or
abstract entity.
2. Edges: The connections between vertices are known as edges. They can be
undirected (bidirectional) or directed (unidirectional).
3. Weight: A weight can be assigned to an edge, representing the cost or
distance between two vertices. A weighted graph is a graph where the edges
have weights.
4. Degree: The degree of a vertex is the number of edges that connect to it. In
a directed graph, the in-degree of a vertex is the number of edges that point
to it, and the out-degree is the number of edges that start from it.
5. Path: A path is a sequence of vertices that are connected by edges. A
simple path does not contain any repeated vertices or edges.
6. Cycle: A cycle is a path that starts and ends at the same vertex. A simple
cycle does not contain any repeated vertices or edges.
7. Connectedness: A graph is said to be connected if there is a path between
any two vertices. A disconnected graph is a graph that is not connected.
8. Planarity: A graph is said to be planar if it can be drawn on a plane without
any edges crossing each other.
9. Bipartiteness: A graph is said to be bipartite if its vertices can be divided into
two disjoint sets such that no two vertices in the same set are connected by
an edge.
Applications of Graph Data Structure
 In Computer science graphs are used to represent the flow of computation.
 Google maps uses graphs for building transportation systems, where
intersection of two(or more) roads are considered to be a vertex and the
road connecting two vertices is considered to be an edge, thus their
navigation system is based on the algorithm to calculate the shortest path
between two vertices.
 In Facebook, users are considered to be the vertices and if they are friends
then there is an edge running between them. Facebook’s Friend suggestion
algorithm uses graph theory. Facebook is an example of undirected graph.
 In World Wide Web, web pages are considered to be the vertices. There is
an edge from a page u to other page v if there is a link of page v on page u.
This is an example of Directed graph. It was the basic idea behind Google
Page Ranking Algorithm .
 In Operating System, we come across the Resource Allocation Graph
where each process and resources are considered to be vertices. Edges are
drawn from resources to the allocated process, or from requesting process
to the requested resource. If this leads to any formation of a cycle then a
deadlock will occur.
 In mapping system we use graph. It is useful to find out which is an
excellent place from the location as well as your nearby location. In GPS we
also use graphs.
 Facebook uses graphs. Using graphs suggests mutual friends. it shows a
list of the f following pages, friends, and contact list.
 Microsoft Excel uses DAG means Directed Acyclic Graphs.
 In the Dijkstra algorithm, we use a graph. we find the smallest path
between two or many nodes.
Advantages of Graph:
 Representing complex data: Graphs are effective tools for representing
complex data, especially when the relationships between the data points are
not straightforward. They can help to uncover patterns, trends, and insights
that may be difficult to see using other methods.
 Efficient data processing: Graphs can be processed efficiently using graph
algorithms, which are specifically designed to work with graph data
structures. This makes it possible to perform complex operations on large
datasets quickly and effectively.
 Network analysis: Graphs are commonly used in network analysis to study
relationships between individuals or organizations, as well as to identify
important nodes and edges in a network. This is useful in a variety of fields,
including social sciences, business, and marketing.
 Pathfinding: Graphs can be used to find the shortest path between two
points, which is a common problem in computer science, logistics, and
transportation planning.
 Visualization: Graphs are highly visual, making it easy to communicate
complex data and relationships in a clear and concise way. This makes them
useful for presentations, reports, and data analysis.
 Machine learning: Graphs can be used in machine learning to model
complex relationships between variables, such as in recommendation
systems or fraud detection.
Disadvantages of Graph
 Limited representation: Graphs can only represent relationships between
objects, and not their properties or attributes. This means that in order to
fully understand the data, it may be necessary to supplement the graph with
additional information.
 Difficulty in interpretation: Graphs can be difficult to interpret, especially if
they are large or complex. This can make it challenging to extract meaningful
insights from the data, and may require advanced analytical techniques or
domain expertise.
 Scalability issues: As the number of nodes and edges in a graph increases,
the processing time and memory required to analyze it also increases. This
can make it difficult to work with large or complex graphs.
 Data quality issues: Graphs are only as good as the data they are based
on, and if the data is incomplete, inconsistent, or inaccurate, the graph may
not accurately reflect the relationships between objects.
 Lack of standardization: There are many different types of graphs, and
each has its own strengths and weaknesses. This can make it difficult to
compare graphs from different sources, or to choose the best type of graph
for a given analysis.
 Privacy concerns: Graphs can reveal sensitive information about
individuals or organizations, which can raise privacy concerns, especially in
social network analysis or marketing.
Gate Previous Year Problems on Graph Data
Structure
1. Consider the tree arcs of a BFS traversal from a source node W in an
unweighted, connected, undirected graph. The tree T formed by the tree
arcs is a data structure for computing. [GATE CSE 2014 Set 2]
(A) the shortest path between every pair of vertices.
(B) the shortest path from W to every vertex in the graph.
(C) the shortest paths from W to only those nodes that are leaves of T.
(D) the longest path in the graph.
Solution: Correct answer is (B)
2. Traversal of a graph is somewhat different from the tree because [GATE
CSE 2006 Set 1]
(A) There can be a loop in a graph, so we must maintain a visited flag for every
vertex
(B) DFS of a graph uses the stack, but the inorder traversal of a tree is
recursive
(C) BFS of a graph uses a queue, but a time-efficient BFS of a tree is recursive.
(D) All of the above
Solution: Correct answer is (A)
Explanation: There can be a loop in a graph, and due to this, we must
maintain a visited flag for every vertex.
3. What are the suitable Data Structures for the following
algorithms? [GATE CSE 2013 Set 2]
1) Breadth-First Search
2) Depth First Search
3) Prim’s Minimum Spanning Tree
4) Kruskal’s Minimum Spanning Tree

(A)
1) Stack
2) Queue
3) Priority Queue
4) Union Find

(B)
1) Queue
2) Stack
3) Priority Queue
4) Union Find

(C)
1) Stack
2) Queue
3) Union Find
4) Priority Queue
(D)
1) Priority Queue
2) Queue
3) Stack
4) Union Find
Solution: (B)
Explanation: 1) Queue is used in Breadth-First Search
2) Stack is used in depth-first search-dfs
3) Priority Queue is used in Prim’s Minimum Spanning Tree .
4) Union Find is used in Kruskal’s Minimum Spanning Tree .
4. Let G be a weighted graph with edge weights greater than one and G’
be the graph constructed by squaring the weights of edges in G. LetT and
T’ be the minimum spanning trees of G and G’ respectively, with total
weights t and t’. Which of the following statements is TRUE? [GATE CSE
2020 ]
(A) T’ = T with total weight t’ = t^2
(B) T’ = T with total weight t’ < t^2
(C) T’ =t- T but total weight t’ = t^2
(D) None of these
Solution: (D)
5. The Breadth-First Search algorithm has been implemented with the help of a
queue. What is a possible order of visiting the nodes of the following graph is
(A) NQMPOR
(B) QMNPOR
(C) QMNPRO
(D) MNOPQR

Solution: (C)
Explanation: Option (A) is NQMPOR. It cannot be BFS because P is visited
before O here.
Option (D) is MNOPQR. It cannot be a BFS because the traversal begins with
M, but O has been visited before N and Q.
In BFS, every adjacent must be called before adjacent of adjacent.
(B) and (C) correspond to QMNP. Before N and P, M had been added to the
queue (because M comes before NP in QMNP). R is placed in the line before N
and P’s neighbors because it is M’s neighbor (which is O). As a result, R is
visited first, followed by O.
6. Let G be an undirected graph. Consider a depth-first traversal of G,
where T is the depth-first search tree that results. Let u be the first new
(unvisited) vertex visited after u in the traversal, and v be its first new
(unvisited) vertex visited after u. Which of the assertions below is always
true? [GATE CSE 2014 ]
(A) In G, u,v must be an edge, while in T, u is a descendent of v.
(B) In G, u,v must be an edge, while in T, v is a descendent of u.
(C) If u,v in G is not an edge, then u in T is a leaf
(D) If u,v in G is not an edge, then u and v in T must have the same parent.
Solution: (C)
Explanation:
In DFS, if ‘v’ is visited
after ‘u,’ one of the following is true.
1) (u, v) is an edge.
u
/\
vw
//\
xyz
2) A leaf node is ‘u.’
w
/\
xv
//\
uyz
In DFS, after we have visited a node, we first go back to all children who were
not visited. If no children are left unvisited(u is a leaf), then control goes back to
the parent, and the parent then visits the subsequent unvisited children.
7. Which of the two traversals (BFS and DFS) may be used to find if there
is a path from s to t given two vertices in a graph s and t? [GATE CSE
2014 Set 2]
(A) Only BFS
(B) Only DFS
(C) Both BFS and DFS
(D) Neither BFS nor DFS
Solution: (C)
Explanation: Both traversals can be used to see if there is a path from s to t.
8. The statement written below is true or false? [GATE CSE 2021]
If a directed graph’s DFS contains a back edge, any other directed graph’s DFS
will also have at least a single back edge.
(A) True
(B) False
Solution: (A)
Explanation: A cycle in the graph is called its back edge. So if we get a cycle,
all DFS traversals would contain at least one back edge.
9. Which of the condition written below is sufficient to detect a cycle in a
directed graph? [GATE CSE 2008]
(A) There is an edge from a currently visited node to an already seen node.
(B) There is an edge from the currently visited node to an ancestor of the
currently visited node in the forest of DFS.
(C) Every node is seen two times in DFS.
(D) None of the above
Solution: (B)
Explanation: If there is an edge from the currently visited node to an ancestor
of the currently visited node in the forest of DFS, it means a cycle is formed. As
this is an apparent condition about cycle formation, so this condition is
sufficient.
10. If the finishing time f[u] > f[v] of DFS for two vertices u and v in a
graph G which is directed, and u and v are in the DFS tree same as each
other in the DFS forest, then u is an ancestor of v in the depth-first
tree. [GATE CSE 2014 Set 2]
(A) True
(B) False
Solution: (B)
Explanation: In a graph that contains three nodes, r u and v, with edges (r; u)
and (r; v), and r is the starting point for the DFS, u and v are siblings in the DFS
tree; neither as the ancestor of the other.
11. Is the statement written below true or false? [GATE CSE 2015]
A DFS of a directed graph generally produces the exact number of edges of a
tree, i.e., not dependent on the order in which vertices are considered for DFS.
(A) True
(B) False
Solution: (B)
Explanation: Consider the following graph. If we start from ‘a’, then there is
one tree edge. If we start from ‘b,’ there is no tree edge.
a—->b