SYBSC-Computer-Science-SEM-4-Fundamental-of-Algorithms-munotes

Page 1

1 1
INTRODUCTION TO ALGORITHM
Unit Structure:
1.1 Objectives
1.2 Introduction to Algorithm
1.3 Why to analysis algorithm
1.4 Running time analysis
1.5 How to Compare Algorithms
1.6 Rate of Growth
1.7 Commonly Used Rates of Growth
1.8 Types of Analysis
1.9 Asymptotic Notation
1. Big-O Not ation
2. Omega -Ω Notation
3. Theta -Θ Notation
1.10 Properties of Notations
1.11 Summary
1.12 Questions
1.13 Reference for further reading
1.1 OBJECTIVE
After going through this unit, you will be able to:
Understand the fundamental concepts of algorithm design and why
algorithm analysis is necessary. How to Compare Algorithms, Rates of
Growth and Their Varieties, Analysis Types, and Asymptotic Notation
1.2 INTRODUCTION TO ALGORITHM
A well -defined computing technique that accepts a value or set of values
as input and outputs a value or set of values is referred to informally as an
algorithm. As a result, an algorithm is a series of computations that
converts an input into an output. A tool for resolving a well -defined
computational problem is another way to look at an algorithm. The
require d input/output connection is briefly described in the issue munotes.in

Page 2

Fundamental of
Algorit hms
2 statement. In order to achieve that input/output connection, the algorithm
specifies a particular computing method. For instance, it can be necessary
to organise a list of integers in non -decreasi ng order. Numerous common
design strategies and analytical tools may be included into this challenge
because it regularly occurs in real -world settings.
What Makes a Good Algorithm?
 It is important to specify input and output clearly.
 The algorithm's steps should all be distinct and understandable.
 When compared to other possible solutions, algorithms should be the
most efficient.
 There should be no computer code in an algorithm. It is preferable to
write the method in a way that it may be applied to severa l
programming languages.
 Algorithms operate on the basis of input and output. They start with an
input of some value, follow the precise instructions, and end up with
an output.
Characteristics of an algorithm:
1. Input: External input should be given in a mounts of zero or more.
2. Output: Must generate at least one outcome.
3. Clearness: The actions to complete the task should be explicit and clear.
4. Finiteness: Must come to an end after a set number of steps.
5. Effectiveness: Must yield the intended ou tcome.
Example 1
Algorithm for adding two integers the user providedentered by the user.
Step 1: Start
Step 2: Declare three variables n1, n2 and res.
Step 3: Read the value of variables n1 and n2.
Step 4: Add the value of variablesn1 and n2 and assign t he result to res.
res=n1+n2
Step 5: Display res
Step 6: Stop

munotes.in

Page 3

Introduction to
Algorithm
3 Example 2
Algorithm for subtraction two integers the user provided.
Step 1: Start
Step 2: Declare three variables n1, n2 and res.
Step 3: Read the value of variables n1 and n2.
Step 4: Subtra ct the value of variables n1 and n2 and assign the result to
res.
res=n1 -n2
Step 5: Display res
Step 6: Stop
Example 3
Algorithm for calculating factorial of an integer the user provided.
Step 1: Start
Step 2: Declare two variables n andfact.
Step 3: Rea d the value of variable n.
Step 4: Variable fact is set as 1
Step 5: fact <= fact * n
Step 6: Decrease n
Step 7: Verify if n is equal to 0
Step 8: If n is equal to zero, goto step 10 (break out of loop)
Step 9: Else goto step 5
Step 10: Display fact
Examp le 4
Algorithm for calculating square of a number the user provided.
Step 1: Start
Step 2: Declare two variables n and res.
Step 3: Read the value of variable n.
Step 4 : res=n*n
Step 5: Display res
Step 6: Stop munotes.in

Page 4

Fundamental of
Algorit hms
4 1.3 WHY TO ANALYSIS ALGORITHM
An essential component of computational complexity theory is algorithm
analysis, which offers a theoretical estimate of the resources needed by an
algorithm to solve a particular computing issue. Calculating how much
time and space are needed to execute an algorithm i s called algorithm
analysis. As a result, the analysis can only be considered approximate. In
addition, by examining many algorithms, we may contrast them and
choose the most effective one for our needs. The technique of determining
an algorithm's computat ional complexity is known as algorithm analysis.
The time, space, and any other resources required to execute (run) the
algorithm are all referred to as the method's computational complexity.
Comparing several algorithms that are applied to the same issue is the aim
of algorithm analysis. This is performed to measure which approach uses
less memory and resolves a certain problem more rapidly.
Algorithm Analysis Types:
1. Best case
2. Worst case
3. Average case
Best case : Best case: Specify the input for the method that requires the
minimum amount of time. Calculate an algorithm's lower bound in the
best case scenario. The lower bound on the algorithm's running time for
every given input is provided by the best case analysis of algorithms.
Simply stated, it says that every software will require at least (more than
or equal to) that amount of time to do its task.
Example -The perfect scenario occurs in a linear search when the search
data is present at the initial place of large data.
Worst Case : Specify the input for the algorithm to use if you want it to run
quickly. Calculate an algorithm's upper bound as worst case scenario. The
upper bound on the algorithm's running time for any given input is
provided by the worst -case analysis of algorithms. In other words, it sa ys
that any programme will run in a maximum amount of time (less than or
equal to).
Example -The worst case scenario happens in a linear search when there is
no search data at all.
Average case : Consider all random inputs and figure out how long it will
take to process each one on average. The total inputs are then divided by
this number. The average case analysis of algorithms, as the name implies,
adds up the running times on all potential inputs before taking the average.
Therefore, in this instance, the algorithm's execution time serves as both
the lower and upper bounds. In other words, we can determine the
algorithm's typical running time through it. munotes.in

Page 5

Introduction to
Algorithm
5 Example:
Find the ace of spades from a deck of 52 cards.
One card at a time is flipped until an ace of spades is revealed.
Best case scenario : Everything goes as smoothly as it possibly can, we
complete the task speedily, and we call it a day.
You turned over an ace of spades as your opening card.
Worst case scenario : Everything is getting completely out o f control, so
you must put in the most effort to complete your mission.
The final card you flipped was an ace of spades.
Average case scenario : Neither very poorly nor really well, things go.
The ace of spades is not the first or last card that you see.
1.4 RUNNING TIME ANALYSIS
When algorithms are analysed, their computational complexity —the
amount of time, storage, and/or other resources required to run them —is
determined. To put it simply, to gauge how effective a particular algorithm
is.
In order to con duct performance study, we typically applied to calculate
and evaluate the worst -case theoretical running times complexity of
algorithms.
O(1), also known as Constant Running Time, is the quickest possible
running time for any algorithm. In this example, the algorithm runs at the
same speed regardless of the size of the input. An algorithm should have
this runtime, although it's rarely possible.
In fact, the quantity of the input or amount of operations needed for every
entry element, or n, determines an a lgorithm's runtime (performance).
According to running time complexity, the algorithms can be categorised
as follows in order of best to worst performance where c is a positive
constant and n is the size of the input:
Algorithm category Explanation
logari thmic
O(logn) Running time increases in logarithmic proportion
to n.
linear
O(n) Running time increases directly in proportion to n.
superlinear
O(nlogn) Running time increases in proportion to n. munotes.in

Page 6

Fundamental of
Algorit hms
6
Polynomial
O(nc) Running time increases faster than p revious
iterations based on n.
exponential
O(cn) Running time becomes even faster than using the
polynomial approach based on n.
factorial
O(n!) Running time increases the fastest and quickly
becomes unsuitable for even tiny values of n.

1.5 HOW TO COM PARE ALGORITHMS
In order to analyse the algorithm, we need to know two fundamental
parameters:
 Space Complexity: The amount of space needed for an algorithm to
operate completely might be thought of as the space complexity.
An algorithm's space complexity is a measure of how much memory it
uses over its existence.
An algorithm's space requirements are equal to the sum of the two factors
listed below.
1. A fixed component is a place needed to hold constants, simple
variables, programme sizes, and other variable s that are independent of
the size of the problem.
2. A variable component is the area needed by variables, whose size is
completely based on the scope of the issue. Stack space for recursions,
dynamic memory allocation, etc.
Any algorithm's S(p) space comple xity is defined as S(p) = A + Sp (I)
Where S(I), which depends on instance characteristic I, is viewed as the
variable component of the algorithm while A is treated as the fixed part of
the algorithm.
 Time Complexity: Time complexity, which measures how lo ng an
algorithm takes to run completely, is a function of input size n.
The measure of how long an algorithm will take to complete execution is
called the time complexity of the algorithm. Given that each step requires
a fixed amount of time, time requirem ents can be expressed or defined as a
numerical function t(N), where t(N) can be expressed as the number of
steps.
For instance, N steps are required to add two n -bit integers. As a result, the
total calculation time is given by t(N) = c*n, where c is the amount of time
needed to add two bits. Here, we observe that as input size increases, t(N)
climbs linearly..
munotes.in

Page 7

Introduction to
Algorithm
7 1.6 RATE OF GROWTH
An algorithm's growth rate is the rate at which the cost of the algorithm
increases as the size of its input increases. The ter m "Rate of Growth"
describes how quickly running time grows in response to input.
Let's say you visited a store to purchase a car and a bicycle. If a friend sees
you there and inquires about your purchase, we typically reply that you are
purchasing a car. Because the price of a car is excessively high compared
to the price of a bicycle (approximating the cost of cycle to the cost of a
car).
Overall Cost = Car Cost + Bicycle Cost
Overall Cost ≈ Car Cost (approximation)
For the abovementioned example, we can describe the cost of the car and
the cost of the bike in terms of function, ignoring the low order variables
that are generally irrelevant (for large values of input size, n).
As an example in the below case, n3, 2n2 and 10n are the individual costs
of so me function and approximate it to n3. Since, n3 is the highest rate of
growth.
n3 + 2n2 + 10n ≈ n3
Understanding growth rates is the key to algorithm analysis. How much
more resources will my algorithm need as the volume of data increases, in
other words? Usually, we use a function to express the rate of resource
expansion of a piece of code . This section will look at graphs for various
growth rates, ranging from the most efficient to the least efficient, to assist
comprehend the implications.
 Constant Growth Rate
Where the requirement for resources does not increase, it is said to be
constan t. To put it another way, processing 1 piece of data uses the same
resources as processing 1 million pieces of data. A horizontal line appears
on the graph with such a growth rate.
 Logarithmic Growth Rate
When the data is doubled, the resource requirements increase by one unit,
which is known as a logarithmic growth rate. This basically indicates that
the growth rate's curve flattens as big data increases (closer to horizontal
but never reaching it). What a curve of this kind would look like is
depicted in the following graph.
 Linear Growth Rate
A growth rate that is linear is one in which the demand for resources and
the volume of data are precisely proportionate to one another. That is, the
growth rate can be represented by a straight, non -horizontal line. munotes.in

Page 8

Fundamental of
Algorit hms
8  Log Linear
A line with a small curve represents a log linear growth rate. Lower
numbers have a more prominent curve than higher ones.
 Quadratic Growth Rate
One who can describe a parabola as having a quadratic growth rate.
 Cubic Growth Rate
Although this may resemble the quadratic curve very much, it develops
much more quickly.
 Exponential Growth Rate
Each additional unit of data demands a doubling of resources, which is
known as an exponential growth rate. As you can see, the growth rate
initially appears to be flat before rapidly rising to almost vertical (keep in
mind that it cannot actually be vertical).
Following graph showing the rates of growth for six equations with n
input values




munotes.in

Page 9

Introduction to
Algorithm
9

Source: https://opendsa -server.cs.vt.edu/OpenDSA/Books/ CS4104/html/_
images/plot.png
1.7 COMMONLY USED RATES OF GROWTH
Time
Complexity Name Example
1 Constant A linked list's first element being added.
log n Logarithmic In a sorted array, locating a specific
element.
n Linear Locating a specific element in an unsorted
array.
n log n Linear
Logarithmic Separating n things according to "Divide
and Conquer."
n2 Quadratic The graph's shortest route connecting any
two nodes
n3 Cubic Multiplication of a matrix.
2n Exponential The challenge with the Towers of Hanoi.


munotes.in

Page 10

Fundamental of
Algorit hms
10 Examples
Sequential Statements
If our sentences contain fundamental operations like comparisons,
assignments, and variable reads. We can assume they take the same
amount of time O(1).
Example where we can calculate the square sum of two values.
n1 = a * a;
n2 = b * b;
res = n1 + n2;
Constant time is spent on each line O(1).
1.8 TYPES OF ANALYSIS
It is a method for illustrating limiting behaviour. The appro ach is
applicable to all fields of science. It can be used to evaluate how well an
algorithm performs on a significant amount of data.
When analysing algorithms in computer science, it is important to take
into account how well they function when used with very big input
datasets.
The fastest and slowest potential execution times for an algorithm are
expressed using asymptotic notation. These are also known as "best case"
and "worst case," respectively.
We calculate the complexity based on the input size in asymptotic
notations. These notations are essential because they allow us to assess the
complexity of the algorithms without increasing the cost of running them.
(Example in terms of n) " "
The simplest illustration is a function ƒ (n) = n2+3n, where the term 3n
becomes unimportant in comparison to n2 when n is very high. The
function " ƒ (n) is stated to be asymptotically equivalent to n2 as n → ∞ "
is expressed symbolically as " ƒ (n) ~ n2" here.
The significance of asymptotic notation
1. They provide st raightforward indicators of an algorithm's effectiveness.
2. They make it possible to compare the results of different algorithms.
1.9 ASYMPTOTIC NOTATION
1. Omega(Ω) Notation :
The formal notation for expressing the lowest bound of an algorithm's
executio n time is Ω (n). It assesses the worst -case time complexity or the munotes.in

Page 11

Introduction to
Algorithm
11 fastest possible runtime for an algorithm. The best -case situation is
depicted in this asymptotic notation, which is the opposite of large o
notation. The lower bound of an algorithm's exec ution time is presented
formally in this manner. This indicates that this is the shortest amount of
time needed to execute an algorithm. It represents the speed at which an
algorithm can operate.
Assume that the most significant term in the function f(n), g(n), represents
the time complexity of an algorithm.
If f(n) >= C g(n) for all n >= n0, C > 0 and n0 >= 1.
Then we can represent f(n) as Ω(g(n)).
f(n) = Ω(g(n))
Example
The least amount of time needed to sort 1000 numbers is "10 seconds," if
we are sorting 1000 numbers. These 1000 numbers cannot be sorted in
less than 10 seconds using omega notation. Not 9 or 8 seconds, but 11 or
12 seconds is OK.
2. Big -o(O) Notation :
The formal notation for expressing an algorithm's running time upper
bound is the big -o O. The worst -case time complexity or the longest time
an algorithm might possibly take to finish is measure d. By indicating the
function's order of increase, this asymptotic notation measures an
algorithm's efficiency. It gives a function an upper bound, assuring that it
will never grow faster than that of the upper bound.
It measures the algorithm's worst -case complexity. Calculates the
execution time that took the most time. As a result, it provides a formal
means of expressing the maximum allowable execution time for an
algorithm.
Assume that the most significant term in the function f(n), g(n), represents
the time complexity of an algorithm.
If f(n) <= C g(n) for all n >= n 0, C > 0 and n 0>= 1.
Then we can represent f(n) as O(g(n)).
f(n) = O(g(n))
Example:
The maximum amount of time needed to sort 1000 numbers is "50 secs,"
if we are sorting 1000 numbers. The se 1000 numbers can be sorted in less
than 50 seconds using big -o notation. 48 or 46 seconds are acceptable but
51 or 52 seconds are not.
munotes.in

Page 12

Fundamental of
Algorit hms
12 3. Theta(Θ) Notation :
In order to express precise asymptotic behaviour, the theta notation
bounds a functions from a bove and below. The execution time of a given
algorithm will, "on average," be the same for any given input. The typical
case scenario is depicted in this asymptotic notation. When solving a real -
world problem, an algorithm cannot perform worst or best. Th eta notation
(), which denotes the average scenario, shows how the temporal
complexity varies between the best case and worst situation. When the
value of the worst -case and best -case scenarios are equal, theta notation is
commonly utilized. It represents both the top and lower bounds of an
algorithm's running time.
Assume that the most significant term in the function f(n), g(n), represents
the time complexity of an algorithm.
If C1 g(n) <= f(n) <= C2 g(n) for all n >= n0, C1 > 0, C2 > 0 and n0 >= 1.
Then we can represent f(n) as Θ(g(n)).
f(n) = Θ(g(n))
Example:
Let's use the example of sorting 1000 numbers once more. The algorithm
takes 10 seconds the first time, 11 seconds the second time, and 7 seconds
the third time.
1.10 PROPERTIES OF NOTATIONS
Let f(n ) and g(n) be asymptotically positive functions. Properties of
asymptotic notations:
 Transitivity:
f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n)). Valid for O and
Ω as well.

 Reflexivity:
f(n) = Θ(f(n)). Valid for O and Ω.

 Symmetry:
f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)).

 Transpose symmetry:
f(n) = O(g(n)) if and only if g(n) = Ω(f(n)).

 If f(n) is in O(kg(n)) for any constant k > 0,
then f(n) is in O(g(n)).

 If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)),
then (f1 + f2)(n) is in O(max(g 1(n)), (g1(n))).

 If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n))
then f1(n) f2(n) is in O(g1(n) g1(n)). munotes.in

Page 13

Introduction to
Algorithm
13 1.11 SUMMARY
 An algorithm is a set of clear, step -by-step directions for solving a
particular issue.
 We may choose the algorithm that uses the least amount of time and
space by performing an algorithm analysis.
 The objective of an algorithm analysis is to evaluate different
algorithms, mostly in terms of running time but also in terms of other
elements.
 The Best Case, Worst Case, and Average Case ar e used to evaluate an
algorithm's complexity.
 Upper Bounding Function in Big -O Notation.
 Lower Bounding Function in the Omega -Ω Notation.
 Order Function in Theta - Θ Notation.
1.12 QUESTIONS
1. What are the essential properties of an algorithms? Explain.
2. Define algorithm. State its essential characteristics.
3. Write an algorithm for adding two integers the user provided.
4. Write an algorithm for calculating factorial of an integer the user
provided.
5. Explain why analysis of algorithm is important.
6. Explain the runni ng time of an algorithm.
7. Explain how to compare algorithms. Give example.
8. Explain the terms in Rate of growth.
9. Write a note on Upper and Lower bound of an algorithm.
10. Brief describe Big -O and Omega Ω in algorithm analysis.
1.13 REFERENCE FOR FURTHER READING
 https://www.geeksforgeeks.org/method -of-guessing -and-confirming/
 Analysis of algorith ms. (2022, November 15). In Wikipedia.
https://en.wikipedia.org/wiki/Analysis_of_algorithms
 https://bou rnetocode.com/projects/AQA_A_Theory/pages/4 -3-
Algorithms.html
 Data Structure and Algorithmic Thinking with Python, Narasimha
Karumanchi, Career Monk Publications, 2016.
 Data Structures and Algorithms in Python, Michael T. Goodrich,
Roberto Tamassia, Micha el H. Goldwasser, 2016, Wiley.
 Algorithms by Robert Sedgewick & Kevin Wayne. Addison -Wesley
Professional.
 Python Algorithms: Mastering Basic Algorithms in the Python
Language, Magnus Lie Hetland.

munotes.in

Page 14

14 2
MASTER THEOREM
Unit Structure :
2.1 Objectives
2.2 Commonly used Logarithms and Summations
2.2.1 Guidelines for Asymptotic Analysis
2.3 Performance characteristics of algorithms
2.4 Master Theorem for Divide and Conquer
2.5 Divide and Conquer Master Theorem: Problems & S olutions
2.6 Master Theorem for Subtract and Conquer Recurrences
2.7 Method of Guessing and Confirming
2.8 Summary
2.9 Questions
2.10 Reference for further reading
2.1 OBJECTIVE
After going through this unit, you will be able to understand:
Basic algorithm properties , Perf ormance characteristics of algorithms,
Master Theorem for Divide and Conquer Problems & Solutions, Master
Theorem for Subtract andConquer Recurrences, Method of Guessing and
Confirming.
2.2 COMMONLY USED LOGARITHMS AND
SUMMATIONS
Because of a number of adv antageous characteristics that made complex,
time-consuming calculations simpler, logarithms were quickly adopted by
scientists.
There are numerous uses for the common logarithm in science and
engineering, which is a logarithm to base 10 (b = 10).
A base e logarithm is known as a natural logarithm. Its simpler derivative
makes it useful in both mathematics and science.
The base -2 logarithm known as the binary logarithm is frequently
employed in computer science.

munotes.in

Page 15

Master Theorem
15 2.2.1 Guidelines for Asymptotic Analysis
There are some rules to help us determine the running time of an
algorithm. I have described with an example using python code
1. Loops: The running time of a loop is, at most, the running time of the
statements inside the loop (including tests) multiplied by t he number
of iterations.

2. Nested loops: Analyse from the inside out. Total running time is the
product of the sizes of all the loops.

3. Consecutive statements: Add the time complexities of each statement.

4. If-then-else statements: Worst -case running time: t he test, plus either
the then part `the else part (whichever is the larger).

5. Logarithmic complexity: An algorithm is O(logn) if it takes a constant
time to cut the problem size by a fraction (usually by 1/2 ).
For any positive values of m, n, and r as we ll as any positive integers a and
b, logarithms have the following arithmetic properties.

Source:
https://d2vlcm61l7u1fs.cloudfront.ne t/media%2F53d%2F53d266b3 -56c1 -
4cea-99a5 -4eaf6ecae629%2FphpjB5pBJ.png
2.3 PERFORMANCE CHARACTERISTICS OF
ALGORITHMS
There are numerous routes we can take to get from city "A" to city "B."
We have the option of travelling by bicycle, bus, train, and aeropl ane. We
select the one that best suits us based on accessibility and convenience.
Similar to this, there are other algorithms available in computer science to
address an issue. When there are multiple algorithms available to address a
problem, the best sol ution must be chosen. We can choose the best munotes.in

Page 16

Fundamental of
Algorithms
16 algorithm to solve a problem from a variety of algorithms with the use of
performance analysis.
When there are several potential solutions to a problem, we evaluate them
and choose the one that best meets our ne eds. The official explanation is
as follows:
Making an evaluation of an algorithm is the process of measuring its
performance.
The following definitions are also possible:
An algorithm's performance is measured by how well it can predict the
resources need ed to complete its goal.
This indicates that when there are several algorithms available to solve a
problem, we must choose the best algorithm to do so.
To select the best algorithm, we compare algorithms that are solving the
same problem. Algorithms are c ompared using a set of parameters or
elements, such as the amount of memory needed, how quickly the
algorithm runs, how simple it is to understand and apply, etc.
In general, the following factors affect how well an algorithm performs:
1. Does that algorit hm offer a precise solution to the issue?
2. Is it simple to understand?
3. How simple is it to put into practise?
4. How much memory (space) is needed to fix the issue?
5. How long does it take to resolve the issue? Etc.,
When analysing an algorithm, we s olely take into account the time and
space needed for that specific method, ignoring all other factors.
These details can also be used to define performance analysis of an
algorithm, which is calculating the amount of time and space an algorithm
needs to r un is the process of performing performance analysis on the
algorithm.
2.4 MASTER THEOREM FOR DIVIDE AND CONQUER
One of the various algorithm models is the Divide and Conquer strategy.
Essentially, it consists of three steps. −
Divide : In this stage, the problem is divided into a number of smaller,
related problems.
Conquer : Use recursive solutions to solve the sub problems.
Combine : the solutions to the individual problems to arrive at the
solution. munotes.in

Page 17

Master Theorem
17 T(n) = aT(n/b) + f(n)
where n is the size of the problem
a = the number of sub problems in the recursion, where a >= 1
n/b = the size of each sub problem
f(n) = th e price of work performed in addition to recursive calls, such as
splitting a problem into smaller ones and the cost of combining those
smaller issues to obtain the answer.

2.5 MASTER THEOREM: PROBLEMS & SOLUTIONS
Example 1: Use Master's theorem to solve the recurrence relation shown
below -
T(n) = 3T(n/2) + n2
Solution:
T(n) = aT(n/b) + f(n)
Here
a = 3
b = 2
f(n) = n2
log ba = log 23= 1.58
means f(n) ba+ , where, is a constant.
Here, Case 3 suggests -
T(n) = f(n) = Θ(n2)
Example 2: Use Master's theo rem to solve the recurrence relation shown
below -
munotes.in

Page 18

Fundamental of
Algorithms
18 T(n) = 8T(n/4) – n2logn
Solution:
T(n) = aT(n/b) + f(n)
Here
The provided recurrence relation does not match Master's theorem's
general form.
Therefore, the Master's theorem cannot be used to solve it.
Example 3: Use Master's theorem to solve the recurrence relation shown
below -
T(n)=2T(n/2)+n
Solution:
T(n) = aT(n/b) + f(n)
Here
a = 2
b = 2
f(n) = n2
log ba = log 22= 1
means f(n) = nlog
ba+ , where, is a constant.
Here, Case 2 suggests -
T(n) = f(n) = Θ(nlog
ba * log n)= Θ(n log n)
Example 4: Use Master's theorem to solve the recurrence relation shown
below -
T(n) = 3T (n/2)+n3
Solution: T(n) = 3T (n/2) + n3 => T (n) =( n3) (Master Theorem Case 3.a)
Solution:
T(n) = aT(n/b) + f(n)
Here
a = 3
b = 2
f(n) = n2 munotes.in

Page 19

Master Theorem
19 log ba = log 23= 1.58
means f(n) = nlog
ba+ , where, is a constant.
Here, Case 3 suggests -
T(n) = f(n) = Θ(n3)
Example 5: Use Master's theorem to solve the recurrence relation shown
below-
T(n) = 4T (n/2)+n²
Solution: T(n) = 4T (n/2) + n² => T (n) = O(nlogn) (Master Theorem Case
2.a)
Solution:
T(n) = aT(n/b) + f(n)
Here
a = 4
b = 2
f(n) = n2
log ba = log 24= 2
means f(n) = nlog
ba+ , where, is a constant.
Here, Case 2 suggests -
T(n) = f( n) = Θ(nlog
ba * log n)= Θ(n log n)
Example 6 : Use Master's theorem to solve the recurrence relation shown
below -
T(n)=2nT(n/2)+nn
Solution:
T(n) = aT(n/b) + f(n)
Here
The provided recurrence relation does not match Master's theorem's
general form.
Therefo re, the Master's theorem cannot be used to solve it.
munotes.in

Page 20

Fundamental of
Algorithms
20

Source: https://dotnettutorials.net/lesson/master -theorem/

Source: https://dotnettutorials.net/lesson/master -theorem/

munotes.in

Page 21

Master Theorem
21 2.6 MASTER THEOREM FOR SUBTRACT AND
CONQUER RECURRENCES
Master theorem is used to determine the Big – O upper bound on functions
which possess recurrence, i.e which can be broken into sub problems.
Let T (n) be a function defined on positive n as shown below:

for some constants c, a>0, b>0, k>=0 and function f(n). If f(n) is O(nk),
then
1. If a<1 then T(n) = O(nk)
2. If a=1 then T(n) = O(nk+1)
3. if a>1 then T(n) = O(nkan/b)

Example 1: Use Master's t heorem for Subtract and Conquer Recurrences
to solve the below -
T(n) = 3T(n -1) when a>0
=1 otherwise
Solution:

Here
a=3
b=1
d=0
Hence T(n) = O(n03n/1)
Here, Case 2 suggests - (a>1)
Therefore T(n)=O(3n). munotes.in

Page 22

Fundamental of
Algorithms
22 Example 2: Use Mas ter's theorem for Subtract and Conquer Recurrences
to solve the below -
T(n) = 5T(n -3)+O(n2) when n>0
=1 otherwise
Solution:

Here
a=5
b=3
d=2
Hence T(n) = O(n25n/3)
Here, Case 2 suggests - (a>1)
Therefore T(n)= O(n25 n/3)
2.7 METHOD OF GUESSING AND CONFIRMING
This approach's fundamental premise is to make a well -informed
prediction and then use induction to confirm that it is true. Any recurrence
can be resolved using this technique. In general, either the proof will w ork
(in which case we are finished) or the proof will fail if a solution is
guessed and then we attempt to check our guess inductively (in that case
the failure will help us refine our guess).
Consider the recurrence T(N) = N*T(N) + N, for instance. The fo rmat
demanded by the Master Theorems is not met by this. A careful
examination of the recurrence gives us the idea that it is equivalent to the
divide and conquer strategy, which involves breaking the problem into N
subproblems, each of size N. As can be s een, the first level of recursion's
subproblems are N bytes in size. Therefore, let's assume that T(N) =
O(N*log N) and then attempt to support our assumption. Let’s start by
trying to prove an upper bound:
T(N) \le cN*logN:
T(N) = √N*T(√N) + N
T(N) \le √N* c√N*log√N + N
T(N) = N* clog √N + N
T(N) = N*1/2*c*log N + N
T(N) \le cN*log N munotes.in

Page 23

Master Theorem
23 Only that 1 le 1/2*clog N is assumed in the final inequality. If N is large
enough and c is constant, regardless of how little it is, this is true.
We can see from the previous proof that we were right about the upper
bound. Let's now establish the bottom bound for its occurrence:
T(N) = √N*T(√N) + N
T(N) \ge √N* k√N*log√N + N
T(N) = N* klog √N + N
T(N) = N*1/2*k*log N + N
T(N) \ge N*k*log N
The final inequality just makes the assumption that 1 ge 1/2*k*log N. If N
is large enough and for any constant k, this is false.
We can see from the previous proof that our assumption regarding the
lower bound is unreliable.
It is clear from the reasoning above that (N*log N) is an excessiv ely large
number. How about Θ (N) instead? The direct proof of the lower bound is
simple:
T(N) = √N*T(√N) + N \ge N
Now, let us prove the upper bound for this Θ(N):
T(N) = √N*T(√N) + N \\ \le √N*c√N + N \\ = N c+ N \\ = N (c + 1) \\
\nleqcN
It is clear from t he previous induction that Θ(N) is too small and Θ(N*log
N)(N*log N) is too large. So what do we need that is greater than N and
less than N*log N? Consider N* √log N.
Proving upper bound for N* √log N:
T(N) = √N*T(√N) + N
T(N) \le √n*c√N*√(log √N) + N
T(N) = N* 1/ √2 *c*log √N + N
T(N) \le N*c*log √N
Proving lower bound for N* √log N:
T(N) = √N*T(√N) + N
T(N) \ge √N*k√N*√(log√N) + N
T(N) = N*1/ √2*k*log √N + N
T(N) \ngeq N*k*log √N munotes.in

Page 24

Fundamental of
Algorithms
24 The last step doesn’t work. So, Θ(N*√log N) doesn’t work. What else is
between N and N*log N? How about N*log(log N)?
Proving upper bound for N*log(log N):
T(N) = √N*T(√N) + N
T(N) \le √N*c√N*log(log √N) + N
T(N) = N*clog(log N) - cN + N
T(N) \le N*clog(log N), if \ c\ge 1
Proving lower bound for N*log(log N):
T(N) = √N*T(√N) + N
T(N) \ge √N*k√N*log(log √N) + N
T(N) = N*k*log(log N) - kN + N
T(N) \ge N*klog(log N), if \ k \le 1
From the above proofs, it can see that T(N) \le N*clog(log N), if \ c \ge 1
and T(N) \ge N*klog(log N), if \ k \le 1.
2.8 SUMMARY
 There are numerous uses for the common logarithm in science and
engineering

 An algorithm's performance is measured by how well it can predict the
resources needed to complete its goal.

 When analysing an algorithm, we solely take into account the time and
space needed for t hat specific method, ignoring all other factors.

 The master theorem is used in calculating the time complexity of
recurrence relations (divide and conquer algorithms) in a simple and
quick way.

 Master theorem is used to determine the Big – O upper bound on
functions which possess recurrence, i.e which can be broken into sub
problems.

 The basic idea behind this method is to guess the answer, and then
prove it correct by induction. This method can be used to solve any
recurrence.


munotes.in

Page 25

Master Theorem
25 2.9 QUESTIONS
1. Use Maste r's theorem to solve the below:
a. T (n) = 4T(n/2) + n
b. T (n) = 2T(n/2) + log n
c. T (n) = 4T(n/ 2) + n log n (log 24=2)
d. T(n) = 3T(n/3) + n log n
e. T (n) = 4T(n/4) + n
f. T (n) = T(n/2) + 1
g. T (n) = 2T(n/2) + n2
2. What is commonly used Logarithms and Summations.
3. Write a note on Master Theorem. Give an example.
4. Write a note on Master Theorem for Subtract and Conquer
Recurrences
5. Write a note on method of guessing and conforming.
6. Write a note on Master Theorem for Divide and Conquer.
7. Explain Guidelines for Asymptotic Analys is.
8. Which factors affect how well an algorithm performs?
9. Write a note on Performance characteristics of algorithms.
2.10 REFERENCE FOR FURTHER READING
 https://www.geeksforgeek s.org/method -of-guessing -and-confirming/

 Analysis of algorithms. (2022, November 15). In Wikipedia .
https://en.wikipedia.org/wiki/Analysis_of_algorithms

 https://bournetocode.com/projects/AQA_A_Theory/pages/4 -3-
Algorithms.html

 Data Structure and Algorithmic Thinking with Python,
NarasimhaKarumanchi ,CareerMonk Publications, 2016.

 Data Structures and Al gorithms in Python, Michael T. Goodrich,
Roberto Tamassia, Michael H. Goldwasser, 2016, Wiley.

 Algorithms by Robert Sedgewick & Kevin Wayne. Addison -Wesley
Professional.

 Python Algorithms: Mastering Basic Algorithms in the Python
Language, Magnus Lie Het land.

 munotes.in

Page 26

26 3
TREE ALGORITHMS
Unit Structure
3.0 Objectives
3.1 Introduction
3.2 An Overview
3.2.1 What is a tree?
3.2.2 Terminology of TREE?
3.2.3 Characteristics of a Trees?
3.2.4 Advantages o f BST
3.2.5 Types of tree?
3.3 Arithematic Tree
3.3.1 Expression Binary Tree
3.3.2 Arithematic VS Expression Bina ry Tree?
3.3.3 Design of Tree?
3.3.4 Representation of tree
3.3.5 Representation of link list
3.3.6 singly vs doubly link li st
3.4 Balanced Tree
3.4.1 From programmers point of view
3.4.2 From users point of view
3.5 What is Binary Se arch Tree?
3.5.1 What is BST?
3.5.2 What does balanced binary tree ?
3.5.3 what is AVL tree?
3.6 Let us Sum Up
3.7 List of References
3.8 Unit End Exercise
munotes.in

Page 27

Tree Algorithms
27 3.0 OBJECTIVES
What is the objective of algorithm s?
1. Algorithms define how a particular task is to be performed . They
provide computers with instructions. They tell machines on assembly
lines how specific parts should be put together. Or they evaluate
application forms and recommend the best candidates.
2. Provides a hierarchical way of storing data . Reflects structural
relationship in a data set. Allows insertion, deletion and searching
operations that yield results faster t han an array or linked list. Provides
a flexible way to hold and move data.
3. Hierarchi cal Structure: Trees are used to model hierarchical structures,
such as the file system in a computer or the organizational chart in a
company. The tree structure allows f or a natural representation of
parent -child relationships, making it easy to understa nd and
visualize the data .
3.1 INTRODUCTION
A tree is a non -linear abstract data type with a hierarchy -based structure. It
consists of nodes (where th e data is stored) that are connected via links.
The tree data structure stems from a single node called a root node and has
subtrees connected to the root.

Important Terms
Following are the important terms with respect to tree.
 Path − Path refers to the sequence of nodes along the edges of a tree.
 Root − The node at the top of the tree is called root. There is only one
root per tree and one path frocm the root node to any node. munotes.in

Page 28

Fundamental of
Algorithms
28  Parent − Any node except the root node has one edge upwa rd to a
node called parent.
 Child − The node below a given node connected by its edge
downward is called its child node.
 Leaf − The node which does not have any child node is called the leaf
node.
 Subtree − Subtree represents the descendants of a node.
 Visiting − Visiting refers to checking the value of a node when control
is on the node.
 Traversing − Traversing means passing through nodes in a specific
order.
 Levels − Level of a node represents the generation of a node. If the
root node is at level 0, then its next child node is at level 1, its
grandchild is at level 2, and so on.
 Keys − Key represents a value of a node based on which a search
operation is to be carried out for a node.
Types of Trees
There are three types of trees −
 General Trees
 Binary Tre es
 Binary Search Trees
General Trees
General trees are unordered tree data structures where the root node has
minimum 0 or maximum ‘n’ subtrees.
The General trees have no constraint placed on their hierarchy. The root
node thus acts like the superset of al l the other subtrees.
munotes.in

Page 29

Tree Algorithms
29 Binary Trees
Binary Trees are general trees in which the root node can only hold up to
maximum 2 subtrees: left subtree and right subtree. Based on the number
of children, binary trees are divided into three types.
Full Binary Tree
 A full binary tree is a binary tree type where every node has either 0 or
2 child nodes.
Complete Binary Tree
 A complete binary tree is a binary tree type where all the leaf nodes
must be on the same level. However, root and internal nodes in a
complete bi nary tree can either have 0, 1 or 2 child nodes.
Perfect Binary Tree
 A perfect binary tree is a binary tree type where all the leaf nodes are
on the same level and every node except leaf nodes have 2 children.








Binary Search Trees
Binary Search Tre es possess all the properties of Binary Trees including
some extra properties of their own, based on some constraints, making
them more efficient than binary trees.
The data in the Binary Search Trees (BST) is always stored in such a way
that the values in the left subtree are always less than the values in the root
node and the values in the right subtree are always greater than the values
in the root node, i.e. left subtree < root node ≤ right subtree.
munotes.in

Page 30

Fundamental of
Algorithms
30

Advantages of BST
 Binary Search Trees are more efficient than Binary Trees since time
complexity for performing variou s operations reduces.
 Since the order of keys is based on just the parent node, searching
operation becomes simpler.
 The alignment of BST also favors Range Queries, which are executed
to find values existing between two keys. This helps in the Database
Management System.
Disadvantages of BST
The main disadvantage of Binary Search Trees is that if all elements in
nodes are either greater than or lesser than the root node, the tree
becomes skewed . Simply put, the tree becomes slanted to one side
completely.
This skewness will make the tree a linked list rather than a BST, since the
worst case time complexity for searching operation becomes O(n).
To overcome this issue of skewness in the Binary Search Trees, the
concept of Balanced Binary Search Trees was intro duced.
Balanced Binary Search Trees
Consider a Binary Search Tree with ‘m’ as the height of the left subtree
and ‘n’ as the height of the right subtree. If the value of (m -n) is equal to
0,1 or -1, the tree is said to be a Balanced Binary Search Tree .
The trees are designed in a way that they self -balance once the height
difference exceeds 3. Binary Search Trees use rotations as self -balancing
algorithms. There are four different types of rotations: Left Left, Right
Right, Left Right, Right Left.

munotes.in

Page 31

Tree Algorithms
31 There are various types of self -balancing binary search trees −
 AVL Trees
 Red Black Trees
 B Trees
 B+ Trees
 Splay Trees
 Priority Search Trees
WHAT IS TREE?
Trees: Non-Linear data structure
A data structure is said to be linear if its elements form a sequence or a
linear list. Previous
linear data structures that we have studied like an array, stacks, queues and
linked lists organize data in linear order. A data structure is said to be non
linear if its elements form a hierarchical classification where, data items
appear at various levels.
Trees and Graphs are widely used non -linear data structures. Tree and
graph structures represent hierarchical relationship between individual
data elements. Graphs are nothing but trees with certain restrictions
removed.
Trees repre sent a special case of more general structures known as graphs.
In a graph, there is no restrictions on the number of links that can enter or
leave a node, and cycles may be present in the graph. The figure 5.3.1
shows a tree and a non-tree.

Tree is a pop ular data structure used in wide range of applications. A tree
data structure can be defined as follows...
Tree is a non-linear data structure which organizes data in hierarchical
structure and this is a recursive definition.
A tree data structure can also be defined as follows... A tree is a finite set of
one or more nodes such that:There is a specially designated node called
the root. The remaining nodes are partitioned into n>=0 disjoint sets T1, ...,
munotes.in

Page 32

Fundamental of
Algorithms
32 Tn, where each of these sets is a tree. We call T1, . .., Tn are the subtrees of
the root.

A tree is hierarchical collection of nodes. One of the nodes, known as the
root, is at the top of the hierarchy. Each node can have at most one link
coming into it. The node where the link originates is called the par ent
node. The root node has no parent. The links leaving a node (any number
of links are allowed) point to child nodes. Trees are recursive structures.
Each child node is itself the root of a subtree. At the bottom of the tree are
leaf nodes, which have no children.
Advantages of trees
Trees are so useful and frequently used, because they have some very
serious advantages:
 Trees reflect structural relationships in the data
 Trees are used to represent hierarchies
 Trees provide an efficient insertion and sear ching
 Trees are very flexible data, allowing to move sub trees around with
minimum effort
3.2 AN OVERVIEW
In a Tree, Every individual element is called as Node. Node in a tree data
structure, stores the actual data of that particular element and link to next
element in hierarchical structure. Example



munotes.in

Page 33

Tree Algorithms
33

1. Root
In a tree data structure, the first node is called as Root Node. Every tree
must have root node. We can say that root node is the origin of tree data
structure. In any tree, there must be on ly one r oot node. We never have
multiple root nodes in a tree. In above tree, A is a Root node
2. Edge
In a tree data structure, the connecting link between any two nodes is
called as EDGE. In a tree with 'N' number of nodes there will be a
maximum of 'N -1' number of edges.
3. Parent
In a tree data structure, the node which is predecessor of any node is called
as PARENT NODE. In simple words, the node which has branch from it to
any other node is called as parent node. Parent node can also be defined as
"The node which has child / children". e.g., Parent (A,B,C,D).
4. Child
In a tree data structure, the node which is descendant of any node is called
as CHILD Node. In simple words, the node which has a link from its
parent node is called as child node. In a tree, any parent node can have any
number of child nodes. In a tree, all the nodes except root are child nodes.
e.g., Children of D are (H, I,J).
5. Siblings
In a tree data structure, nodes which belong to same Parent are called as
SIBLINGS. In simple words, the nodes with sam e parent are called as
Sibling nodes. Ex: Siblings (B,C, D)
6. Leaf
In a tree data structure, the node which does not have a child (or) node
with degree zero is called as LEAF Node. In simple words, a leaf is a node
with no child.In a tree data struct ure, the leaf nodes are also called as
External Nodes. External node is also a node with no child. In a tree, leaf
node is also called as 'Terminal' node. Ex: (K,L,F,G,M,I,J) munotes.in

Page 34

Fundamental of
Algorithms
34 7. Internal Nodes
In a tree data structure, the node which has atleast one child is called a s
INTERNAL Node. In simple words, an internal node is a node with atleast
one child.
In a tree data structure, nodes other than leaf nodes are called as Internal
Nodes. The root node is also said to be Internal Node if the tree has more
than one no de. Inte rnal nodes are also called as 'Non -Terminal' nodes.
Ex:B,C,D,E,H
8. Degree
In a tree data structure, the total number of children of a node (or)number
of subtrees of a node is called as DEGREE of that Node. In simple words,
the Degree of a node is total numb er of children it has. The highest degree
of a node among all the nodes in a tree is called as 'Degree of Tree'

9. Level
In a tree data structure, the root node is said to be at Level 0 and the
children of root node are at Level 1 and the children of the nod es which
are at Level 1 will be at Level 2 and so on... In simple words, in a tree each
step from top to bottom is called as a Level and the Level count starts with
'0' and incremented by one at each level (Step). Some authors start root
level with 3.
10. Heig ht
In a tree data structure, the total number of edges from leaf node to a
particular node in the longest path is called as HEIGHT of that Node. In a
tree, height of the root node is said to be height of the tree. In a tree, height
of all leaf node s is '0' .
11. Depth
In a tree data structure, the total number of edges from root node to a
particular node is called as DEPTH of that Node. In a tree, the total
number of edges from root node to a leaf node in the
longest path is said to be Depth of the tree. In simp le words, the highest
depth of any leaf node in a tree is said to be depth of that tree. In a tree,
depth of the root node is '0'.


munotes.in

Page 35

Tree Algorithms
35 12. Path
In a tree data structure, the sequence of Nodes and Edges from one node to
another node is called as PATH between that two Nodes. Length of a Path
is total number of nodes in that path. In below example the path A - B - E -
J has length 4.

13. Sub Tree
In a tree data structure, each child from a node forms a subtree recursively.
Every child node will form a subtree on its parent node.

Tree Representations
A tree data structure can be represented in two methods. Those methods
are as follows...
1.List Representation
2. Left Child - Right Sibling Representation Consider the following tree...


1. List Representation
In this representation, we use two types of nodes one for representing the
node with data and another for representing only references. We start with
a node with data from root node in the tree. Then it is linked to an internal
munotes.in

Page 36

Fundamental of
Algorithms
36 node t hrough a reference node and is linked to any other node directly.
This process repeats for all the nodes in the tree.
The above tree example can be represented using List representation as
follows...

Fig: List representation of above Tree

Fig: Possible node structure for a tree of degree k
2. Left Child - Right Sibling Representation
In this representation, we use list with one type of node which consists of
three fields namely Data field, Left child reference field and Right sibling
reference field. Data field stores the actual value of a node, left reference
field stores the address of the left child and right reference field stores the
address of the right sibling node. Graphical representation of that node is
as follows...

In this representation, every node's data field stores the actual value of that
node. If that node has left child, then left reference field stores the address
of that left child node otherwise that field stores NULL. If that node has
right sibling then right reference field stores the addre ss of right sibling
node otherwise that field stores NULL.
The above tree example can be represented using Left Child - Right
Sibling representation as follows...
munotes.in

Page 37

Tree Algorithms
37

Representation as a Degree –Two Tree
To obtain degree -two tree representation of a tree, r otate the right - sibling
pointers in the left child - right sibling tree clockwise by 45 degrees. In a
degree -two representation, the two children of anode are referred as left
and right children.

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

Page 38

Fundamental of
Algorithms
38 There are different types of binary trees and they are...Strictly Binary Tree
In a binary tree, every node can have a maximum of two children. But in
strictly binary tree, every node should have exactly two children or none.
That means every internal node must have exactly two children. A strictly
Binary Tree can be defined as follows...
A binary tree in w hich every node has either two or zero number of
children is called Strictly Binary Tree. Strictly binary tree is also called as
Full Binary Tree or Proper Binary Tree or 2-Tree
1. Complete Binary Tree
In a binary tree, every node can have a maximum o f two ch ildren. But in
strictly binary tree, every node should have exactly two children or none
and in complete binary tree all the nodes must have exactly two children
and at every level of complete binary tree there must be 2 level number of
nodes. For example at level 2 there must be 2^2 = 4 nodes and at level 3
there must be 2^3 = 8 nodes.
A binary tree in which every internal node has exactly two children and all
leaf nodes are at same level is called Complete Binary Tree.
Complete binary tree is also called as Perfect Binary Tree

2. Extended Binary Tree
A binary tree can be converted into Full Binary tree by adding dummy
nodes to existing nodes wherever required.
The full binary tree obtained by adding dummy nodes to a binary tree is
called as Extended Binary Tree.
Abstract Data Type Definition: A binary tree is a finite set of nodes
that is either empty or consists of a root and two disjoint binary trees
called left subtree and right subtree.
ADT contains specification for the binary tree ADT.
Structure Binary_ Tree (abbreviated BinTree) is objects: a finite set of
nodes either empty or consisting of a root node, left Binary_Tree, and
right Binary_Tree. Functions:
munotes.in

Page 39

Tree Algorithms
39 For all bt, bt1, bt2 BinTree, item  element Bintree Create()::= creates
an empty binary tree
Boolean IsEmpty(bt)::= if (bt==empty binary tree) return TRUE else
return FALSE
BinTree MakeBT(bt1, item, bt2)::= return a binary tree whose left subtree
is bt1, whose right subtree is bt2, and whose root no de contains the data
item
Bintree Lchild(bt)::= if (IsEmpty(bt)) return error else return the left
subtree of bt element Data(bt)::= if (IsEmpty(bt)) return error else return
the data in the root node of bt Bintree Rchild(bt)::= if (IsEmpty(bt)) re turn
error else return the right subtree of bt
We use linked list to represent a binary tree. In a linked list, every node
consists of three fields. First field, for storing left child address, second for
storing actual data and third for storing right child address. In this linked
list representation, a node has the following structure...
Type def struct node *tree_pointer; typedef struct node {
int data;
tree_pointer left_child, right_child;};

Binary Tree Traversals
When we wanted to display a binary tree, we need to follow some order in
which all the nodes of that binary tree must be displayed. In any binary tree
displaying order of nodes depends on the traversal method. Displaying
(or) visiting order of nodes in a binary tr ee is called as Binary Tree
Trave rsal.


munotes.in

Page 40

Fundamental of
Algorithms
40 There are three types of binary tree traversals.
1) In - Order Traversal
2) Pre - Order Traversal
3) Post - Order Traversal
Binary Tree Traversals
• 3. In - Order Traversal ( leftChild - root - rightChild )
• I - D - J - B - F - A - G - K - C – H
• 2. Pre - Order Traversal ( root - leftChild - rightChild )
• A - B - D - I - J - F - C - G - K – H
• 3. Post - Order Traversal ( leftChild - rightChild - root )
• I - J - D - F - B - K - G - H - C – A
CHAPTER 5
In - Order Traversal ( left Child - root – right Child )
In In -Order traversal, the root node is visited between left child and right
child. In this traversal, the left child node is visited first, then the root node
is visited and later we go for visiting right child node. This in -order
traversal is applicable for eve ry root node of all subtrees in the tree. This is
performed recursively for all nodes in the tree.
In the above example of binary tree, first we try to visit left child of root
node 'A', but A's left child is a root node fo r left subtree. so we try to visi t
its (B's) left child 'D' and again D is a root for subtree with nodes D, I and
J. So we try to visit its left child 'I' and it is the left most child. So first
wevisit 'I'then go for its root node 'D' and later we visit D 's right child 'J'.
With this we have completed the left part of node B. Then visit 'B' and
next B's right child 'F' is visited. With this we have completed left part of
node A. Then visit root node 'A'. With this we have completed left and
root parts of n ode A. Then we go for right part of the node A. In right of A
again there is a subtree with root C. So go for left child of C and again it is
a subtree with root G. But G does not have left part so we visit 'G' and then
visit G's right child K. With this w e have completed the left part of node
C. Then visit root node'C' and next visit C's right child 'H' which is the
right most child in the tree so we stop the process.
That means here we have visited in the order of I - D - J - B - F - A - G - K
- C - H usi ng In -Order Traversal.
munotes.in

Page 41

Tree Algorithms
41 In-Order Traversal for above example of binary tree is I - D - J - B - F - A -
G - K - C – H
Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree. Step 2 − Visit root node.
Step 3 − Recursively travers e right subtree.
void inorder(tre e_pointer ptr) /* inorder tree traversal */ Recursive
{
if (ptr) {
inorder(ptr ->left_child); printf(“%d”, ptr ->data); indorder(ptr -
>right_child);
}
}
1. Pre - Order Traversal ( root - leftChild - rightChild )
In Pre -Order trav ersal, the root node is visited b efore left child and right
child nodes. In this traversal, the root node is visited first, then its left
child and later its right child. This pre -order traversal is applicable for
every root node of all subtrees in the tree.
In the above example of binary tree, first we visit root node 'A' then visit
its left child 'B' which is a root for D and F. So we visit B's left child 'D'
and again D is a root for I and J. So we visit D's left child'I' which is the
left most child. So next we go for visiting D's righ t child 'J'. With this we
have completed root, left and right parts of node D and root, left parts of
node B. Next visit B's right child'F'. With this we have completed root and
left parts of node A. So we go for A's right child 'C' which is a root
node for G and H. After visiting C, we go for its left child 'G' which is a
root for node K. So next we visit left of G, but it does not have left child
so we go for G's right child 'K'. With this we have completed node C's root
and left parts. Next visit C's rig ht child 'H' which is the right most child
in the tree. So we stop the process. That means here we have visited
in the order of A-B-D-I-J-F-C-G-K-H using Pre-Order Traversal.
Algorithm
Until all nodes are travers ed − Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree. Step 3 − Recursively traverse
right subtree.
void preorder(tree_pointer ptr) /* preorder tree traversal */ Recursive
{ munotes.in

Page 42

Fundamental of
Algorithms
42 if (ptr) {
printf(“%d”, ptr ->data); preorder(ptr ->left_child); preorder(ptr -
>right_child);
}
}
2. Post - Order Traversal ( leftChild - rightChild - root )
In Post-Order traversal, the root node is visited after left child and right
child. In this traversal, left child node is visited first, then its right child and
then its root node. This is recursively performed until the right most node
is visited.
Here we have visited in the order of I - J - D - F - B - K - G - H - C - A
using Post -Order Traversal. Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree. Step 2 − Recursively traverse
right subtree. Step 3 − Visit root node.
void postorder(tree_pointer ptr) /* postorder tree traversal */
Recursive
{
if (ptr) {
postorder(ptr ->left_child); postorder(ptr ->right_chi ld); printf(“%d”, ptr-
>data);
}
}
3.3 ARITHMATIC TREE
Arithmetic Expression Using BT
inorder traversal A / B * C * D + E
infix expression preorder traversal
+ * * / A B C D E prefix expression
postorder traversal A B / C * D * E +
postfix expression level order traversal
+ * E * D / C A B


munotes.in

Page 43

Tree Algorithms
43




15
Trace Operations of Inorder Traversal
Iterative Inorder Traversal (using stack)
void iter_inorder (tree_pointer node)
{
int top= -1; /* initialize stack */ tree_pointer stack[MAX_STACK_SIZE]; for (;;) {
for (; node; node=node ->left_child) add(&top, node); /* add to stack */
node= delete(&top); /* delete from stack */ if (!node) break; /* empty stack */
printf(“%D”, node->data);
node = node->right_child;
}
}
In iterative in order traversal, we must create our own stack to add and remove nodes
as in recursion.
Analysis: Let n be number of nodes in tree, every node of tree is placed on and
removed from the stack exactly once. So time complexity is O(n). The space
requirement is equal to the depth of tree which is O(n).
Level Order Traversal ( Using Queue) -- Traversal without Stack
void level_order(tree_pointer ptr) /* level order tree traversal */
{
int front = rear = 0;
tree_pointer queue[MAX_QUEUE_SIZE]; if (!ptr) return; /* empty queue */
addq(front, &rear, ptr);
for (;;) {
ptr = deleteq(&front, rear); if (ptr) {
printf(“%d”, ptr->data); if (ptr->left_child) + * E* D/ CABmunotes.in

Page 44

Fundamental of
Algorithms
44 addq(front, &rear, ptr->left_child); if (ptr->right_child)
addq(front, &rear, ptr->right_child);
}
else break;
} }
Level order Traversal is implemented with circular queue. In this order, we visit the root
first, then root’s left child followed by root’s right child. We continue in this manner,
visiting the nodes at each new level from left most to right most nodes.
We begin by adding root to the queue. The function operates by deleting the node at the
front of the queue, printing out the node’s data field, and adding the node’s left and
right children to the queue. The level order traversal for above arithmetic expression
is + * E * D / C A B.
Binary Search Trees
Binary Search Tree Representation
Binary Search tree exhibits a special behavior. A node's left child must
have value less than its parent's value and node's right child must have
value greater than it's parent value.

We're going to implement tree using node object and connecting them
through references.
Definition: A binary search tree (BST) is a binary tree. It may be empty. If
it is not empty,then all nodes follows the below mentioned properties −
 Every element has a unique key.
 The keys in a nonempty left subtree (right subtree) are smaller
(larger) than the key in the root of subtree.
 The keys in a nonempty right subtree larger than the key in the root of
subtree.
 The left and right subtrees are also binary search trees. left sub -tree and
right sub-tree and can be defined as −
munotes.in

Page 45

Tree Algorithms
45 left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

Fig: Example Binary Search Trees
ADT for Dictionary:
BST Basic Operations
The basic operations that can be perform ed on binary search tree data
structure, are following −
 Search − search an element in a binary search tree.
 Insert − insert an element into a binary search tree / create a tree.
 Delete − Delete an element from a binary search tree.
 Height -- Height of a binary search tree.
Searching a Binary Search Tree
Let an element k is to search in binary search tree. Start search from root
node of the search tree. If root is NULL, search tree contains no nodes
and search unsuccessful. Otherwise, compare k with the key in the root.
If k equals the root’s key, terminate search, if k is less than key value,
searchelement k in left subtree otherwise search element k in right subtree.
The function search recursively searches the subtrees.
Algorithm:Recursive search of a Binary Search Tree
tree_pointer search(tree_pointer root, int key)
{
/* return a pointer to the node that contains key. If there is no such node,
return NULL */
if (!root) return NULL;
if (key == root->data) return root; if (key < root->data)
return search(ro ot->left_child, key); return search(root ->right_child,key);
}
Algorithm: Iteraive search of a Binary Search Tree
tree_pointer search2(tree_pointer tree, int key)
munotes.in

Page 46

Fundamental of
Algorithms
46 {
while (tree) {
if (key == tree->data) return tree; if (key < tree->data)
tree = tree ->left_c hild; else tree = tree->right_child;
}
return NULL;
}
Analysis of Recursive search and Iterative Search Algorithms:
If h is the height of the binary search tree, both algorithms perform search in O(h) time.
Recursive search requires additional stack space which is O(h).
3.4 BALANCED TREE
Inserting into a Binary Search Tree
The very first insertion creates the tree. Afterwards, whenever an element
is to be inserted. First locate its proper location. Start search from root
node then if data is less than key value, search empty location in left sub
tree and insert the data. Otherwise search empty location in right sub tree
and insert the data.In a binary search tree, the insertion operation is
performed with O(log n) time complexity. In binary search tree, new node
is always ins erted as a leaf node. The insertion operation is performed as
follows...
Step 1: Create a newNode with given value and set its left and right to
NULL. Step 2: Check whether tree is Empty.
Step 3: If the tree is Empty, then set set root to newNode.
Step 4: If the tree is Not Empty, then check whether value of newNode is
smaller or larger than the node (here it is root node).
Step 5: If newNode is smaller than or equal to the node, then move to its
left child. If newNode is larger than the node, then move to its right child.
Step 6: Repeat the above step until we reach a node (e.i., reach to NULL)
where search terminates.
Step 7: After reaching a last node, then insert the newNode as left child if
newNode is smaller or equal to that node e lse insert it as right child.
munotes.in

Page 47

Tree Algorithms
47 void insert (int data ) {
struct node *tempNode = (struct node *)
malloc (sizeof (struct node )); struct node *current ;
struct
node
*parent ;
tempNo
de-
>data =
data ;
tempNo
de-
>leftChi
ld =
NULL ;
tempNo de->rightChild = NULL ;
//if tree is
empty,
create root Algorithm
Create newnode If root is NULL
then create root node return
If root exists then
compare the data with node.data
while until insertion position is located If data is greater than node.data
goto right subtree else
goto left subtree endw hile
insert newnode end If
Implementation
The implementation of insert function should look like this –
munotes.in

Page 48

Fundamental of
Algorithms
48
Deleting a node
Remove operation on binary search tree is more complicated, than insert
and search. Ba sically, in can be divided into two stages:
 search for a node to remove
 if the node is found, run remove algorithm.
Remove algorithm in detail
Now, let's see more detailed description of a remove algorithm. First stage
is identical to algorithm for lookup, except we should track the parent of
the current node. Second part is more tricky. Ther e are three cases, which
are described below .
1. Node to be removed has no children. --This case is quite simple.
Algorithm sets corresponding link of the parent to NULL and disposes
the node.
Example. Remove -4 from a BST.




retur}}//go to right of
the tree else {
current = current -
>rightChild ;
//insert to the
right if(current == NULL) { }}munotes.in

Page 49

Tree Algorithms
49 2. Node to be removed has one child. In this case , node is cut from the
tree and algorithm links single child (with it's subtree) directly to the
parent of the removed node.

3. Node to be removed has two children. --This is the most complex case.
The deleted node can be replaced by eit her largest key in its left
subtree or the smallest in its right subtree. Preferably which node
has one child.

Deletion Operation in BST
In a binary search tree, the deletion operation is performed with O(log n)
time complexity. Deleting a node from Binar y search tree has f ollowing
three cases...
Case 1: Deleting a Leaf node (A node with no children) Case 2: Deleting a
node with one child
Case 3: Deleting a node with two children Case 1: Deleting a leaf node
We use the following steps to delete a leaf node from BST... Step 1: Find
the node to be deleted using search operation
Step 2: Delete the node using free function (If it is a leaf) and terminate
the function. Case 2: Deleting a node with one child
We use the following steps to delete a node with one child from BST...
Step 1: Find the node to be deleted using search operation
Step 2: If it has only one child, then create a link between its parent and
child nodes. Step 3: Delete the node using free function and terminate the
function.
Case 3: Deleting a node with two childr en
We use the following steps to delete a node with two children from BST...
Step 1: Find the node to be deleted using search operation
Step 2: If it has two children, then find the largest node in its left subtree
munotes.in

Page 50

Fundamental of
Algorithms
50 (OR) the smallest node in its right subtr ee.
Step 3: Swap both deleting node and node which found in above step.
Step 4: Then, check whether deleting node came to case 1 or case 2 else
goto steps 2 Step 5: If it comes to case 1, then delete using case 1 logic.
Step 6: If it com es to case 2, then delete using case 2 logic.
Step 7: Repeat the same process until node is deleted from the tree.
/* deletion in binary search tree */
void deletion(struct treeNode **node, struct treeNode **parent, int data) {
struct treeNode *tmpNode, *t mpParent;
if (*node == NULL) return;
if ((*node) ->data == data) {
/* deleting the leaf node */
if (!(*node) ->left && !(*node) ->right) { if (parent) {
/* delete leaf node */
if ((*parent) ->left == *node) (*parent) ->left = NULL;
else
(*parent) ->right = NULL;
free(*node);
} else {
/* delete root node with no children */ free(*node);
}
/* deleting node with one child */
} else if (!(*node) ->right && (*node) ->left) {
/* deleting node with left child alone */ tmpNode = *node;
(*parent) ->right = (*node) ->left; free(tmpNode);
*node = (*parent) ->right;
} else if ((*node) ->right && !(*node) ->left) {
/* deleting node with right child alone */ tmpNode = *node;
(*parent) ->left = (*node) ->right; free(tmpNode);
(*node) = (*parent) ->left; munotes.in

Page 51

Tree Algorithms
51 } else if (!(*node) ->right ->left) {
/*
* deleting a node whose right child
* is the smallest node in the right
* subtree for the node to be deleted.
*/
tmpNode = *node;
(*node) ->right ->left = (*node) ->left;
(*parent) ->left = (*node) ->right; free(tmpNode);
*node = (*parent) ->left;
} else {
/*
* Dele ting a node with tw o children.
* First, find the smallest node in
* the right subtree. Replace the
* smallest node with the node to be
* deleted. Then, do proper connections
* for the children of replaced node.
*/
tmpNode = (*node) ->right; while (tmpNode ->left) {tmp Parent = tmpNode;
tmpNode = tmpNode ->left;
}
tmpParent ->left = tmpNode ->right; tmpNode ->left = (*node) ->left;
tmpNode ->right =(*node) ->right; free(*node);
*node = tmpNode;
}
} else if (data < (*node) ->data) {
/* traverse towards left subtree */ deletion(&( *node) ->left, node, data);
} else if (data > (*node) ->data) {
/* traversing towards right subtree */ deletion(&(*node) ->right, node, munotes.in

Page 52

Fundamental of
Algorithms
52 data);
}
}
Height of a Binary Search Tree:
Height of a Binary Tree For a tree with just one node, the root node, the
height is defined to be 0 , if there are 2 levels of nodes the height is 1 and
so on. A null tree (no nodes except the null node) is defined to have a
height of –3.
The following height function in pseudocode is defined recursively



Example
Construct a Binar y Search Tree by in serting the following sequence of
numbers... 10,12,5,4,20,8,7,15 and 13
Above elements are inserted into a Binary Search Tree as follows...
munotes.in

Page 53

Tree Algorithms
53

Generic Trees (N-ary Trees)
Generic trees are a collection of nodes where each node is a data
structure that consi sts 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 nodes. Every node stores
address of its children and the very first node’s ad dress will be store d in
a separate pointer called root.
The Generic trees are the N -ary trees which have the following
properties:
1. Many children at every node.
2. The number of nodes for each node is not known in advance.

munotes.in

Page 54

Fundamental of
Algorithms
54 Example:


Generic Tree
To represent the abo ve tree, we have to consider the worst case, that is
the node with maximum children (in above example, 6 children) and
allocate that many pointers for each node.
The node representation based on this method can be written as:
struct Node{
int data;
Node *firstchild;
Node *secondchild;
Node *thirdchild;
Node *fourthchild;
Node *fifthchild;
Node *sixthchild;
};
Disadvantages of the above representation are:
1. Memory Wastage – All the pointers are not required in all th e cases.
Hence, the re is lot of memory wastage.
2. Unknown number of children – The number of children for each
node is not known in advance.
Simple Approach:
For storing the address of children in a node we can use an array or linked
list. But we will face some issues with bo th of them. munotes.in

Page 55

Tree Algorithms
55 1. In Linked list, we can not randomly access any child’s address. So it
will be expensive.
2. In array , we can randomly access the address of any child, but we can
store only fixed number of children’s addresses in it.
Better Appr oach:
We can use Dynamic Arrays for storing the address of children’s address.
We can randomly access any child’s address and the size of the vector is
also not fixed.
Inorder traversal of a Binary tree can either be done using recursion
or with the use of a auxiliary stack . The idea of threaded binar y trees is
to make inorder traversal faster and do it without stack and without
recursion. A binary tree is made threaded by making all right child
pointers that would normally be NULL point to the inorder successor of
the node (if it exists).
A threaded b inary tree is a typ e of binary tree data structure where the
empty left and right child pointers in a binary tree are replaced with
threads that link nodes directly to their in -order predecessor or successor,
thereby providing a way to traverse the tree wi thout using recursi on or a
stack.
Threaded binary trees can be useful when space is a concern, as they can
eliminate the need for a stack during traversal. However, they can be
more complex to implement than standard binary trees.
There are two types of th readed binary trees .
Single Threaded: Where a NULL right pointers is made to point to the
inorder successor (if successor exists)
Double Threaded: Where both left and right NULL pointers are made
to point to inorder predecessor and inorder successor respec tively. The
predece ssor threads are useful for reverse inorder traversal and postorder
traversal.
The threads are also useful for fast accessing ancestors of a node.
Following diagram shows an example Single Threaded Binary Tree. The
dotted lines represent threads. munotes.in

Page 56

Fundamental of
Algorithms
56

C and C++ representation of a Threaded Node
Following is C and C++representation of a single -threaded node. struct Node
{
int data;
struct Node *left, *right;
bool rightThread;
}
Java representation of a Threaded Node
Following is Java representat ion of a single -threaded node.
Since right pointer is used for two purposes, the boolean variable
rightThread is used to indicate whether right pointer points to right child
or inorder successor. Similarly, we can add leftThread for a do uble
threaded binar y tree.
Inorder Traversal using Threads Following is code for inorder
traversal in a threaded binary tree.
Following diagram demonstrates inorder order traversal using threads.
munotes.in

Page 57

Tree Algorithms
57

Advantages of Threaded Binary Tree
 In this Tree it enabl es linear traversal of elements.
 It eliminates the use of stack as it perform linear traversal, so save
memory. munotes.in

Page 58

Fundamental of
Algorithms
58  Enables to find parent node without explicit use of parent pointer
 Threaded tree give forward and backward traversal of nodes by in -
order fashio n
 Nodes contain poi nters to in -order predecessor and successor
 For a given node, we can easily find inorder predecessor and
successor. So, searching is much more easier.
 In threaded binary tree there is no NULL pointer present. Hence
memory wastage in occ upying NULL links i s avoided.
 The threads are pointing to successor and predecessor nodes. This
makes us to obtain predecessor and successor node of any node
quickly.
 There is no need of stack while traversing the tree, because using
thread links we can r each to previously visited nodes.
Disadvantages of Threaded Binary Tree
 Every node in threaded binary tree need extra information(extra
memory) to indicate whether its left or right node indicated its child
nodes or its inorder predecessor or successor. So , the node consumes
extra memory to implement.
 Insertion and deletion are way more complex and time consuming
than the normal one since both threads and ordinary links need to be
maintained.
 Implementing threads for every possible node is complicated.
 Increased complexity: I mplementing a threaded binary tree requires
more complex algorithms and data structures than a regular binary
tree. This can make the code harder to read and debug.
 Extra memory usage: In some cases, the additional pointers used to
threa d the tree can use up more memory than a regular binary tree.
This is especially true if the tree is not fully balanced, as threading a
skewed tree can result in a large number of additional pointers.
 Limited flexibility: Threaded binary trees are speciali zed data
structures that are optimized for specific types of traversal. While
they can be more efficient than regular binary trees for these types of
operations, they may not be as useful in other scenarios. For
example, they cannot be easily modified (e.g . inserting or dele ting
nodes) without breaking the threading.
 Difficulty in parallelizing: It can be challenging to parallelize
operations on a threaded binary tree, as the threading can introduce
data dependencies that make it difficult to process nodes
independently. This can limit the performance gains that can be
achieved through parallelism. munotes.in

Page 59

Tree Algorithms
59 Applications of threaded binary tree –
 Expression evaluation: Threaded binary trees can be used to evaluate
arithmetic expressions in a way that avoids recursion or a stack. The
tree can be constructed from the input expression, and then traversed
in-order or pre -order to perform the evaluation.
 Database indexing: In a database, threaded binary trees can be used
to index data based on a specific field (e.g. last na me). The tree can
be constructed with the indexed values as keys, and then traversed in -
order to retrieve the data in sorted order.
 Symbol table management: In a compiler or interpreter, threaded
binary trees can be used to store and manage symbol tables f or
variables and fu nctions. The tree can be constructed with the symbols
as keys, and then traversed in -order or pre -order to perform various
operations on the symbol table.
 Disk -based data structures: Threaded binary trees can be used in
disk-based data s tructures (e.g. B -trees) to improve performance. By
threading the tree, it can be traversed in a way that minimizes disk
seeks and improves locality of reference.
 Navigation of hierarchical data: In certain applications, threaded
binary trees can be used t o navigate hierarch ical data structures, such
as file systems or web site directories. The tree can be constructed
from the hierarchical data, and then traversed in -order or pre -order to
efficiently access the data in a specific order.
Expression Tree
The expression tree is a binary tree in which each internal node
corresponds to the operator and each leaf node corresponds to the
operand so for example expression tree for 3 + ((5+9)*2) would be:
munotes.in

Page 60

Fundamental of
Algorithms
60 Inorder traversal of expression tree produces infix version of given
postfix ex pression (same with postorder traversal it gives postfix
expression)
Evaluating the expression represented by an expression tree:
Let t be the expression tree
If t is not null then
If t.value is operand then
Return t.value
A = solve(t.left)
B = solve(t.right)
// calculate applies operator 't.value'
// on A and B, and returns value
Return calculate(A, B, t.value)
Construction of Expression Tree:
Now For constructing an expression tree we use a stack . We loop
through input expression and do the following for every character.
1. If a character is an operand push that into the stack
2. If a character is an operator pop two values from the stack make them
its child and push the current node again.
In the end, the only element of the stack will be the root of an expression
tree.
Examples:
Input: A B C*+ D/
Output: A + B * C / D
The first three symbols are operands, so create tree nodes and push
pointers to them onto a stack as shown below.
munotes.in

Page 61

Tree Algorithms
61 In the Next step , an operator ‘*’ will going read, so two pointers to trees
are popped, a new tree is formed and a pointer to it is pushed onto the
stack

In the Next step, an operator ‘+’ will read, so two pointers to trees are
popped, a new tree is formed and a pointe r to it is pushed onto the stack.
Below is the implementation of the above approach: import java.util.Stack;

class Node{
char data;
Node left,right;
public Node( char data){
this.data = data;
left = right = null;
}
}

public class Main {
public static boolean isOperator( char ch){
if(ch=='+' || ch==' -'|| ch=='*' || ch=='/' || ch=='^'){
return true;
}
return false ;
} munotes.in

Page 62

Fundamental of
Algorithms
62 public static Node expressionTree(String postfix){
Stack st = new Stack();
Node t1,t2,temp;

for(int i=0;i if(!isOperator(postfix.charAt(i))){
temp = new Node(postfix.charAt(i));
st.push(temp);
}
else{
temp = new Node(postfix.charAt(i));
t1 = st.pop();
t2 = st.pop();
temp.left = t2;
temp.right = t1;
st.push(temp);
}

}
temp = st.pop();
return temp;
}
public static void inorder(Node root){
if(root== null) return ;

inorder(root.left);
System.out.print(root.data);
inorder(root.right); munotes.in

Page 63

Tree Algorithms
63 }
public static void main(Str ing[] args) {
String postfix = "ABC*+D/";

Node r = expressionTree(postfix);
inorder(r);
}
}
Output
The Inorder Traversal of Expression Tree: A + B * C / D
Time complexity: O(n)
Auxiliary space: O(n)
3.5 WHAT IS BINA RY 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 grea ter than
the node’s key.
 The left and right subtree each must also be a binary search tree.

Binary Search Tree munotes.in

Page 64

Fundamental of
Algorithms
64 Balanced Binary Search Tree
A balanced binary tree is also known as height balanced tree. It is defined
as binary tree in when the difference b etween the height of the left subtree
and right subtree is not more than m, where m is usually equal to 3. The
height of a tree is the number of edges on the longest path between the
root node and the leaf node.

The above tree is a binary search tree . A binary search tree is a tree in
which each node on the left side has a lower value than its parent node,
and the node on the right side has a higher value than its parent node. In
the above tree, n1 is a root node, and n4, n6, n7 are the leaf nodes. The n7
node is the farthest node from the root node. The n4 and n6 contain 2
edges and there exist three edges between the root node and n7 node.
Since n7 is the farthest from the root node; therefore, the height of the
above tree is 3.
Now we will see whether the above tree is balanced or not. The left
subtree contains the nodes n2, n4, n5, and n7, while the right subtree
contains the nodes n3 and n6. The left subtree has two l eaf nodes, i.e., n4
and n 7. There is only one edge between the node n2 and n4 and two edges
between the nodes n7 and n2; therefore, node n7 is the farthest from the
root node. The height of the left subtree is 2. The right subtree contains
only one leaf no de, i.e., n6, and has onl y one edge; therefore, the height of
the right subtree is 3. The difference between the heights of the left subtree
and right subtree is 3. Since we got the value 1 so we can say that the
above tree is a height -balanced tree. This process of calculating th e
difference between the heights should be performed for each node like n2,
n3, n4, n5, n6 and n7. When we process each node, then we will find that
the value of k is not more than 1, so we can say that the above tree is a
balanced binary tree . munotes.in

Page 65

Tree Algorithms
65

In the above tree, n6, n4, and n3 are the leaf nodes, where n6 is the farthest
node from the root node. Three edges exist between the root node and the
leaf node; therefore, the height o f the above tree is 3. Wh en we consider
n1 as the root node, then the left subtree contains the nodes n2, n4, n5, and
n6, while subtree contains the node n3. In the left subtree, n2 is a root
node, and n4 and n6 are leaf nodes. Among n4 and n6 nodes, n6 is the
farthest node from i ts root node, and n6 has two edges; therefore, the
height of the left subtree is 2. The right subtree does have any child on its
left and right; therefore, the height of the right subtree is 0. Since the
height of the left subtree is 2 and the right subtre e is 0, so the difference
between the height of the left subtree and right subtree is 2. According to
the definition, the difference between the height of left sub tree and the
right subtree must not be greater than 3. In this case , the difference comes
to be 2, which is greater than 1; therefore, the above binary tree is an
unbalanced binary search tree.

The above tree is a binary search tree because all the left subtree nodes are
smaller than its parent node and all the right su btree nodes are greater t han
its parent node. Suppose we want to want to find the value 79 in the above
tree. First, we compare the value of node n1 with 79; since the value of 79
is not equal to 35 and it is greater than 35 so we move to the node n3, i.e. , munotes.in

Page 66

Fundamental of
Algorithms
66 48. Since the value 79 is not equal to 48 and 79 is greater than 48, so we
move to the right child of 48. The value of the right child of node 48 is 79
which is equal to the value to be searched. The number of hops required to
search an element 79 is 2 a nd the maximum number of hops required to
search any element is 2. The average case to search an element is O(logn).

The above tree is also a binary search tree because all the left subtree
nodes are smaller than its parent node and all the right subtree nodes are
greater than i ts parent node. Suppose we want to find the find the value 79
in the above tree. First, we compare the value 79 with a node n4, i.e., 13.
Since the value 79 is greater than 13 so we move to the right child of node
13, i.e., n2 (21) . The value of the node n 2 is 21 which is smaller than 79,
so we again move to the right of node 2 3. The value of right child of node
21 is 29. Since the value 79 is greater than 29 so we move to the right
child of node 29. The value of right child of node 29 is 35 which is smalle r
than 79 so we move to the right child of node 35, i.e., 48. The value 79 is
greater than 48, so we move to the right child of node 48. The value of
right child node of 48 is 79 which is equal to the value to be searched. In
this case, the number of hops required to search an element is 5. In this
case, the worst case is O(n).
If the number of nodes increases, the formula used in the tree diagram1 is
more efficient than the formula used in the tree diagram2. Suppose the
number of n odes available in both ab ove trees is 100,000. To search any
element in a tree diagram2, the time taken is 100,000µs whereas the time
taken to search an element in tree diagram is log(100,000) which is equal
16.6 µs. We can observe the enormous difference in time between above
two trees. Therefore, we conclude that the balance binary tree provides
searching more faster than linear tree data structure. munotes.in

Page 67

Tree Algorithms
67 What is AVL Trees?
An AVL tree is a type of binary search tree. Named after it's inventors
Adelson, Velskii , and Landis, AVL trees h ave the property of dynamic
self-balancing in addition to all the other properties exhibited by binary
search trees.
A BST is a data structure composed of nodes. It has the following
guarantees:
1. Each tree has a root node (at the to p)
2. The root node has zero , one, or two child nodes
3. Each child node has zero, one, or two child nodes
4. Each node has up to two children
5. For each node, its left descendants are less than the current node,
which is less than the right descendants
AVL trees hav e an additional guarantee :
1. The difference between the depth of right and left sub -trees cannot be
more than one. This difference is called the balance factor.

In order to maintain this guarantee, an implementation of an AVL will
include an algorithm to re balance the tree when add ing an additional
element would upset this guarantee
AVL trees have a worst case lookup, insert, and delete time of O(log n),
where n is the number of nodes in the tree. The worst case space
complexity is O(n) .
AVL Insertion Proces s
Insertion in an AVL tre e is similar to insertion in a binary search tree. But
after inserting and element, you need to fix the AVL properties using left
or right rotations:
 If there is an imbalance in the left child's right sub -tree, perform a left -
right rotation
 If there is an imbalance in the left child's left sub -tree, perform a right
rotation
 If there is an imbalance in the right child's right sub -tree, perform a left
rotation
 If there is an imbalance in the right child's left sub -tree, perform a
right-left rotation munotes.in

Page 68

Fundamental of
Algorithms
68 AVL Tree Rotations
In AVL trees, after each operation like insertion and deletion, the balance
factor of every node needs to be checked. If every node satisfies the
balance factor condition, then the operation can be concluded. Otherwise,
the tree needs to be rebal anced using rotation operations.
There are four rotations and they are classified into two types:
Left Rotation (LL Rotation)
In left rotations, every node moves one position to left from the current
position.

Right Rotation (RR Rotation)
In right rotati ons, every node moves one position to right from the current
position.
Left-Right Rotation (LR Rotation)
Left-right rotations are a combination of a single left rotation followed by
a single right rotation.
First, every node moves one position to the left, then one position to the
right from the current position.
Right -Left Rotation (RL Rotation)
Right -left rotations are a combination of a single right rotation followed
by a single left rotation.
First, every node moves one position to the right then, then one position to
the left from the current position.
Application of AVL Trees
AVL trees are beneficial in cases like a database where insertions and
deletions are not that frequent, but you frequently check for entries.
Python Funct ions


munotes.in

Page 69

Tree Algorithms
69 Define the class and initialize the nodes class avl_Node(object):
def __init__(self, value):
self.value = value
self.leaf = None
self.root = None
self.height = 1
Define a function to calculate height and Balance Factor. def avl_Height(s elf, root):
if not root:
return 0
return root.height

def avl_BalanceFactor(self, root):
//base case for leaf nodes
if not root:
return 0
//implementing the above mentio ned formula
retur n self.avl_Height(root.l) - self.avl_Height(root.r)
Define a function to find an empty node def avl_MinValue(self, root):
if root is None or root.left is None:
return root
return self.avl_MinValue(root. left)
Define a function to traverse the tree in a preorder way. def preOrder(self, root):
if not root:
return
print("{0} ".format(root.value), end=" ") munotes.in

Page 70

Fundamental of
Algorithms
70 self.preOrder(root.left)
self.preOrder(root.right)
Define functions for rotations def leftRotate(self, b):
a = b.right
T2 = a.left
a.left = b
b.right = T2
b.height = 1 + max(self.avl_Height(b.left),
self.avl_Height(b.right))
a.height = 1 + max(self.avl_Height(a.le ft),
self.avl_Height(a.right))
return a
def rightRotate(self, b):
a = b.left
T3 = a.right
a.right = z
b.left = T3
b.height = 1 + max(self.avl_Height( b.left),
self.avl_Height(b.right))
a.height = 1 + max(self.avl_Height(a.left),
self.avl_Height(a.right))
return a
Define a function for inserting a node in AVL tree in Python def insert _node(self, root, value):
if not root:
return avl_Node(value)
elif value < root.value:
root.left = self.insert_node(root.left, value) munotes.in

Page 71

Tree Algorithms
71 else:
root.right = self.insert_node(root.right, value)

root.height = 1 + max(self.avl_Height(root.left),
self.avl_Height(root.right))
# Update the balance factor and balance the tree
balanceFactor = self.avl_BalanceFactor(root)
if balanceFactor > 1:
if value < root.left.value:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor < -1:
if value > root.right.value:
return self.leftRotate(root)
else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
Define a function for deleting a node from the AVL tree in Python def delete_node(self, root, value):
# Find the node to be deleted and remove it
if not root:
return root
elif value < root.value:
root.left = self.delete_node(root.left, value)
elif value > root.value:
root.right = self.delete_node(root.right, value) munotes.in

Page 72

Fundamental of
Algorithms
72 else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.avl_MinValue(root.right)
root.value = temp.key
root.right = self.delete_node(root.right, temp.value)
if root is None:
retur n root
# Update the balance factor of nodes
root.height = 1 + max(self.avl_Height(root.left),
self.avl_Height(root.right))
balanceFactor = self.avl_BalanceFactor(root)
# Balance the tree
if balanceFactor > 1:
if self.avl_BalanceFactor(root.left) >= 0:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balan ceFactor < -1:
if self.avl_BalanceFactor(root.right) <= 0:
return self.leftRotate(root)
munotes.in

Page 73

Tree Algorithms
73 else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
Complete Code for AVL Tree in Python class avl_Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
class AVLTree(object):
def insert_nod e(self, root, value):
if not root:
return avl_Node(value)
elif value < root.value:
root.left = self.insert_node(root.left, value)
else:
root.right = self.insert_node(root.right, value)
root.height = 1 + max(self .avl_Height(root.left),
self.avl_Height(root.right))
# Update the balance factor and balance the tree
balanceFactor = self.avl_BalanceFactor(root)
if balanceFactor > 1:
if value < root.left .value:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root) munotes.in

Page 74

Fundamental of
Algorithms
74 if balanceFactor < -1:
if value > root.right.value:
return self.leftRotate(root)
else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def avl_Height(self, root):
if not root:
return 0
return root.height
# Get balance factore of the node
def avl_BalanceFactor(self, root):
if not root:
return 0
return self.avl_Height(root.left) - self.avl_Height(root.right)
def avl_M inValue(self, root):
if root is None or root.left is None:
return root
return self.avl_MinValue(root.left)
def preOrder(self, root):
if not root:
return
print("{0} ".format(root.value), end=" ")
self.preOrder(roo t.left)
self.preOrder(root.right)
def leftRotate(self, b):
a = b.right
T2 = a.left munotes.in

Page 75

Tree Algorithms
75 a.left = b
b.right = T2
b.height = 1 + max(self.avl_Height(b.left),
self.avl_Height(b.right))
a.height = 1 + max(self.avl_Height(a.left),
self.avl_Height(a.right))
return a
def rightRotate(self, b):
a = b.left
T3 = a.right
a.right = b
b.left = T3
b.height = 1 + max(self.avl_Height(b.left),
self.avl_Height(b.right))
a.height = 1 + max(self.avl_Height(a.left),
self.avl_Height(a.right))
return a
def delete_node (self, root, value):
# Find the node to be deleted and remove it
if not root:
return root
elif value < root.value:
root.left = self.delete_node(root.left, value)
elif value > root.value:
root.right = self.delete_ node(root.right, value)
else:
if root.left is None:
temp = root.right
root = None munotes.in

Page 76

Fundamental of
Algorithms
76 return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.avl_MinValue(root.right)
root.value = temp.key
root.right = self.delete_node(root.right, temp.value)
if root is None:
return root
# Update the balance factor of nodes
root.height = 1 + max(self.avl_Height(root.left),
self.avl_Height(root.right))
balanceFactor = self.avl_BalanceFactor(root)
# Balance the tree
if balanceFactor > 1:
if self.avl_BalanceFactor( root.left) >= 0:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor < -1:
if self.avl_BalanceFactor(root. right) <= 0:
return self.leftRotate(root)
else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
munotes.in

Page 77

Tree Algorithms
77 Tree = AVLTree()
root = None
root = Tree.insert_node(root,40)
root = Tree.insert_node(root,60)
root = Tree.insert_node(root,50)
root = Tree.insert_node(root,70)
print("PREORDER")
Tree.preOrder(root)
Output:
PREORDER
50 40 60 70
3.6 LET US SUM UP
Give an algorithm for finding the sum of all elements in a binary
tree.


In the above binary tree sum = 106.
// Java Program to print sum of
// all the ele ments of a binary tree
class GFG
{
static class Node
{
int key;
Node left, right;
}

/* utility that allocates a new munotes.in

Page 78

Fundamental of
Algorithms
78 Node with the given key */
static Node newNode(int key)
{
Node node = new Node();
node.key = key;
node.left = node.right = null;
return (node);
}

/* Function to find sum
of all the elements*/
static int addBT(Node root)
{
if (root == null)
return 0;
return (root.key + addBT(root.left) +
addBT(root.right));
}

// Driver Code
public static void main(String args[])
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.left = newNode(6);
root.right.right = newNode(7);
root.right.left.right = newNode(8);

int sum = addBT(root);
Syste m.out.println("Sum of all the elements is: " + sum);
}
}

Output
Sum of all the elements is: 36
Time Complexity: O(N)
Auxiliary Space: O(1), but if we consider space due to the
recursion call stack then it would be O(h), where h is the height of
the Tree. munotes.in

Page 79

Tree Algorithms
79 Method 2 – Another way to solve this problem is by using Level
Order Traversal. Every time when a Node is deleted from the
queue, add i t to the sum variable.
Implementation:
 C++
 Java
 Python3
 C#
 Javascript
# Python3 Program to print sum of all
# the elements of a binary tree

# Binary Tree Node
class newNode:

# Utility function to create a new node
def __init__( self, key):
self.key = key
self.left = None
self.right = None

# Function to find sum of all the element
def sumBT(root):
# sum variable to track the sum of
# all variables.
sum = 0

q = []

# Pushing the first level.
q.append(root)

# Pushing elements at each level from
# the tree.
while len(q) > 0:
temp = q.pop(0)

# After popping each element from queue
# add its data to the sum variable.
sum += temp.key

if (temp.left != None):
q.append(temp.left)
if temp.right != None:
q.append(temp.right) munotes.in

Page 80

Fundamental of
Algorithms
80 return sum


# Driver Code
if __name__ == '__main__' :
root = newNode( 1)
root.left = newNode( 2)
root.right = newNode( 3)
root.left.left = newNode( 4)
root.left.right = newNode( 5)
root.right.left = newNode( 6)
root.right.right = newNode( 7)
root.right.left.right = newNode( 8)

print("Sum of all elements in the binary tree is: ",
sumBT(root))

# This code is contributed by
# Abhijeet Kumar(abhijeet19403) Output
Sum of all elements in the binary tree is: 36
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 3: Using Morris traversal:
The Morris Traversal algorithm is an in -order tree
traversal algorithm that does not require the use of
a stack or recursion, and uses only constant extra
memory. The basic idea behind the Morris Traver sal
algorithm is to use the right child pointers of th e
nodes to create a temporary link back to the node's
parent, so that we can easily traverse the tree
without using any extra memory.
Follow the steps below to implement the above idea:
1. Initialize a var iable sum to 0 to keep track of the sum of
all nodes i n the binary tree.
2. Initialize a pointer root to the root of the binary tree.
3. While root is not null, perform the following steps:
If the left child of root is null, add the value of root to
sum, and mov e to the right child of root.
If the left child of roo t is not null, find the rightmost node
of the left subtree of root and create a temporary link
back to root.
Move to the left child of root. munotes.in

Page 81

Tree Algorithms
81 4. After the traversal is complete, return sum.
Below is the imp lementation of the above approach:
 C++
// C++ code to implement the morris traversal approach
#include
using namespace std;

// Definition of a binary tree node
struct Node {
int val;
Node* left;
Node* right;
Node(int v)
: val(v)
, left(nullptr)
, right(nullptr)
{
}
};

// Morris Traversal function to find the sum of all nodes in
// a binary tree
long int sumBT(Node* root)
{
long int sum = 0;
while (root != nullptr) {
if (root->left
== nullptr) { // If there is no left child, add
// the value of the current node
// to the sum and move to the
// right child
sum += root->val;
root = root->right;
}
else { // If there is a left child
Node* prev = root->left;
while (
prev->right != nullptr
&& prev->right
!= root) // Find the rightmos t node
// in the left subtree of
// the current node
prev = prev->right;
if (prev->right
== nullptr) { // If the right child of the munotes.in

Page 82

Fundamental of
Algorithms
82 // rightmost node is null, set
// it to the current node and
// move to the left child
prev->right = root;
root = root->left;
}
else { // If the right child of the rightmost
// node is the current node, set it to
// null, add the value of the current
// node to the sum and move to the right
// child
prev->right = nullptr;
sum += root->val;
root = root->right;
}
}
}
return sum;
}

// Driver code
int main()
{
// Example binary tree: 1
// / \
// 2 3
// / \
// 4 5
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);

// Find the sum of all nodes in the binary tree
long int sum = sumBT(root);
cout << "Sum of all nodes in the binary tree is " << sum
<< endl;

return 0;
}
// This code is contributed by Veerendra_Singh_Rajpoot Output
Sum of all nodes in the binary tree is 15 munotes.in

Page 83

Tree Algorithms
83 Time Complexity: O(n) , Because of all the nodes are traversing
only once.
Auxiliary Space: O(1)

3.7 LIST OF REFERENCES
http://www.cs.bu.edu/teac hing/c/tree/binary/
http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Common_
uses

3.8 UNIT END EXERCISE
1. What is Inorder Tree Traversal ?
2. Write a shorte note on Preord er Tree Traversal ?
3. What is Postorder Tree Traversal ?
4. Check if two binary trees are identical or not ??
5. Print bottom view of a binary tree ?
6. Print top view of a binary tree ?
7. In-place convert a binary tree to its sum tree ?
8. Determine w hether the given binary tree nodes are cousins of each
other ?
9. Print cousins of a given node in a binary tree ?
10. Check if a binary tree is a sum tree or not ?
11. Combinations of wor ds formed by replacing given numbers with
corresponding alphabets ?
12. Determine wheth er a binary tree is a subtree of another binary t ree?
13. Find the diameter of a binary tree ?
14. Check if a binary tree is symmetric or not ?
15. Convert a binary tree to its mirror ?
16. Determine if a binary tree can be converted to another by doing any
number of swaps of children ?
17. Find the Lowe st Common Ancestor (LCA) of two nodes in a binary
tree?
18. Print all paths from the root to leaf no des of a binary tree ?
19. Find ancestors of a given node in a binary tree ?
20. Find distance between giv en pairs of nodes in a binary tree ? munotes.in

Page 84

Fundamental of
Algorithms
84 21. Find the diagonal sum of a binary tree ?
22. Sink nodes containing zero to the bottom of a binary tree ?
23. Convert a binary tree to a full tree by removing half nodes ?
24. Truncate a binary tree to remove nodes that lie on a path having a
sum less than `k` ?
25. Find maximum sum root to leaf path in a binary tree ?
26. Check if a binary tree is height -balance d or not ?
27. Convert binary tree to Left -child right -sibling binary tree ?
28. Print all paths from leaf to root node of a binary tree ?
29. Iteratively print the leaf to root path for every leaf node i n a binary
tree?
30. Build a binary tree from a parent array ?
31. Find all nodes at a given distance from leaf nodes in a binary tree ?
32. Count all subtree s having the same value of nodes in a binary tree ?
33. Find the maximum difference between a node and its descendants in
a binary tree ?
34. Find the maximum sum path between two leaves in a binary tree ?
35. Construct a binary tree from inorder and preorder traversal ?
36. Construct a binary tree from inorder and postorder traversals ?
37. Construct a binary tree from inorder and level order sequence ?
38. Construct a full binary tree from the preorder sequence with leaf node
information ?
39. Construct a full binary tree from a preorder and po storder sequence ?
40. Find postorder traversal of a binary tree from its inorder and preorder
sequence ?
41. Set next pointer to the inorder successor of all nodes in a binary tree ?
42. Find preorder traversal of a binary tree from its inorder and postorder
sequence ?
43. Find the difference between the sum of all nodes present a t odd and
even levels in a binary tree ?
44. Clone a binary tree with random pointers ?
45. Threaded Binary Tree — Overview and Implementation ? munotes.in

Page 85

Tree Algorithms
85 46. Determine if a binary tree satisfies the heig ht-balanced property of a
red–black tree ?
47. Construct an ancestor matrix from a binary tree ?
48. Find all possible binary trees having the same inorder traversal ?
49. Perform boun dary traversal on a binary tree ?
50. Check if each node of a binary tree has exactly one child ?
51. Evaluate a Binary Expression Tree ?
52. Construction of an expression tree ?
53. Fix children -sum property in a binary tree ?
54. Maximum path sum in a binary tree ?
55. Create a m irror of an m –ary tree ?
56. Print a two -dimensional view of a binary tree ?
57. Construct a binary tree from an ancesto r matrix ?
58. Determine whether a given binary tree is a BST or not ?
59. Find inorder successor for the given key in a BST ?
60. Fix a binary tree that is only one swap away from becoming a BST?
61. Find the size of the largest BST in a binary tree ?
62. Print binary tre e structure with its contents in C++ ?
63. Maximum Independent Set Problem ?Huffman Coding Compre ssion
Algorithm
64. Construct a Cartesian tree from an inorder traversal ?
65. Calculate the height of a binary tree with leaf nodes forming a
circular doubly linked list ?
66. Link nodes pre sent in each level of a binary tree in the form o f a
linked list ?
67. Convert a ternary tree to a doubly -linked list ?
68. Extract leaves of a binary tree into a doubly -linked list ?
69. Find the vertical sum of a binar y tree ?
70. In-place convert a binary tree to a doubly -linked list ?
71. Check whether the leaf trav ersal of given binary trees is the same or
not? munotes.in

Page 86

Fundamental of
Algorithms
86 72. Efficiently print all nodes between two given levels in a binary tree ?
73. Calculate the height of a binary tree ?
74. Delete a binary tree ?
75. Level order traversal of a binary tree ?
76. Spiral order traversal of a binary tree
77. Reverse level order trav ersal of a binary tree ?
78. Print all n odes of a perfect binary tree in a specific order ?
79. Print left view of a binary tree ?
80. Find the next node at the same level as the given node in a binary
tree?
81. Check if a binary tree is a complete binary tree or not ?
82. Print diagonal traversal o f a binary tree ?
83. Print corner n odes of every level in a binary tree ?
84. Invert Binary Tree ?
85. Convert a binary tree into a doubly -linked list in spiral order ?
86. Check if a binary tree is a min -heap or not ?
87. Invert alternate levels of a perfect binary tree ?
88. Perform vertical traversal of a binary tree ?
89. Compute the maximum number of nodes at any level in a binary tree ?
90. Print right view of a binar y tree ?
91. Find the minimum depth of a binary tree ?
92. Depth -First Search (DFS) vs Breadth -First Search (BFS) ?
93. Print nodes of a binary tree in vertical order ?


munotes.in

Page 87

87 4
GRAPH ALGORITHMS
Unit Structure :
4.0 Objectives
4.1 Introduction to Graph
4.2 An Over view
4.2.1 What is a graph algorithms?
4.2.2 Types of graphs
4.2.3 Application of graphs
4.2.4 Depth first search
4.2.5 Breadth first search
4.2.6 Dijkstra’s pa th algorithm
4.3 Applications of Graphs
4.4 Graph Representation
4.5 Graph traversals
4.6 Topological Sort
4.7 Shortest Path Algorithms
4.8 Minimal Spanning Tree
4.9 conclusions
4.10 Unit End Exercises
4.0 OBJECTIVES
 To learn what a graph is and how it is used.
 To implement the graph abstract data type using multiple internal
representations.
 To see how graphs can be used to solve a wide variety of problems
In this chapter we will study graphs. Graphs are a more general structure
than the trees we studied i n the last chapter; in fact you can think of a tree
as a special kind of graph. Graphs can be used to represent many
interesting things about our world, including systems of roads, airline
flights from city to city, how the Internet is connected, or even t he munotes.in

Page 88

Fundamental of
Algorithms
88 sequence of classes you must take to complete a major in computer
science. We will see in this chapter that once we have a good
representation for a problem, we can use some standard graph algorithms
to solve what otherwise might seem to be a very diffi cult problem.
While it is relatively easy for humans to look at a road map and
understand the relationships between different places, a computer has no
such knowledge. However, we can also think of a road map as a graph.
When we do so we can have our compu ter do interesting things for us. If
you have ever used one of the Internet map sites, you know that a
computer can find the shortest, quickest, or easiest path from one place to
another.
As a student of computer science you may wonder about the courses yo u
must take in order to get a major. A graph is good way to represent the
prerequisites and other interdependencies among courses. Figure 1. shows
another graph. This one represents the courses and the order in which they
must be taken to complete a major in computer science at Luther College.

Figure 1: Prerequisites for a Computer Science Major
What is the purpose of graph algorithms?

Graph algorithms are used to solve the problems of representing graphs as
networks like airline flights, how the Intern et is connected, or social
network connectivity on Facebook. They are also popular in NLP and
machine learning to form networks. munotes.in

Page 89

Graph Algorithms
89 The course is designed to develop skills to design and analyze simple
linear and non linear data structures.
4.1 WHAT IS GRAPHS ?
Graph Algorithms: Introduction, Glossary, Applications of Graphs,
Graph
Graph Algorithms

In this article, you would be learning a brief explanation of some of the
most used graph algorithms, which have massive applications in today's
words. Graphs cove r most high -level data structure techniques that one
experiences while implementing them and to know which graph algorithm
is best for the moment effectively is what you would be learning here.
First, let's get a clear idea from the very basics about graph s.
4.2 WHAT IS A GRAPH ?
A graph is a unique data structure in programming that consists of finite
sets of nodes or vertices and a set of edges that connect these vertices to
them. At this moment, adjacent vertices can be called those vertices that
are conn ected to the same edge with each other. In simple terms, a graph is
a visual representation of vertices and edges sharing some connection or
relationship. Although there are plenty of graph algorithms that you might
have been familiar with, only some of th em are put to use. The reason for
this is simple as the standard graph algorithms are designed in such a way
to solve millions of problems with just a few lines of logically coded
technique. To some extent, one perfect algorithm is solely optimized to
achieve such efficient results.
4.2.1 Types of Graphs
There are various types of graph algorithms that you would be looking at
in this article but before that, let's look at some types of terms to imply the
fundamental variations between them. munotes.in

Page 90

Fundamental of
Algorithms
90 Order: Order de fines the total number of vertices present in the graph.
Size: Size defines the number of edges present in the graph.
Self-loop: It is the edges that are connected from a vertex to itself.
Isolated vertex: It is the vertex that is not connected to any othe r vertices
in the graph.
Vertex degree: It is defined as the number of edges incident to a vertex in
a graph.
Weighted graph: A graph having value or weight of vertices.
Unweighted graph: A graph having no value or weight of vertices.
Directed graph: A gra ph having a direction indicator.
Undirected graph: A graph where no directions are defined.

Let's now carry forward the main discussion and learn about different
types of graph algorithms.
4.2.2 Breadth -First Search
Traversing or searching is one of the most used operations that are
undertaken while working on graphs. Therefore, in breadth -first-
search (BFS), you start at a particular vertex, and the algorithm tries to
visit all the neighbors at the given depth before moving on to the next
level of trave rsal of vertices. Unlike trees, graphs may contain cyclic paths
where the first and last vertices are remarkably the same always. Thus, in
BFS, you need to keep note of all the track of the vertices you are visiting.
To implement such an order, you use a q ueue data structure which First -in,
First-out approach. To understand this, see the image given below. munotes.in

Page 91

Graph Algorithms
91

Algorithm
1. Start putting anyone vertices from the graph at the back of the queue.
2. First, move the front queue item and add it to the list of the visited
node.
3. Next, create nodes of the adjacent vertex of that list and add them
which have not been visited yet.
4. Keep repeating steps two and three until the queue is found to be
empty.
Pseudocode
1. Set all nodes to "not visited";
2. q = new Queue();
3. q.enqueue(i nitial node);
4. while ( q ? empty ) do
5. {
6. x = q.dequeue();
7. if ( x has not been visited )
8. {
9. visited[x] = true; // Visit node x !
10.
11. for ( every edge (x, y) /* we are using all edges ! */ )
12. if ( y has not been visited )
13. q.enqu eue(y); // Use the edge (x,y) !!! munotes.in

Page 92

Fundamental of
Algorithms
92 14. }
15. }
Complexity: 0(V+E) where V is vertices and E is edges.
Applications
BFS algorithm has various applications. For example, it is used to
determine the shortest path and minimum spanning tree. It is also used
in web crawlers to creates web page indexes. It is also used as powering
search engines on social media networks and helps to find out peer -to-peer
networks in BitTorrent.
4.2.4 Depth -first search
In depth -first-search (DFS), you start by particularly from the vertex and
explore as much as you along all the branches before backtracking. In
DFS, it is essential to keep note of the tracks of visited nodes, and for this,
you use stack data structure.

Algorithm
1. Start by putting one of the vertexes of the grap h on the stack's top.
2. Put the top item of the stack and add it to the visited vertex list.
3. Create a list of all the adjacent nodes of the vertex and then add those
nodes to the unvisited at the top of the stack.
4. Keep repeating steps 2 and 3, and the stack becomes empty.
Pseudocode
1. DFS(G,v) ( v is the vertex where the search starts )
2. Stack S := {}; ( start with an empty stack )
3. for each vertex u, set visited[u] := false ; munotes.in

Page 93

Graph Algorithms
93 4. push S, v;
5. while (S is not empty) do
6. u := pop S;
7. if (not visited[u]) then
8. visited[u] := true;
9. for each unvisited neighbour w of uu
10. push S, w;
11. end if
12. end while
13. END DFS()
Applications
DFS finds its application when it comes to finding paths between two
vertices and detecting cycles. Also, topological sorting can b e done using
the DFS algorithm easily. DFS is also used for one -solution puzzles.
Dijkstra's shortest path algorithm
Dijkstra's shortest path algorithm works to find the minor path from one
vertex to another. The sum of the vertex should be such that their sum of
weights that have been traveled should output minimum. The shortest path
algorithm is a highly curated algorithm that works on the concept of
receiving efficiency as much as possible. Consider the below diagram.

Algorithm
1. Set all the vertices to infinity, excluding the source vertex.
2. Push the source in the form (distance, vertex) and put it in the min -
priority queue.
3. From the priority, queue pop out the minimum distant vertex from the
source vertex. munotes.in

Page 94

Fundamental of
Algorithms
94 4. Update the distance after popping out the minimu m distant vertex and
calculate the vertex distance using (vertex distance + weight <
following vertex distance).
5. If you find that the visited vertex is popped, move ahead without using
it.
6. Apply the steps until the priority queue is found to be empty.
Pseu docode
1. function dijkstra(G, S)
2. for each vertex V in G
3. distance[V] <- infinite
4. previous[V] <- NULL
5. If V != S, add V to Priority Queue Q
6. distance[S] <- 0
7. while Q IS NOT EMPTY
8. U <- Extract MIN from Q
9. for each unvisited neighbour V of U
10. temp Distance <- distance[U] + edge_weight(U, V)
11. if tempDistance < distance [V]
12. distance[V] <- tempDistance
13. previous[V] <- U
14. return distance[], previous[]
Applications
Dijkstra's shortest path algorithm is used in finding the distance of travel
from on e location to another, like Google Maps or Apple Maps. In
addition, it is highly used in networking to outlay min -delay path problems
and abstract machines to identify choices to reach specific goals like the
number game or move to win a match.
Cycle detec tion
A cycle is defined as a path in graph algorithms where the first and last
vertices are usually considered. For example, if you start from a vertex and
travel along a random path, you might reach the exact point where you
eventually started. Hence, thi s forms a chain or cyclic algorithm to cover
along with all the nodes present on traversing. Therefore, cycle detection
is based on detecting this kind of cycle. Consider the below image. munotes.in

Page 95

Graph Algorithms
95

Pseudocode
1. Brent's Cycle Algorithm Example
2. def brent(f, x0):
3. # main phase: search successive powers of two
4. power = lam = 1
5. tortoise = x0
6. hare = f(x0) # f(x0) is the element/node next to x0.
7. while tortoise != hare:
8. if power == lam: # time to start a new power of two?
9. tortoise = hare
10. power *= 2
11. lam = 0
12. hare = f(hare)
13. lam += 1
14. # Find the position of the first repetition of length ?
15. tortoise = hare = x0
16. for i in range(lam):
17. # range(lam) produces a list with the values 0, 1, ... , lam-1
18. hare = f(hare)
19. # The distance between the hare and tortoise is now ?.
20. # Next, the hare and tortoise move at same speed until they agree
21. mu = 0
22. while tortoise != hare: munotes.in

Page 96

Fundamental of
Algorithms
96 23. tortoise = f(tortoise)
24. hare = f(hare)
25. mu += 1
26. return lam, mu
Applications
Cyclic algorithms are used in message -based distribu ted systems and
large -scale cluster processing systems. It is also mainly used to detect
deadlocks in the concurrent system and various cryptographic applications
where the keys are used to manage the messages with encrypted values.
4.2.4 Minimum Spaning Trees
A minimum spanning is defined as a subset of edges of a graph having no
cycles and is well connected with all the vertices so that the minimum sum
is availed through the edge weights. It solely depends on the cost of the
spanning tree and the minimu m span or least distance the vertex covers.
There can be many minimum spanning trees depending on the edge
weight and various other factors.

Pseudocode
1. Prim's Algorithm Example
2. ReachSet = {0};
3. UnReachSet = {1, 2, ..., N-1};
4. SpanningTree = {};
5. while ( UnReachSet ? empty )
6. {
7. Find edge e = (x, y) such that:
8. 1. x ? ReachSet
9. 2. y ? UnReachSet
10. 3. e has smallest cost munotes.in

Page 97

Graph Algorithms
97 11. SpanningTree SpanningTree = SpanningTree ? {e};
12. ReachSet ReachSet = ReachSet ? {y};
13. UnReachSet UnReachSet = UnReachSet - {y};
14. }
Applications
Minimum spanning tree finds its application in the network design and is
popularly used in traveling salesman problems in a data structure. It can
also be used to find the minimum -cost weighted perfect matching and
multi -terminal minimum cut problems. MST also finds its application in
the field of image and handwriting recognition and cluster analysis.
Applications of Graph Data Structure
A graph is a non -linear data structure, which consists of vertices(or nodes)
connected by edge s(or arcs) where edges may be directed or undirected.


Thus the development of algorithms to handle graphs is of major interest
in the field of computer science.
Three Applications of Graphs in the area of computer engineering:
1. The applications of graph split broadly into three categories:
a) First, analysis to determine structural properties of a network, such as
the distribution of vertex degrees and the diameter of the graph. A vast
number of graph measures exist.
b) Second, analysis to find a measurable quantity within the network, for
example, for a transportation network, the level of vehicular flow within
any portion of it.
c) Third, analysis of dynamic properties of network. Map of a coun try can
be represented using a graph. Road network, Air network or rail network
can be represented using a graph. Connection among routers in a
communication network can be represented using a graph. Routing of a
packet between two communicating nodes can be done through the
shortest path. munotes.in

Page 98

Fundamental of
Algorithms
98 2. Graph theory is useful in biology and conservation efforts where a
vertex can represent regions where certain species exist and the edges
represent migration paths, or movement between the regions. This
information is important when looking at breeding patterns or tracking the
spread of disease.
3. Different activities of a project can be represented using a graph. This
graph can be useful in project scheduling.
Applications of Graphs to Solve Real -World Problems
Graph s are widely used in many fields. Let us take some real -life
examples and solve them through graphs.
Ten Applications of Graphs
Since graphs are powerful abstractions, they can be essential in
modelling data. Given below are some instances for the applicat ions of
graphs.
1. Social network graphs: Graphs show who knows who, how they
communicate with one other, and how they impact each other, as
well as other social structure relationships. The Facebook graph
showing who follows whom or who sends friend invitati ons to
whom is an example. These can be used to figure out how
information spreads, how topics get popular, how communities
grow, and even who could be a good fit for that person.
2. Graphs in epidemiology: Nowadays, the spread of disease is
widespread worldw ide. Analysing such graphs has become an
essential component in understanding and controlling the spread of
diseases.
3. Utility graphs: The power grid, the Internet, and the water
network are graphs with vertices representing connection points
and edges repr esenting the cables or pipes that connect them.
Understanding the reliability of such utilities under failure or
assault and lowering the costs of building infrastructure that meets
desired needs requires analysing the features of these graphs.
4. Transportat ion networks: In transportation network graphs,
vertices are intersections in road networks, and edges are the road
segments that connect them. Vertices are stops in public transit
networks, and edges are the links that connect them. Many map
systems, such as Google Maps, Bing Maps, and Apple iOS 6 maps,
employ such networks to determine the optimal paths between
sites. They’re also utilised to figure out how traffic flows and how
traffic lights work.
5. Constraint graphs: Graphs are often used to represent co nstraints
among items. For example, the GSM network for cell phones
consists of a collection of overlapping cells. Any pair of cells that
overlap must operate at different frequencies. These constraints can munotes.in

Page 99

Graph Algorithms
99 be modelled as a graph where the cells are vertic es and edges are
placed between overlapping cells.
6. Dependence graphs: Graphs can be used to represent
dependencies or precedences among items. Such graphs are often
used in large projects in laying out what components rely on other
components and used to m inimise the total time or cost to
completion while abiding by the dependences.
7. Document link graphs: The most well -known example is the
web’s link graph, in which each web page is a vertex, and a
directed edge connects each hyperlink. Link graphs are used to
assess the relevancy of online pages, the most acceptable sources
of information, and good link sites, among other things.
8. Finite element meshes: Many models of physical systems in
engineering entail partitioning space into discrete pieces, such as
the flow of air over a vehicle or plane wing, the spread of
earthquakes through the ground, or the structural vibrations of a
building. The elements and the connections between them make up
a graph known as a finite element mesh.
9. Robot planning: The edges repr esent possible transitions between
states, whereas the vertices represent various states for the robot.
This requires approximating continuous motion as a sequence of
discrete steps. Such graph plans are used to plan paths for
autonomous vehicles, for exam ple.
10. Graphs in compilers: Graphs are used extensively in compilers.
They can be used for type inference, so -called data flow analysis,
register allocation, and many other purposes. They are also used in
specialised compilers, such as query optimisation in database
languages.
Graph Representation
In this article, we will discuss the ways to represent the graph. By Graph
representation, we simply mean the technique to be used to store some
graph into the computer's memory.
A graph is a data structure that con sist a sets of vertices (called nodes) and
edges. There are two ways to store Graphs into the computer's memory:
o Sequential representation (or, Adjacency matrix representation)
o Linked list representation (or, Adjacency list representation)
In sequential re presentation, an adjacency matrix is used to store the
graph. Whereas in linked list representation, there is a use of an adjacency
list to store the graph.
In this tutorial, we will discuss each one of them in detail munotes.in

Page 100

Fundamental of
Algorithms
100 Now, let's start discussing the ways o f representing a graph in the data
structure.
Sequential representation
In sequential representation, there is a use of an adjacency matrix to
represent the mapping between vertices and edges of the graph. We can
use an adjacency matrix to represent the un directed graph, directed graph,
weighted directed graph, and weighted undirected graph.
If adj[i][j] = w, it means that there is an edge exists from vertex i to vertex
j with weight w.
An entry A ij in the adjacency matrix representation of an undirected gr aph
G will be 1 if an edge exists between V i and V j. If an Undirected Graph G
consists of n vertices, then the adjacency matrix for that graph is n x n, and
the matrix A = [aij] can be defined as -
aij = 1 {if there is a path exists from V i to V j}
aij = 0 {Otherwise}
It means that, in an adjacency matrix, 0 represents that there is no
association exists between the nodes, whereas 1 represents the existence of
a path between two edges.
If there is no self -loop present in the graph, it means that the diagonal
entries of the adjacency matrix will be 0.
Now, let's see the adjacency matrix representation of an undirected graph.

In the above figure, an image shows the mapping among the vertices (A,
B, C, D, E), and this mapping is represented by using the adjace ncy
matrix.
There exist different adjacency matrices for the directed and undirected
graph. In a directed graph, an entry A ij will be 1 only when there is an
edge directed from V i to V j.
Adjacency matrix for a directed graph
In a directed graph, edges repr esent a specific path from one vertex to
another vertex. Suppose a path exists from vertex A to another vertex B; it
means that node A is the initial node, while node B is the terminal node. munotes.in

Page 101

Graph Algorithms
101 Consider the below -directed graph and try to construct the adjace ncy
matrix of it.

In the above graph, we can see there is no self -loop, so the diagonal entries
of the adjacent matrix are 0.
Adjacency matrix for a weighted directed graph
It is similar to an adjacency matrix representation of a directed graph
except th at instead of using the '1' for the existence of a path, here we have
to use the weight associated with the edge. The weights on the graph edges
will be represented as the entries of the adjacency matrix. We can
understand it with the help of an example. C onsider the below graph and
its adjacency matrix representation. In the representation, we can see that
the weight associated with the edges is represented as the entries in the
adjacency matrix.
ADVERTISING

In the above image, we can see that the adjace ncy matrix representation of
the weighted directed graph is different from other representations. It is
because, in this representation, the non -zero values are replaced by the
actual weight assigned to the edges.
Adjacency matrix is easier to implement an d follow. An adjacency matrix
can be used when the graph is dense and a number of edges are large.
Though, it is advantageous to use an adjacency matrix, but it consumes
more space. Even if the graph is sparse, the matrix still consumes the same
space. munotes.in

Page 102

Fundamental of
Algorithms
102 Linked list representation
An adjacency list is used in the linked representation to store the Graph in
the computer's memory. It is efficient in terms of storage as we only have
to store the values for edges.
Let's see the adjacency list representation of an undirected graph.

In the above figure, we can see that there is a linked list or adjacency list
for every node of the graph. From vertex A, there are paths to vertex B
and vertex D. These nodes are linked to nodes A in the given adjacency
list.
An adjac ency list is maintained for each node present in the graph, which
stores the node value and a pointer to the next adjacent node to the
respective node. If all the adjacent nodes are traversed, then store the
NULL in the pointer field of the last node of th e list.
The sum of the lengths of adjacency lists is equal to twice the number of
edges present in an undirected graph.
Now, consider the directed graph, and let's see the adjacency list
representation of that graph.

For a directed graph, the sum of the lengths of adjacency lists is equal to
the number of edges present in the graph.
Now, consider the weighted directed graph, and let's see the adjacency list
representation of that graph. munotes.in

Page 103

Graph Algorithms
103

In the case of a weighted directed graph, each node contains an ext ra field
that is called the weight of the node.
In an adjacency list, it is easy to add a vertex. Because of using the linked
list, it also saves space.
Implementation of adjacency matrix representation of Graph
Now, let's see the implementation of adjacen cy matrix representation of
graph in C.
In this program, there is an adjacency matrix representation of an
undirected graph. It means that if there is an edge exists from vertex A to
vertex B, there will also an edge exists from vertex B to vertex A.
Here, there are four vertices and five edges in the graph that are non -
directed.
1. /* Adjacency Matrix representation of an undirected graph in C */
2.
3. #include
4. #define V 4 /* number of vertices in the graph */
5.
6. /* function to initialize the matrix to zero */
7. void init(int arr[][V]) {
8. int i, j;
9. for (i = 0; i < V; i++)
10. for (j = 0; j < V; j++)
11. arr[i][j] = 0;
12. }
13.
14. /* function to add edges to the graph */
15. void insertEdge( int arr[][V], int i, int j) { munotes.in

Page 104

Fundamental of
Algorithms
104 16. arr[i][j] = 1;
17. arr[j][i] = 1;
18. }
19.
20. /* function to print the matrix elements */
21. void printAdjMatrix( int arr[][V]) {
22. int i, j;
23. for (i = 0; i < V; i++) {
24. printf( "%d: ", i);
25. for (j = 0; j < V; j++) {
26. printf( "%d ", arr[i][j]);
27. }
28. printf( "\n");
29. }
30. }
31.
32. int main() {
33. int adjMatrix[V][V];
34.
35. init(adjMatrix);
36. insertEdge(adjMatrix, 0, 1);
37. insertEdge(adjMatrix, 0, 2);
38. insertEdge(adjMatrix, 1, 2);
39. insertEdge(adjMatrix, 2, 0);
40. insertEdge(adjMatrix, 2, 3);
41.
42. printAdjMatrix(adjMatrix);
43.
44. return 0; munotes.in

Page 105

Graph Algorithms
105 45. }
Outpu t:
After the execution of the above code, the output will be -

Implementation of adjacency list representation of Graph
Now, let's see the implementation of adjacency list representation of graph
in C.
In this program, there is an adjacency list represen tation of an undirected
graph. It means that if there is an edge exists from vertex A to vertex B,
there will also an edge exists from vertex B to vertex A.
1. /* Adjacency list representation of a graph in C */
2. #include
3. #include
4.
5. /* structure to represent a node of adjacency list */
6. struct AdjNode {
7. int dest;
8. struct AdjNode* next;
9. };
10.
11. /* structure to represent an adjacency list */
12. struct AdjList {
13. struct AdjNode* head;
14. };
15.
16. /* structure to represent the graph */
17. struct Graph {
18. int V; /*number of vertices in the graph*/
19. struct AdjList* array; munotes.in

Page 106

Fundamental of
Algorithms
106 20. };
21.
22.
23. struct AdjNode* newAdjNode( int dest)
24. {
25. struct AdjNode* newNode = (struct AdjNode*)malloc( sizeof (struct
AdjNode));
26. newNode ->dest = dest;
27. newNode ->next = NULL;
28. return newNode;
29. }
30.
31. struct Graph* createGraph( int V)
32. {
33. struct Graph* graph = (struct Graph*)malloc( sizeof (struct Graph));
34. graph ->V = V;
35. graph -
>array = (struct AdjList*)malloc(V * sizeof (struct AdjList));
36.
37. /* Initiali ze each adjacency list as empty by making head as NUL
L */
38. int i;
39. for (i = 0; i < V; ++i)
40. graph ->array[i].head = NULL;
41. return graph;
42. }
43.
44. /* function to add an edge to an undirected graph */
45. void addEdge( struct Graph* graph , int src, int dest)
46. { munotes.in

Page 107

Graph Algorithms
107 47. /* Add an edge from src to dest. The node is added at the beginnin
g */
48. struct AdjNode* check = NULL;
49. struct AdjNode* newNode = newAdjNode(dest);
50.
51. if (graph ->array[src].head == NULL) {
52. newNode ->next = graph ->array[src].head;
53. graph ->array[src].head = newNode;
54. }
55. else {
56.
57. check = graph ->array[src].head;
58. while (check ->next != NULL) {
59. check = check ->next;
60. }
61. // graph ->array[src] .head = newNode;
62. check ->next = newNode;
63. }
64.
65. /* Since graph is undirected, add an edge from dest to src also */
66. newNode = newAdjNode(src);
67. if (graph ->array[dest].head == NULL) {
68. newNode ->next = graph ->array[dest] .head;
69. graph ->array[dest].head = newNode;
70. }
71. else {
72. check = graph ->array[dest].head;
73. while (check ->next != NULL) {
74. check = check ->next;
75. } munotes.in

Page 108

Fundamental of
Algorithms
108 76. check ->next = newNode;
77. }
78. }
79. /* function to print the adjacency list representation of graph*/
80. void print( struct Graph* graph)
81. {
82. int v;
83. for (v = 0; v < graph ->V; ++v) {
84. struct AdjNode* pCrawl = graph ->array[v].head;
85. printf( "\n The Adjacency list of vertex %d is: \n head ", v);
86. while (pCrawl) {
87. printf( "-> %d", pCrawl ->dest);
88. pCrawl = pCrawl ->next;
89. }
90. printf( "\n");
91. }
92. }
93.
94. int main()
95. {
96.
97. int V = 4;
98. struct Graph* g = createGraph( V);
99. addEdge(g, 0, 1);
100. addEdge(g, 0, 3);
101. addEdge(g, 1, 2);
102. addEdge(g, 1, 3);
103. addEdge(g, 2, 4);
104. addEdge(g, 2, 3); munotes.in

Page 109

Graph Algorithms
109 105. addEdge(g, 3, 4);
106. print(g);
107. return 0;
108. }
Output:
In the output, we will see the adjacen cy list representation of all the
vertices of the graph. After the execution of the above code, the output
will be -

Conclusion
Here, we have seen the description of graph representation using the
adjacency matrix and adjacency list. We have also seen th eir
implementations in C programming language.
So, that's all about the article. Hope, it will be helpful and informative to
you.

Graph traversal
In this section we will see what is a graph data structure, and the traversal
algorithms of it.
The graph i s one non -linear data structure. That is consists of some nodes
and their connected edges. The edges may be director or undirected. This
graph can be represented as G(V, E). The following graph can be
represented as G({A, B, C, D, E}, {(A, B), (B, D), (D, E), (B, C), (C, A)})
The graph has two types of traversal algorithms. These are called the
Breadth First Search and Depth First Search. munotes.in

Page 110

Fundamental of
Algorithms
110 Breadth First Search (BFS)
The Breadth First Search (BFS) traversal is an algorithm, which is used to
visit all of the nodes of a given graph. In this traversal algorithm one node
is selected and then all of the adjacent nodes are visited one by one. After
completing all of the adjacent vertices, it moves further to check another
vertices and checks its adjacent vertices again.
Algorithm
bfs(vertices, start)
Input: The list of vertices, and the start vertex.
Output: Traverse all of the nodes, if the graph is connected.
Begin
define an empty queue que
at first mark all nodes status as unvisited
add the start vertex into the que
while que is not empty, do
delete item from que and set to u
display the vertex u
for all vertices 1 adjacent with u, do
if vertices[i] is unvisited, then
mark vertices[i] as temporarily visited
add v into the queue
mark
done
mark u as completely visited
done
End
Depth First Search (DFS)
The Depth First Search (DFS) is a graph traversal algorithm. In this
algorithm one starting vertex is given, and when an adjacent v ertex is
found, it moves to that adjacent vertex first and try to traverse in the same
manner. munotes.in

Page 111

Graph Algorithms
111 Algorithm
dfs(vertices, start)
Input: The list of all vertices, and the start node.
Output: Traverse all nodes in the graph.
Begin
initially make the state to unvisited for all nodes
push start into the stack
while stack is not empty, do
pop element from stack and set to u
display the node u
if u is not visited, then
mark u as visited
for all nodes i connected to u, do
if ith vertex is unvisited, then
push ith vertex into the stack
mark ith vertex as visited
done
done
End
4.6 TOPOLOGICAL SORT
The topological sort algorithm takes a directed graph and returns an
array of the nodes where each node appears before all the nodes it points
to.
Since node 1 points to nodes 2 and 3, node 1 appears before them in the
ordering. And, since nodes 2 and 3 both point to node 4, they appear
before it in the ordering.
So [1, 2, 3, 4, 5] would be a topological ordering of the graph.
Can a graph have more than one valid topological ordering? Yep! In the
example above, [1, 3, 2, 4, 5] works too. munotes.in

Page 112

Fundamental of
Algorithms
112 Cyclic Graphs
Look at this directed graph with a cycle:
The cycle creates an impossible set o f constraints —B has to be
before and after D in the ordering.
As a rule, cyclic graphs don't have valid topological orderings.
The Algorithm
How can we produce a topological ordering for this directed graph?
Well, let's focus on the first node in the topol ogical ordering. That node
can't have any incoming directed edges; it must have an indegree ↴ of
zero.
Why?
Because if it had incoming directed edges, then the nodes pointing to it
would have to come first.
So, we'll find a node with an indegree of zero and add it to the topological
ordering.
That covers the first node in our topological ordering . What about the next
one?
Once a node is added to the topological ordering, we can take the node,
and its outgoing edges, out of the graph.
Then, we can repeat our earlier approach: look for any node with an
indegree of zero and add it to the ordering.
This is a common algorithm design pattern:
1. Figure out how to get the first thing.
2. Remove the first thing from the problem.
3. Repeat.
Note: this isn't the only way to produce a topological ordering.
Implementation
We'll use the strategy we outlined above:
1. Ident ify a node with no incoming edges.
2. Add that node to the ordering.
3. Remove it from the graph.
4. Repeat. munotes.in

Page 113

Graph Algorithms
113 We'll keep looping until there aren't any more nodes with indegree zero.
This could happen for two reasons:
 There are no nodes left. We've taken all of them out of the graph and
added them to the topological ordering.
 There are some nodes left, but they all have incoming edges. This
means the graph has a cycle, and no topological ordering exists.
One small tweak. Instead of actually removing the nodes from th e graph
(and destroying our input!), we'll use a hash map to track each node's
indegree. When we add a node to the topological ordering, we'll
decrement the indegree of that node's neighbors, representing that those
nodes have one fewer incoming edges.
Let's code it up!
deftopological_sort( digraph ):
# digraph is a dictionary:
# key: a node
# value: a set of adjacent neighboring nodes
# construct a dictionary mapping nodes to their
# indegrees
indegrees ={node :0for node in digraph }
for node in digraph :
forneighbor in digraph [node ]:
indegrees [neighbor ]+=1
# track nodes with no incoming edges
nodes_with_no_incoming_edges =[]
for node in digraph :
if indegrees [node ]==0:
nodes_with_no_incoming_edges .append (node )
# initially, no nodes in our orderi ng
topological_ordering =[]
# as long as there are nodes with no incoming edges
# that can be added to the ordering munotes.in

Page 114

Fundamental of
Algorithms
114 while len(nodes_with_no_incoming_edges )>0:
# add one of those nodes to the ordering
node =nodes_with_no_incoming_edges .pop()
topologi cal_ordering .append (node )
# decrement the indegree of that node's neighbors
forneighbor in digraph [node ]:
indegrees [neighbor ]-=1
if indegrees [neighbor ]==0:
nodes_with_no_incoming_edges .append (neighbor )
# we've run out of nodes with no incoming e dges
# did we add all the nodes or find a cycle?
iflen(topological_ordering )==len(digraph ):
return topological_ordering # got them all
else:
raise Exception ("Graph has a cycle! No topological ordering exists.")
Time and Space Complexity
Breaking the algorithm into chunks, we:
 Determine the indegree for each node. This is O(M) time (where M is
the number of edges), since this involves looking at each directed edge
in the graph once.
 Find nodes with no incoming edges. This is a simple loop through all
the nodes with some number of constant -time appends. O(N) time
(where N is the number of nodes).
 Add nodes until we run out of nodes with no incoming edges. This
loop could run once for every node —O(N) times. In the body, we:
o Do two constant -time operations on an ar ray to add a node to the
topological ordering.
o Decrement the indegree for each neighbor of the node we added. Over
the entire algorithm, we'll end up doing exactly one decrement for
each edge, making this step O(M) time overall .
 Check if we included all no des or found a cycle. This is a
fast (1)O(1) comparison. munotes.in

Page 115

Graph Algorithms
115 All together, the time complexity is O(M+N).
That's the fastest time we can expect, since we'll have to look at all the
nodes and edges at least once.
What about space complexity? Here are the data structures we created:
 indegrees —this has one entry for each node in the graph, so it's
O(N) space.
 nodesWithNoIncomingEdges —in a graph with no edges, this would
start out containing every node, so it's O(N) space in the worst case.
 Topological Ordering —in a graph with no cycles, this will eventually
have every node. O(N) space.
All in all, we have three structures and they're all O(N) space. Overall
space complexity: O(N).
This is the best space complexity we can expect, since we must allocate a
return arra y which costs O(N) space itself.
Uses
The most common use for topological sort is ordering steps of a
process where some the steps depend on each other.
As an example, when making chocolate bundt cake,
 The ingredients have to be mixed before going in the b undt pan.
 The bundt pan has to be greased and floured before the batter can be
poured in.
 The oven has to be preheated before the cake can bake.
 The cake has to be baked before it cools.
 The cake has to cool before it can be iced.
 This process can be repre sented as a directed graph. Each step is a
node, and we'll add directed edges between nodes to represent that one
step has to be done before another. munotes.in

Page 116

Fundamental of
Algorithms
116

 Once we have our dependencies represented using a directed graph, we
can use topological sort to provide a valid ordering to tackle all the
steps.
munotes.in

Page 117

Graph Algorithms
117 Topological sorting of a graph follows the algorithm of ordering the
vertices linearly so that each directed graph having vertex ordering ensures
that the vertex comes before it. Users can understand it more acc urately by
looking at the sample image given below.

In the above example, you can visualize the ordering of the unsorted graph
and topologically sorted graph. The topologically sorted graph ensures to
sort vertex that comes in the pathway.
Pseudocode
1. topological_sort(N, adj[N][N])
2. T = []
3. visited = []
4. in_degree = []
5. for i = 0 to N
6. in_degree[i] = visited[i] = 0
7. for i = 0 to N
8. for j = 0 to N
9. if adj[i][j] is TRUE
10. in_degree[j] = in_degree[j] + 1
11. for i = 0 to N
12. if in_degree[i] is 0
13. enque ue(Queue, i)
14. visited[i] = TRUE
15. while Queue is not Empty
16. vertex = get_front (Queue)
17. dequeue(Queue)
18. T.append(vertex) munotes.in

Page 118

Fundamental of
Algorithms
118 19. for j = 0 to N
20. if adj[vertex][j] is TRUE and visited[j] is FALSE
21. in_degree[j] = in_degree[j] - 1
22. if in_degree[j] is 0
23. enqueue(Queue, j)
24. visited[j] = TRUE
25. return T
Application
Topological sorting covers the room for application in Kahn's and DFS
algori thms. In real -life applications, topological sorting is used in
scheduling instructions and serialization of data. It is also popularly used
to determine the tasks that are to be compiled and used to resolve
dependencies in linkers.
Graph coloring
Graph co loring algorithms follow the approach of assigning colors to the
elements present in the graph under certain conditions. The conditions are
based on the techniques or algorithms. Hence, vertex coloring is a
commonly used coloring technique followed here. F irst, in this method,
you try to color the vertex using k color, ensuring that two adjacent
vertexes should not have the same color. Other method includes face
coloring and edge coloring. Both of these methods should also ensure that
no edge or face should be inconsequent color. The coloring of the graph is
determined by knowing the chromatic number, which is also the smaller
number of colors needed. Consider the below image to understand how it
works.

Pseudocode
1. #include
2. #include
3. using namespace std; munotes.in

Page 119

Graph Algorithms
119 4. // A class that represents an undirected graph
5. class Graph
6. {
7. int V; // No. of vertices
8. list *adj; // A dynamic array of adjacency lists
9. public:
10. // Constructor and destructor
11. Graph(int V) { this->VV = V; adj = new list[V]; }
12. ~Graph() { delete [] adj; }
13. // function to add an edge to graph
14. void addEdge(int v, int w);
15. // Prints greedy coloring of the vertices
16. void greedyColoring();
17. };
18. void Graph::addEdg e(int v, int w)
19. {
20. adj[v].push_back(w);
21. adj[w].push_back(v); // Note: the graph is undirected
22. }
23. // Assigns colors (starting from 0) to all vertices and prints
24. // the assignment of colors
25. void Graph::greedyColoring()
26. {
27. int result[V];
28. // Assign the first color to first vertex
29. result[0] = 0;
30. // Initialize remaining V-1 vertices as unassigned
31. for (int u = 1; u < V; u++)
32. result[u] = -1; // no color is assigned to u munotes.in

Page 120

Fundamental of
Algorithms
120 33. // A temporary array to store the available colors. True
34. // value of available[cr] would mean that the color cr is
35. // assigned to one of its adjacent vertices
36. bool available[V];
37. for (int cr = 0; cr < V; cr++)
38. available[cr] = false;
39. // Assign colors to remaining V-1 vertices
40. for (int u = 1; u < V; u++)
41. {
42. // Process all adjacent vertices and flag their colors
43. // as unavailable
44. list::iterator i;
45. for (i = adj[u].begin(); i != adj[u].end() ; ++i)
46. if (result[*i] != -1)
47. available[result[*i]] = true;
48. // Find the first available color
49. int cr;
50. for (cr = 0; cr < V; cr++)
51. if (available[cr] == false)
52. break ;
53. result[u] = cr; // Assign the found color
54. // Reset the values back to false for the next iteration
55. for (i = adj[u].begin(); i != adj[u].end(); ++i)
56. if (result[*i] != -1)
57. available[result[*i]] = false;
58. }
59. // print the result
60. for (int u = 0; u < V; u++)
61. cout << "Vertex " << u << " ---> Color " munotes.in

Page 121

Graph Algorithms
121 62. << result [u] << endl;
63. }
64. // Driver program to test above function
65. int main()
66. {
67. Graph g1(5);
68. g1.addEdge(0, 1);
69. g1.addEdge(0, 2);
70. g1.addEdge(1, 2);
71. g1.addEdge(1, 3);
72. g1.addEdge(2, 3);
73. g1.addEdge(3, 4);
74. cout << "Coloring of graph 1 \n";
75. g1.greedyColoring();
76. Graph g2(5);
77. g2.addEdge(0, 1);
78. g2.addEdge(0, 2);
79. g2.addEdge(1, 2);
80. g2.addEdge(1, 4);
81. g2.addEdge(2, 4);
82. g2.addEdge(4, 3);
83. cout << "\nColoring of graph 2 \n";
84. g2.greedyColoring();
85. return 0;
86. }
Application
Graph coloring has vast applications in data structures as well as in
solving real -life problems. For example, it is used in timetable scheduling
and assigning radio frequencies for mobile. It is also used in Sudoko and
to check if the given graph is bipartite. Graph coloring can also be used in
geographical maps to mark countries and states in different colors. munotes.in

Page 122

Fundamental of
Algorithms
122 Maximum flow
The maximum flow algorithm is usually treated as a problem -solving
algorithm where the graph is modeled like a network flow infrastructure.
Hence, the maximum flow is determi ned by finding the path of the flow
that has the maximum flow rate. The maximum flow rate is determined
by augmenting paths which is the total flow -based out of source node
equal to the flow in the sink node. Below is the illustration for the same.
1. functio n: DinicMaxFlow(Graph G,Node S,Node T):
2. Initialize flow in all edges to 0, F = 0
3. Construct level graph
4. while (there exists an augmenting path in level graph):
5. find blocking flow f in level graph
6. FF = F + f
7. Update level graph
8. return F
Applications
Like you, the maximum flow problem covers applications of popular
algorithms like the Ford -Fulkerson algorithm, Edmonds -Karp algorithm,
and Dinic's algorithm, like you saw in the pseudocode given above. In rea l
life, it finds its applications in scheduling crews in flights and image
segmentation for foreground and background. It is also used in games like
basketball, where the score is set to a maximum estimated value having
the current division leader.
Matchin g
A matching algorithm or technique in the graph is defined as the edges
that no common vertices at all. Matching can be termed maximum
matching if the most significant number of edges possibly matches with as
many vertices as possible. It follows a specif ic approach for determining
full matches, as shown in the below image. munotes.in

Page 123

Graph Algorithms
123

Applications
Matching is used in an algorithm like the Hopcroft -Karp algorithm and
Blossom algorithm. It can also be used to solve problems using a
Hungarian algorithm that covers con cepts of matching. In real -life
examples, matching can be used resource allocation and travel
optimization and some problems like stable marriage and vertex cover
problem.
Conclusion
In this article, you came across plenty of graph coloring algorithms and
techniques that find their day -to-day applications in all instances of real
life. You learned how to implement them according to situations, and
hence the pseudo code helped you process the information strategically
and efficiently. Graph algorithms are co nsidered an essential aspect in the
field confined not only to solve problems using data structures but also in
general tasks like Google Maps and Apple Maps. However, a beginner
might find it hard to implement Graph algorithms because of their
complex nat ure. Hence, it is highly recommended to go through this
article since it covers everything from scratch.
Shortest Path Algorithms
Dijkstra's Algorithm finds the shortest path between a given node (which
is called the "source node") and all other nodes in a graph. This algorithm
uses the weights of the edges to find the path that minimizes the total
distance (weight) between the source node and all other nodes.
What is Dijkstra’s Algorithm?
Dijkstra’s algorithm is a popular algorithms for solving many single -
source shortest path problems having non -negative edge weight in the
graphs i.e., it is to find the shortest distance between two vertices on a
graph. It was conc eived by Dutch computer scientist Edsger W.
Dijkstra in 1956.
The algorithm maintains a set of visited vertices and a set of unvisited
vertices. It starts at the source vertex and iteratively selects the unvisited munotes.in

Page 124

Fundamental of
Algorithms
124 vertex with the smallest tentative distanc e from the source. It then visits
the neighbors of this vertex and updates their tentative distances if a
shorter path is found. This process continues until the destination vertex is
reached, or all reachable vertices have been visited.
 What is Dijkstra’s Algorithm?
 Need of Dijkstra’s Algorithm (Purpose and Use-Cases)
 Basics of Dijkstra’s Algorithm
 Basics requirements for Implementation of Dijkstra’s Algorithm
 Can Dijkstra’s algorithm work on both directed and undirected graphs?
 Algorithm:
 How Does Dijkst ra’s Algorithm Works?
 Pseudo Code for Dijkstra’s Algorithm
 Ways to Implement Dijkstra’s Algorithm
 Implementation of Dijkstra’s Algorithm:
 1. Dijkstra’s Shortest Path Algorithm using priority_queue (Heap)
 2. Dijkstra shortest path algorithm using Prim’s Algorithm
 3. Dijkstra’s shortest path with minimum edges
 4. Dijkstra’s shortest path algorithm using Set
 Complexity Analysis of Dijkstra’s Algorithm
 Dijkstra’s Algorithm vs Other Algorithms
 Problems Related to Dijkstra’s Algorithm
Need for Dijkstra’s Algorit hm (Purpose and Use-Cases)
The need for Dijkstra’s algorithm arises in many applications where
finding the shortest path between two points is crucial.
For example , It can be used in the routing protocols for computer
networks and also used by map systems to find the shortest path between
starting point and the Destination (as explained in How does Google Maps
work? )
Basic Characterstics of Dijkstra’s Algorithm
 Below are the basic steps of how Dijkstra’s algorithm works:
So Basically, Dijkstra’s algorithm starts at the node source node we
choose and then i t analyzes the graph condition and its paths to find the
optimal shortest distance between the given node and all other nodes in
the graph.
 Dijkstra’s algorithm keeps track of the currently known shortest
distance from each node to the source node and upda tes the value after
it finds the optimal path once the algorithm finds the shortest path
between the source node and destination node then the specific node is
marked as visited. munotes.in

Page 125

Graph Algorithms
125 Basics requirements for Implementation of Dijkstra’s Algorithm
1. Graph : Dijkstra’s Algorithm can be implemented on any graph but it
works best with a weighted Directed Graph with non -negative edge
weights and the graph should be represented as a set of vertices and
edges.
2. Source Vertex: Dijkstra’s Algorithm requires a source node which is
starting point for the search.
3. Destination vertex: Dijkstra’s algorithm may be modified to terminate
the search once a specific destination ver tex is reached.
4. Non-Negative Edges: Dijkstra’s algorithm works only on graphs that
have positive weights this is because during the process the weights of
the edge have to be added to find the shortest path. If there is a negative
weight in the graph then the algorithm will not work correctly. Once a
node has been marked as visited the current path to that node is marked
as the shortest path to reach that node.
Can Dijkstra’s algorithm work on both Directed and Undirected
graphs?
Yes, Dijkstra’s algorithm can work on both directed graphs and undirected
graphs as this algorithm is designed to work on any type of graph as long
as it meets the requirements of having non -negative edge weights and
being connected.
 In a directed graph, each edge has a direction, indicating the direction
of travel between the vertices connected by the edge. In this case, the
algorithm follows the direction of the edges when searching for the
shortest path.
 In an undirected graph, the edges have no direction, and the
algorithm can t raverse both forward and backward along the edges
when searching for the shortest path.
Algorithm for Dijkstra’s Algorithm :
 Mark the source node with a current distance of 0 and the rest with
infinity.
 Set the non -visited node with the smallest current dis tance as the
current node.
 For each neighbor, N of the current node adds the current distance of
the adjacent node with the weight of the edge connecting 0 ->1. If it is
smaller than the current distance of Node, set it as the new current
distance of N.
 Mark the current node 1 as visited.
 Go to step 2 if there are any nodes are unvisited. munotes.in

Page 126

Fundamental of
Algorithms
126 How does Dijkstra’s Algorithm works?
Let’s see how Dijkstra’s Algorithm works with an example given below:
Dijkstra’s Algorithm will generate the shortest path from Node 0 to all
other Nodes in the graph.
Consider the below graph:

Dijkstra’s Algorithm
The algorithm will generate the shortest path from node 0 to all the other
nodes in the graph.
For this graph, we will assume that the weight of the edges represents
the distance between two nodes.
As, we can see we have the shortest path from,Node 0 to Node 1, from
Node 0 to Node 2, from
Node 0 to Node 3, from
Node 0 to Node 4, from
Node 0 to Node 6.
Initially we have a set of resources given below :
 The Distance from the sou rce node to itself is 0. In this example the
source node is 0.
 The distance from the source node to all other node is unknown so we
mark all of them as infinity.
Example: 0 -> 0, 1 -> ∞,2-> ∞,3-> ∞,4-> ∞,5-> ∞,6-> ∞.
 we’ll also have an array of unvisited el ements that will keep track of
unvisited or unmarked Nodes. munotes.in

Page 127

Graph Algorithms
127  Algorithm will complete when all the nodes marked as visited and the
distance between them added to the path. Unvisited Nodes: - 0 1 2 3 4
5 6.
Step 1: Start from Node 0 and mark Node as visited a s you can check in
below image visited Node is marked red.

Dijkstra’s Algorithm
Step 2: Check for adjacent Nodes, Now we have to choices (Either choose
Node1 with distance 2 or either choose Node 2 with distance 6 ) and
choose Node with minimum distance. In this step Node 1 is Minimum
distance adjacent Node, so marked it as visited and add up the distance.
Distance: Node 0 -> Node 1 = 2

Dijkstra’s Algorithm
Step 3: Then Move Forward and check for adjacent Node which is Node
3, so marked it as visited a nd add up the distance, Now the distance will
be:
Distance: Node 0 -> Node 1 -> Node 3 = 2 + 5 = 7 munotes.in

Page 128

Fundamental of
Algorithms
128

Dijkstra’s Algorithm
Step 4: Again we have two choices for adjacent Nodes (Either we can
choose Node 4 with distance 10 or either we can choose Node 5 with
distance 15) so choose Node with minimum distance. In this step Node
4 is Minimum distance adjacent Node, so marked it as visited and add up
the distance.
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 = 2 + 5 + 10 = 17

Dijkstra’s Algorithm
Step 5: Again, Move Forward and check for adjacent Node which
is Node 6, so marked it as visited and add up the distance, Now the
distance will be:
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 -> Node 6 = 2 + 5 + 10
+ 2 = 19 munotes.in

Page 129

Graph Algorithms
129

Dijkstra’s Algorithm
So, the Shortest Distance from the Source Vertex is 19 which is
optimal one
Pseudo Code for Dijkstra’s Algorithm
function Dijkstra(Graph, source):
// Initialize distances to all nodes as infinity, except for the source node.
distances = map infinity to all nodes
distances = 0
// Initialize an empty set of visited nodes and a priority queue to keep
track of the nodes to visit.
visited = empty set
queue = new PriorityQueue()
queue.enqueue(source, 0)
// Loop until all nodes have been visited.
while queue is not empty:
// Dequeue the node with the smallest distance from the priority
queue.
current = queue.dequeue()
// If the node has already been visited, skip it.
if current in visited:
continue
// Mark the node as visited.
visited.add(current)
// Check all neighboring nodes to see if their distances need to be
updated.
for neighbor in Graph.neighbors(current):
// Calculate the tentative distance to the neighbor through the
current node.
tentative_distance = distances[current] +
Graph.distance(current, neighbor) munotes.in

Page 130

Fundamental of
Algorithms
130 // If the tentative distance is smaller than the current distance to the
neighbor, update the distance.
if tentative_distance< distance s[neighbor]:
distances[neighbor] = tentative_distance
// Enqueue the neighbor with its new distance to be considered
for visitation in the future.
queue.enqueue(neighbor, distances[neighbor])
// Return the ca lculated distances from the source to all other nodes in
the graph.
return distances

Ways to Implement Dijkstra’s Algorithm:
There are several ways to Implement Dijkstra’s algorithm, but the most
common ones are:
1. Using priority queue to keep track of all vertices.
2. Using an array to keep track of Distances.
3. Using a set to keep track of the visited vertices.
1. Dijkstra’s Shortest Path Algorithm using priority_queue (Heap)
In this Implementation, we are given a graph and a source vertex in the
graph, finding th e shortest paths from the source to all vertices in the given
graph.
Example:
Input: Source = 0

Example
Output: Vertex
Vertex Distance from Source munotes.in

Page 131

Graph Algorithms
131 0 -> 0
1 -> 2
2 -> 6
3 -> 7
4 -> 17
5 -> 22
6 -> 19
Below is the algorithm based on the above idea:
1. Initialize distances of all vertices as infinite.
2. Create an empty priority_queuepq . Every item of pq is a pair (weight,
vertex). Weight (or distance) is used as first item of pair as first item is
by default used to compare two pairs
3. Insert source vertex into pq and make its distance as 0.
4. While either pq doesn’t become empty
1. Extract minimum distance vertex from pq.
Let the extracted vertex be u.
2. Loop through all adjacent of u and do the following for every vertex v.
3. If there is a shorter path to v throu gh u.
1. Update distance of v, i.e., do dist[v] = dist[u] + weight(u, v)
2. Insert v into the pq (Even if v is already there)
5. Print distance array dist[] to print all shortest paths.
Below is the C++ Implementation of the above approach:
// Program to find Dijkstra's shortest path using
// priority_queue in STL
#include
usingnamespace std;
#define INF 0x3f3f3f3f
// iPair ==> Integer Pair
typedef pair< int, int>iPair;
// This class represents a directed graph using
// adjacency list representation munotes.in

Page 132

Fundamental of
Algorithms
132 classGraph {
intV; // No. of vertices
// In a weighted graph, we need to store vertex
// and weight pair for every edge
list>* adj;
public :
Graph( intV); // Constructor
// function to add an edge to graph
voidaddEdge( intu, intv, intw);
// prints shortest path from s
voidshortestPath( ints);
};
// Allocates memory for adjacency list
Graph::Graph( intV)
{
this->V = V;
adj = newlist[V];
}
voidGraph::addEdge( intu, intv, intw)
{
adj[u].push _back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
// Prints shortest paths from src to all other vertices
voidGraph::shortestPath( intsrc)
{
// Create a priority queue to store vertices that
// are being preprocessed. This is weird syntax in C++. munotes.in

Page 133

Graph Algorithms
133 // Refer below link for details of this syntax
// https://www.geeksforgeeks.org/implement -min-heap -using -stl/
priority_queue, greater>
pq;
// Create a vector for distances and initialize all
// distances as infinite (INF)
vector< int>dist(V, INF);
// Insert source itself in priority queue and initialize
// its distance as 0.
pq.push(make_pair(0, src));
dist[src] = 0;
/* Looping till priority queue becomes empty (or all
distances are not finalized) */
while (!pq.empty()) {
// The first vertex in pair is the minimum distance
// vertex, extract it from priority queue.
// vertex label is stored in second of pair (it
// has to be done this way to keep the vertices
// sorted distance (distance must be first item
// in pair)
intu = pq.top().second;
pq.pop();
// 'i' is used to get all adjacent vertices of a
// vertex
list>::iterator i;
for(i = adj[u].begin(); i != adj[u].end(); ++i) {
// Get vertex label and weight of current
// adjacent of u. munotes.in