I. K. G.

Punjab Technical University

Self Learning Material

MSIT203/ MCA203 DATA STRUCTURES
Section A

Data Structure Introduction to Data Structure: Concept of data, problem analysis, data structures and
data structure operations, notations, mathematical notation and functions, algorithmic
complexity, Big-O Notation and time space trade off. Overview of Arrays, Recursion,
(MSIT- 203) Pointers, Pointer Arithmetic, Array of pointers, Arrays in terms of pointers, Static and
Dynamic Memory Management, Garbage Collection. Understanding & implementation
of various Data Structures with applications. Stack: operations like push, pop and
Course: Masters of Science [IT] various applications like conversion from infix to postfix and prefix expressions,
evaluation of postfix expression using stacks Queues: operations like enqueue,
dequeue on simple, circular and priority queues. Linked Lists: operations like
Semester- II creations, insertion, deletion, retrieval and traversal on single, circular and doubly
linked list.
Section B
Trees definitions and concepts: Root, Node, Leaf Node, Level, Degree, Height and
tree representation using Linked List and Array. Types of Trees: Binary trees, Binary
search tree, Height balanced (AVL) tree, B- trees, B+ Tree. Tree operations: creation,
insertion, deletion and traversals (Preorder, In-order, Postordered) and searching on
various types of trees. Heap: Definition, Structure, Algorithms and applications
Section C
Graph definitions and concepts: Edge, Vertices, and Graph representation using
Adjacency matrix, Adjacency lists Types of graphs: Weighted, Unweighted, Directed,
Undirected Graphs. Graph operations: creation, insertion, deletion, traversals and
searching (depth-first, breadth-first) of various types of graphs and Dijkstra’s algorithm
for shortest distance calculation.
Section D
Searching: Concept and efficiency of linear and binary search algorithms.
Distance Education Programme Sorting: Concepts, Order, Stability, Efficiency of various algorithms (Selection
Sort, Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Radix Sort)
Hashing: Definition, Implementation and applications. Note: Programs are to be
I. K. Gujral Punjab Technical University implemented in C++ Books:
Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by
Cengage
Schaum’s Outline of Data Structures with C++ - Hubbard John. R by Tata McGraw- Hill
Jalandhar Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson
education.

Syllabus

Table of Contents Mr. Vishal Sharma

Assistant Professor
Chapter No. Title Written By Page No. DAV College, Jalandhar,
1 Fundamentals of data structures Ms. Kanchan Gupta, AP, Mayur 1 Punjab, 144001
College, Kapurthala
2 Array Ms. Kanchan Gupta, AP, Mayur 14
College, Kapurthala
3 Linked List Ms. Kanchan Gupta, AP, Mayur 30
College, Kapurthala ©I K Gujral Punjab Technical University Jalandhar
4 Stacks and Queues Ms. Kanchan Gupta, AP, Mayur 51 All rights reserved with I K Gujral Punjab Technical University Jalandhar
College, Kapurthala
5 Introduction to trees Ms. Kanchan Gupta, AP, Mayur 72
College, Kapurthala
6 Traversing binary tree Ms. Kanchan Gupta, AP, Mayur 87
College, Kapurthala

7 Binary Search Tree Ms. Kanchan Gupta, AP, Mayur 106

College, Kapurthala

8 Height balanced trees Ms. Kanchan Gupta, AP, Mayur 125

College, Kapurthala

9 Heap Ms. Kanchan Gupta, AP, Mayur 146

College, Kapurthala
10 Fundamentals of graphs Ms. Kanchan Gupta, AP, Mayur 162
College, Kapurthala

11 Graph operations Ms. Kanchan Gupta, AP, Mayur 179

College, Kapurthala

12 Sorting- 1 Ms. Kanchan Gupta, AP, Mayur 198

College, Kapurthala

13 Sorting- 2 Ms. Kanchan Gupta, AP, Mayur 218

College, Kapurthala

14 Searching Ms. Kanchan Gupta, AP, Mayur 234

College, Kapurthala

Reviewed By:
Lesson- 1 Fundamentals of data structure etc. this input is often called data. Data is a collection of related data items. It has some meaning. Data
Structure can be historical or current. Today's computing tries to gather as much of data as possible. Whether
1.0 Objective useful or not, it is important that you gather as much data as possible. Even though data is meaningful,
1.1 Introduction it is still raw and has no direct benefits that can be drawn from it.
1.2 Data
1.3 Problem analysis It is important that we process data so that knowledge can be derived from it. Processing data also
1.4 Data structures involves careful extraction of only the useful data. Because you collect everything that comes your way,
1.5 Data structure operations it is important that in the end you are able to identify the important data. Once the useful and important
1.6 Algorithmic complexity and time space trade off data has been identified, the data is processed and transformed into information. Information consists
1.7 Mathematical notation and functions of only useful data including the aggregation and summarization of data.
1.8 Asymptotic Notations Information is also stored in the form of charts and graphs.
1.9 Summary
1.10 Glossary For example, consider the sales data of a company from across the country. The data includes the sales
1.11 Answers to check your progress/self assessment questions of each and every product for all the months and from all the respective regions. As the data is for one
1.12 References/ Suggested Readings complete year, you can imagine the size of data. If the data as such is presented to the management, it
1.13 Model questions is of no use for them. What is needed is to convert this data into information.

1.0 Objective Suppose the management wants to discuss the sales of electronic items for 2 regions. It means, only the
After Studying this lesson, students will be able to: sales data of electronic items from 2 regions is extracted. Now there is a need to compute the aggregation
1. Explain the concept of data. of each item for all months. Graphs and charts can be created to show the increase or decrease in the
2. Define the term data structure. sales of this year as compared to the sales of the last year on monthly basis. Sales of newly launched
3. Discuss various operations done on data structures. product can be compared with old products.
4. Explain the algorithm complexity.
5. Discuss various notations to express complexity. Once you have information with you, knowledge can be derived from the same and it can be used by
the management for effective decision making.
1.1 Introduction
Remember the block diagram of computer system. It consists of an input device, processing device and 1.3 Problem analysis
an output device. Imagine how much on data is fed into individual systems of daily basis and its size Data collection is done keeping in mind the problem in hand. Problem definition is the first step.
keeps on increasing day by day. The focus of today's computing is to manage this data effectively, Problems can be from any real life work or standard computer science problem. For example, making
process it and derive knowledge from it. Companies are willing to spend tremendous amount of money a software for library management in which you want to search for books based on indexes like book_Id,
just to derive knowledge from data. In this very first lesson you will learn the concept of data structure Author_Name, etc. So the problem in hand is to search for a book. Search is one the common operations
which is the study of logical representation of data and relationship between data items. What is an performed. Once the problem is defined, you need to record on daily basis data related to all books
algorithm and how you can measure the complexity of an algorithm. issued. Then on the basis of problem definition and data in hand, you design efficient algorithm for the
same.
1.2 Data What is problem analysis? When you approach to find the solution for any defined problem, the
Computer system needs input before it can perform any sort on processing on it. Input can be directly solution has to be within the constraints defined and should also be solvable in finite number of steps.
provided by the user or it can be retrieved from various other sources like internet, files, records, sheets,

1 2

Constraints refer to the availability of resources and you have to limit your solution within the set
constraints. Resources in term of memory, CPU time, etc.
Also the solution has to be in finite number of steps. The steps may take any length of time to execute
when programmed, but the steps cannot be infinite. For some input of size N if the solution is infinite,
the solution is not acceptable. Only the solution that provides answer in finite number of steps for all
values of N is acceptable.
The solution to any problem can be expressed in the form of text or picture. Algorithm is used to express
the solution in terms of text. Algorithm is a well-defined step by step solution for any defined problem.
It is written using simple English or any other human understandable form. Whereas flow chart is used Figure 1.1 Types of data structures
to represent solution in pictorial form. It is used to show the flow of control from beginning to end. You
can get a clear idea of where the flow is heading for with every step or 1. Linear Data structures: Linear data structures are one in which the elements are stored
iteration. sequentially one after the other and there is only one path between all elements in the data structure

Check your progress/ Self assessment questions- 1 a. Array: Arrays is used to represent homogeneous data items or data items of same type
like array of numbers, array of words, etc. data items in an array are stored contiguously in
Q1. Why there is need to process data before deriving knowledge from it?
____________________________________________________________________________ memory. Array is static in nature which means the size and location of memory allocated
to array cannot be changed later on.
___________________________________________________________________________

____________________________________________________________________________ b. Linked List: data items in linked list are stored non-contiguously in memory and each
Q2. What do you understand by designing a solution within constraints? data item is represented as node. Each node contains the location of next node in memory
____________________________________________________________________________ and linked list can be used to represent non-homogeneous data items. Linked list is dynamic
___________________________________________________________________________ in nature which means the size and location of memory allocated to it can be changed at
any time.
____________________________________________________________________________

Q3. Only the solution that provides answer in _____________ number of steps for all values of N is c. Queue: Queue is special FIFO (first in first out) data structure in which the data item
acceptable.
which is inserted first is also the first data item to be removed from the queue. Insertion
Q4. __________________ is used to represent solution in pictorial form. and deletion in queue happens at two different ends of queue. Insertion happens from the
back called the REAR of the queue and deletion happens from the beginning called the
1.4 Data structures
FRONT of the queue.
Data structure is logical organization of data items in memory. Data structure is also used to defined the
relationship between various data items contained in it. Once you collect the data, the purpose for which
d. Stack: Stack is special LIFO (last in first out) data structure in which the data item
the data has been collected and the relationship between the data items varies a great deal. There are a
which is last to be inserted is the first data item to be removed from the stack. Insertion and
number of data structures available and you can choose the best that represents the kind of relationship
deletion in stack are called PUSH & POP and they both happen at one end of the stack
that exists.
called the TOP of the stack.

Types of data structures

2. Non-Linear Data structures: Non-Linear data structures are one in which the elements are not
The data structures are divided into two group:
stored sequentially and there exists multiple paths from one node or data element.

3 4
 a. Tree: Tree data structure is used to represent hierarchical relationship between the data Complexity of the algorithm can be defined using two parameters:
items called nodes. A binary tree T consists of a ROOT node and left sub-tree LR and right
sub-tree RR. LR and RR are further two binary trees. 1. Time complexity: Time complexity for an algorithm can be measured in terms of number of
computational steps or number of operations performed by it.
b. Graph: Graph is a collection of set of vertices (v) that represents the data items and set Worst case: Maximum number of steps needed to execute algorithm successfully for all values of n.
of edges (E) that are used to connect the vertices. Best case: Minimum number of steps needed to execute algorithm successfully for all values of n.
Average case: Average number of steps to execute algorithm for random values of n.
1.5 Data structure operations
2. Space complexity: Space complexity for an algorithm refers to the amount of space needed by
Following are the 6 common operations performed on any data structure. variables, other objects and functions used by it.
Study of algorithm complexity is very important. With tremendous increase in data over last few years,
1. Traversal: Traversal operation is used to apply some process to each element of the data structure. it is important that we continue to design algorithms having lesser complexity than the ones in use today.
Traversal can be defined as an operation to visit each data item in the data structure exactly once.
2. Insertion- Insertion operation is used to add a single data item into the data structure. Time space trade off
3. Deletion- Deletion operation is used to remove a single data item from the data structure. Algorithm complexity is computed using two parameters: time and space. Algorithms for most of the
4. Search- Search operation is used to find the location of a particular data item in the data structure. standard problems have already been designed. Still research is being carried on to design better
5. Merge- Merge operation is used to merge two sorted lists of size m & n respectively and generate a algorithms. It is not easy to design new algorithms that beats old algorithms on both parameters.
single sorted list of size m + n.
6. Sort- Sort operation is used to arrange the data items in the data structure based on some ordering It is possible to compromise on one parameter to improve the second parameter. You can reduce the
rule. Two ordering rules are ascending order and descending order. time complexity of an algorithm by compromising on space and allocating more space for objects used
in algorithms. Similarly you can reduce the space complexity by compromising on time.
1.6 Algorithmic complexity and time space trade off
The best short example to understand time space trade off is swapping of two numbers. There are two
Problem has already been defined earlier in this lesson. Algorithm is a very popular programming tool. possible solutions to this problem. One uses third variable to swap two numbers and one is able to swap
Before you write a program, it is advisable that you begin with algorithm. two numbers without the use of third number. But the number of operations performed by the first
algorithm using three variables is half the operations done by second algorithm. Which shows that there
Algorithm is a well-defined step by step solution for any defined problem. Algorithm is not specific to is clear trade off between time and space. Improvement of one leads to decline in other.
any computer programming language and is generally written in human understandable form. It means
even a layman who has no knowledge computer programming can understand the solution provided in Check your progress/ Self assessment questions- 2

the algorithm. Q5. Define Data structure.

___________________________________________________________________________

When you say that algorithm is a solution to a defined problem, it is possible that two different people ___________________________________________________________________________
can design two different algorithms or solutions for the same problem. It then becomes imperative that
___________________________________________________________________________
you are able to compare the solutions and find which one is more effective than the other. For this you
can compute the complexity of the 2 algorithms and compare the same to select the one with lesser Q6. Data structure is broadly classified as _____________ and _____________________ data
structures.
complexity.

5 6

Q7. Define Queue data structure. b. INT (6) = 6

___________________________________________________________________________
c. INT (-9.7) = -9
___________________________________________________________________________
5. ABS or absolute function on let us day 'a' is used to positive real value in 'a'. If 'a' is positive, same
___________________________________________________________________________
value is returned and if 'a' is negative, it is multiplied by -1 and the result which is positive real
number in returned.
Q8. _____________ is LIFO data structure in which the data item which is last to be inserted is the first
data item to be removed. Some of the examples are as follows:
a. ABS (8.3) = 8.3
Q9. _________________ can be defined as an operation to visit each data item in the data structure
exactly once. b. ABS (-12.1) = 12.1
c. ABS (-19) = 19

1.7 Mathematical notation and functions

6. Summation ∑ symbol or mathematical notation is used to find the sum of set of related numbers
normally stored in an array.
In this section you will learn some of the mathematical notations and functions that are frequently used
in algorithm analysis and even in this SLM at some stage: Consider this,
1. Floor function on let us say 'a' is used to find the greatest integer that does not exceed 'a'.
2. Ceiling function on let us say 'a' is used to find the least integer that is not less than 'a'. Denoted that you want to find the sum of data items starting from index 1 to n in array or set 'a' of size'
If 'a' itself is an integer, than both Floor and Ceiling function on 'a' will return 'a' and also Floor(a) will j'. 'k' is a dummy index.
be equal to Ceiling(a).
For example,
Some of the examples are as follows: Consider the following array with 'j' = 5 elements
a. Floor (8.8) = 8
1 56 323 21 55
b. Ceiling (6.7) = 7
c. Floor (9) = 9
d. Ceiling (11.1) = 12
Hence, = 1 + 56 + 323 + 21 = 401

3. Mod function is used to find the leftover value when a dividend is divided by some divisor. Let us
7. Exponent or integer exponent 'm' is a mathematical notation with following properties:
consider J to be the dividend and K to be the divisor then:
(k mod J) = remainder or leftover
xm = x * x * x ...... * x (m times)
For example,
x0 = 1 x-m = 1/ xm xm/n = n√ am
a. (8 % 3) = 2
For example,
b. (2 % 5) = 2
33 = 3 * 3 * 3 = 27
22 = 1/ 22 = 1 / (2* 2) = 0.25
4. INT function on let us say 'a' converts it into an integer value by removing the fractional part from
it. INT(a) returns Floor (a) which is the greatest integer that does not exceed 'a' if 'a' is positive and
8. Logarithm is related to exponent. Logarithm of any positive number 'a' having base 'b' represents
INT(a) returns Ceiling(a) which is the least integer that is not less than 'a' if 'a' is negative. a. INT
the exponent to which 'b' must be raised to get 'a'.
(8.8) = 8

7 8
Such that, x = logb a is same as bx = a F(n) = 100*1 + 5 = 105 <= c * g(n) = 105 * 1 =105 It
For example, log2 16 = 4 and 24 = is also true for all values of n > 1.
16 Hence f(n)=100n + 5 is Big O(g(n)) = Big O(n) for c =105 and all n >= 1

1.8 Asymptotic Notations Check your progress/ Self assessment questions- 3

Asymptotic notation is also known as growth rate. Asymptotic notation is studied to observe the effect Q10. What is the role of floor and ceiling function?
of growing value of N which is the input size to the time efficiency or complexity of the algorithm. ___________________________________________________________________________

There are total of 3 asymptotic notations that are used to represent that complexity of an algorithm. In ___________________________________________________________________________
this section only the Big O notation is explained as it represents the worst case complexity and is
___________________________________________________________________________
accepted norm.
1. Big O Notation: represented as O() It is used to define only the upper bound of an algorithm Q11. Define asymptotic notation.
___________________________________________________________________________
complexity,. It states that the complexity of given algorithm will never be more than its upper bound. It
is used to represent the worst case complexity and is widely used to represent the complexity of ___________________________________________________________________________
algorithm. f(n) is the complexity of given algorithm and g(n) is some standard function: It is said that
___________________________________________________________________________
f(n) = Big O ( g(n)) if, f(n) <= c g(n) for some positive value of c, and for all values of n >= n0.

Q12. Explain big O Notation.

The notation may not hold true for value of n < n0 or some other value of c.
___________________________________________________________________________

___________________________________________________________________________

___________________________________________________________________________

Q13. Which of the following is not a data structure operation?

a. Merge
b. Sort
c. Insert
d. Pivot

Q14. Which of the following is linear data structure?

Figure 1.2 Big O Notation
a. Linked list
b. Stack
Consider the following, f(n)=100n
c. Array
+5
d. All the above
It can be expressed in terms of Big O as follows:
For f(n)=100n + 5, replacing all constants and selecting the highest degree of n you get g(n) = n
1.9 Summary
Now you need to select some value of c and n0 such that,
Input can be directly provided by the user or it can be retrieved from various other sources like internet,
100n + 5 <= c * n for all value of n >= n0
files, records, sheets, etc. this input is often called data. Data is a collection of related data items. It has
For n0 =1 and c= 105,
some meaning. Data is in raw form and has no direct benefits. Processing data involves careful

9 10

extraction of only the useful data. Once the useful and important data has been identified, the data is 8. Logarithm is related to exponent. Logarithm of any positive number 'a' having base 'b' represents
processed and transformed into information consisting of aggregation and summarization of data. the exponent to which 'b' must be raised to get 'a'.
Information is also stored in the form of charts and graphs. Asymptotic notation is also known as growth rate. Asymptotic notation is studied to observe the effect
When you approach to find the solution for any defined problem, the solution has to be within the of growing value of N which the input size to the time efficiency or complexity of the algorithm. Big O
constraints defined and should also be solvable in finite number of steps. Constraints refer to the notation is used to define only the upper bound of an algorithm complexity. f(n) is the complexity of
availability of resources and you have to limit your solution within the set constraints. Resources in given algorithm and g(n) is some standard function:
term of memory, CPU time, etc. it is said that f(n) = Big O ( g(n)) if, f(n) <= c g(n) for some positive value
of c, and for all values of n >= n0.
Data structure is logical organization of data items in memory. Data structure is also used to define the
relationship between various data items contained in it. 1.10 Glossary
Data structure types: Data Structure- Data structure is logical organization of data items stored in memory.
Linear data structure: array, linked list, stack, queue. Asymptotic Notation- Asymptotic notation is the effect of growing value of N which is the input size to
Non-Linear data structures: tree, graph. the time efficiency or complexity of the algorithm.
Operations on data structures: Big O notation- It is used to define only the upper bound of an algorithm complexity.
Traversal, insertion, deletion, search, merge and sort. Data- Data is a collection of related data items.
Complexity of the algorithm can be defined using two parameters: Algorithm- Algorithm is a well-defined step by step solution for any defined problem.
1. Time complexity: Time complexity for an algorithm can be measured in terms of number of Flow chart- Flow chart is used to represent solution in pictorial form.
computational steps or number of operations performed by it.
2. Space complexity: Space complexity for an algorithm refers to the amount of space needed by 1.11 Answers to check your progress/self assessment questions
variables, other objects and functions used by it. 1. It is important that we process data before we derive knowledge from it. Processing data involves
Some of the mathematical notations and functions frequently used in algorithm analysis are as follows: careful extraction of only the useful data. Once the useful data has been identified, aggregation and
1. Floor function on let us say 'a' is used to find the greatest integer that does not exceed 'a'. summarization of data along with charts and graphs are generated which are helpful in knowledge
2. Ceiling function on let us say 'a' is used to find the least integer that is not less than 'a'. discovery.
3. Mod function is used to find the leftover value when a dividend is divided by some divisor. 2. Constraints refer to the availability of resources and you have to limit your solution within the set
4. INT function on let us say 'a' converts it into an integer value by removing the fractional part from constraints. Resources in term of memory, CPU time, etc. you cannot use more than allocated
it. memory or CPU time set.
5. ABS or absolute function on let us day 'a' is used to positive real value in 'a'. If 'a' is positive, same 3. Finite
value is returned and if 'a' is negative, it is multiplied by -1 and the result which is positive real 4. Flow chart
number in returned. 5. Data structure is logical organization of data items in memory. Data structure is also used to defined
6. Summation ∑ symbol or mathematical notation is used to find the sum of set of related numbers the relationship between various data items contained in it.
normally stored in an array. 6. Linear, Non-Linear.
7. Exponent or integer exponent 'm' is a mathematical notation with following properties: 7. Queue is FIFO data structure in which the data item which is inserted from the back end of the queue
xm = x * x * x ...... * x (m times) called REAR and deletion happens from the beginning end of the queue called FRONT.
x0 = 1 x-m = 1/ 8. Stack.
xm xm/n = n 9. Traversal.
am 10.
a. Floor function on let us say 'a' is used to find the greatest integer that does not exceed 'a'.

11 12
b. Ceiling function on let us say 'a' is used to find the least integer that is not less than 'a'. 2.1 Introduction
11. Asymptotic notation is also known as growth rate. Asymptotic notation is studied to observe the 2.2 Definition of Linear array
effect of growing value of N which the input size to the time efficiency or complexity of the 2.3 Memory representation of linear array
algorithm. 2.4 Basic operations on array
12. Big O Notation is used to define only the upper bound of an algorithm complexity,. It states that the 2.4.1 Traversing a Linear array
complexity of given algorithm will never be more than its upper bound. 2.4.2 Inserting in Linear array
it is said that f(n) = Big O ( g(n)) if, f(n) <= c g(n) for some positive value 2.4.3 Deleting from Linear array
of c, and for all values of n >= n0. 2.5 2-D array
13. d. 2.6 Memory representation of 2-D array
14. d. 2.7 Pointer
2.8 Pointer arithmetic and arrays in terms of pointers
1.12 References/ Suggested Readings 2.9 Array of pointers
1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill 2. 2.10 Static and dynamic memory
Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by 2.11 Summary
Cengage. 2.12 Glossary
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education. 2.13 Answers to check your progress/self assessment questions
2.14 References/ Suggested Readings
1.13 Model questions 2.15 Model questions
1. Explain the concept of data and information in detail.
2. Define data structure and explain various operations implemented on data structure. 2.0 Objective
3. Explain various mathematical functions and notations used in data structures. After studying this lesson, students will be able to:
4. Explain Asymptotic notation and Big O /notation. 1. Define linear data structure array
5. Explain the concept of algorithm complexity. 2. Explain the memory representation of array
3. Explain algorithms for basic operations on array.
4. Explain the memory representation of 2-D array
5. Describe the use of pointers

2.1 Introduction
Array is the most basic data structure used in computer science. It is particularly useful when the size
of data items is small. All operations of data structure are possible on array. Array can be linear in
dimension or multi dimensional. Pointer can be used to point to any location within the array. It is also
possible to create array of pointers. In this lesson you will see the algorithms for basic operations on
array and how linear and 2-D arrays are represented in memory.

Lesson 2 Array 2.2 Definition of Linear array

Structure of the lesson A linear array is collection of homogeneous finite number of data elements that are stored contiguously
2.0 Objective in memory. The elements in an array are accessed using an index number.

13 14

1. Creating a large number of data elements with single identifier and storing them contiguously in
Size represents the size of the array, i.e. the total number of elements that can be stored in an array. The memory.
smallest index number of an array is referenced by LB called lower bound and the largest index number 2. Particularly useful for representing in memory data structures like stacks, queues, trees and graphs.
of an array is referenced by UB called upper bound. 3. Easy and effective data structure for implementing operations like sorting, searching and merging.

size = UB - LB + 1 2.3 Memory representation of linear array

Elements of the array are stored contiguously in memory. It makes it rather easy to access each element
The value of LB can also be negative. It is not mandatory for the first element to be stored at index 1 of the array knowing that the two consecutive elements are stored in two contiguous memory blocks.
always. The address where the first element of the array is stored is called base address of the array and is
denoted as base(ARRAY_NAME).
For example,
If LB = -4 and UB = 7, then size = UB - LB + 1; size = 7 - (-4) + 1; size = 7+4+1 = 12 The first element of the array can be accessed using base(a), where a is the name of any array. We can
access the memory location of kth element of the linear array using the following formulae:
Index Value

-2 12 loc (a[k]) = base (a) + w ( k - LB) where, a is the name of any array k is
the index number of the array element whose location is to be accessed
-1 11 base(a) refers to the base address of the array a.

0 56
w refers to the word size or bytes per storage location for each element of the array. The value of w
1 7 depends on the type of the array. For an array of integer elements, the value of w is 2. For a float array,
the value of w is 4 and for char is it 1. In other words w represents the amount of memory taken by each
2
element of an array of a specified data type.
3
Index Value Memory
4
location
-2 12 100
Table 2.1
-1 11 102

In the last table, the LB of the array is -2 and UB is 4. Hence the size of the array is 4 - (-2) + 1 = 7. 0 56 104
But there are only 4 elements in the array which is 3 less than the size of the array. The index number
1 7 106
of the last element in an array at any given moment of time is denoted by N.
2 26 108
Application of arrays
3 54 110
Arrays are particularly useful in following areas:
4 11 112

15 16
 Table 2.2 2. Apply PROCESS to ARR[I]

[End of For Loop]

Let us consider an integer array (a) as shown in the last table. The base address base (a) is 100 as the
3. Exit
first element of the array is stored at memory location 100. The next element is stored at location 102
which means that the value of w is 2. Let us suppose we want to know the location of element k = 2;

loc (a[k]) = base (a) + w ( k - LB) ALGORITHM TRAVERSE_N (TRAVERSING AN ARRAY) Apply PROCESS operation to
the array(ARR) with lower bound LB and upper bound UB. It is assumed that the array
loc (a[2]) = 100 + 2 ( 2 - (-2)) is NOT full and N points to the index number of last element in the array.
= 100 + 2 ( 4) = 100 + 8 =108
1. I = LB

As you can see in the figure as well, the element with index 2 is stored at memory location 108. 2. Repeat while I <= N

3. Apply PROCESS to ARR[I]

Check your progress/ Self assessment questions
4. I = I + 1
Q1. Define linear array.
____________________________________________________________________________ [End of while Loop]

___________________________________________________________________________ 4. Exit

____________________________________________________________________________
2.4.2 Inserting in Linear array
Q2. What is the memory location of an array element with index k = 3 considering that base address of
Second basic operation is to insert an element at given location in an array.
the array is 120 and it is an float array with LB = -1.
____________________________________________________________________________
ALGORITHM INSERT (INSERTING IN AN ARRAY) insert ITEM at a given location K in
___________________________________________________________________________
the array(ARR) with lower bound LB and upper bound UB. N is the index of the last
element in the array.
____________________________________________________________________________
1. Set I = N [Last element in the array]
Q3. What does UB, LB and N refers to? How can we compute the size of an array?
____________________________________________________________________________ 2. Repeat While (I >= K)

___________________________________________________________________________ 3. Set ARR[I+1] = ARR[I] [Move elements to next index position]

____________________________________________________________________________ 4. Set I = I – 1 [Decrement I by 1]

2.4 Basic operations on array [End of While Loop]

2.4.1 Traversing a Linear array 5. Set ARR[K] = ITEM [Insert ITEM at location K]
Traversing refers to visiting each element of an array exactly once and applying any specified process 6. Set N = N + 1 [Increment the value of N by 1]
to each element.
7. Exit

ALGORITHM TRAVERSE_ALL (TRAVERSING AN ARRAY) Apply PROCESS operation

to the array(ARR) with lower bound LB and upper bound UB. It is assumed that the For example, consider the following array:
array is full.

1. Repeat For I = LB to UB

17 18

There are 6 elements in the array which means N= 6

Let us suppose the location K from where the element is to be delete is 4
According to the algorithm, I is initialized with 4 (i.e. K) and in the first iteration the element at index
5 is shifted to index 4.

In iteration no. 2, the value of I which was incremented to 5 in first iteration results in shifting the
element at index 6 to index position 5.

2.4.3 Deleting from Linear array

Third operation given in this section is to delete an element at given location from an array.
In the last step of the algorithm, the value of N is decremented by 1 to make it 5 and hence makes the
element at position 6 irrelevant. The final array looks like this,
ALGORITHM DELETE (DELETING FROM AN ARRAY) deletes an element at a given
location K in the array(ARR) with lower bound LB and upper bound UB and stores it in
ITEM. N is the index of the last element in the array.

1. Set ITEM = ARR[K] [Assign the element to be deleted at location K to ITEM]

2. Repeat For I = K to N

3. Set ARR[I] = ARR[I+1] [Move the elements one position to the left] 2.5 2-D array

[End of For Loop] 2-D array is a logical representation of array elements in the matrix form. The computer memory is
single dimensional or linear. The logical and physical mapping of linear array is same, but there are
4. Set N = N – 1 [Decrement the value of N by 1]
points to consider in the logical and physical mapping of 2-D arrays. Logical representation is how the
5. Exit
user views the data elements and physical representation is how the elements are actually stored in
memory. The physical representation of 2-D array is discussed in the next section.
For example, consider the following array:

Like in linear array, the elements in 2-D array can be accessed using two index values. One represents
the row number and the other represents the column number of the element to be accessed.

Let LB= 1, UB =10

19 20
 Column-Major Order- In case the column-major order is followed, the entire first column is stored in
memory allocated to 2-D array and then followed by 2nd column and so on.
The same matrix or 2-D array is represented in memory using column-major order as follows

[1, 1] [2, 1] [3, 1] [1, 2] [2, 2] [3, 2] [1, 3] [2, 3] [3, 3]

The address where the first element of the 2-D array is stored is also called base address of the array
and is denoted as base(ARRAY_NAME).

The first element of the array can be accessed using base(a), where a is the name of any array and is
Figure 2.1
always the element with row and column index value of 1 no matter which order of memory
representation you follow. We can access the memory location of [ I, J ] element of the 2-D array as
The figure above shows the logical representation of 2-D array. The element are stored in the form of
follows:
matrix. Each element is indexed using two subscript values.

Row-Major Order
2.6 Memory representation of 2-D array
loc (a[ I, J ]) = base (a) + w [ n ( I -1 ) + ( J -1 ) ] where,
2-D array can be represented in memory using either of the two techniques:
a is the name of any 2-D array
 Row-Major Order
I and J are the index number's of the array element whose location is to be accessed base(a)
 Column-Major Order.
refers to the base address of the array a.
Row-Major Order- As already stated in the previous section, the computer memory is linear. Hence,
w refers to the word size or bytes per storage location for each element of the array. The value of w
the 2-D array is also physically stored in memory linearly. In case the row-major order is followed, the
depends on the type of the array.
entire first row is stored in memory allocated to 2-D array and then followed by 2nd row and so on.
n is the number of columns in the 2-D array
Consider the following logical representation of 2-D array:

Consider the following 2-D array

14 56 11

29 69 89

Table 2.3 (a)

Index Value Memory

Figure 2.2 location

The same is represented in memory using row-major order as follows: [1, 1] 14 100

[1, 2] 56 102

[1, 1] [1, 2] [1, 3] [2, 1] [2, 2] [2, 3] [3, 1] [3, 2] [3, 3] [1, 3] 11 104

21 22

[2, 1] 29 106 w refers to the word size or bytes per storage location for each element of the array. The value of w
depends on the type of the array.
[2, 2] 69 108
m is the number of rows in the 2-D array
[2, 3] 89 110
Index Value Memory
Table 2.3 (b) location
[1, 1] 14 100
Let us consider a 2-D integer array (a) as shown in the tables above. Value of w is 2 and base (a) is
100. Let us suppose we want to know the location of element a[ 1, 3]; [2, 1] 29 102

loc (a[ I, J ]) = base (a) + w [ n ( I -1 ) + ( J -1 ) ] loc (a[1, 3]) =

[1, 2] 56 104
100 + 2 ( 3 (1-1) + (3-1))
= 100 + 2 ( 2) = 100 + 4 =104 [2, 2] 69 106

[1, 3] 11 108
As you can see in the figure as well, the element with index [1,3] is stored at memory location 104.
[2, 3] 89 110
Check your progress/ Self assessment questions
Table 2.4
Q4. Define 2-D array.
____________________________________________________________________________
Let us suppose we want to know the location of element a[ 1, 3];
___________________________________________________________________________ loc (a[ I, J ]) = base (a) + w [ m ( J -1 ) + ( I -1 ) ] loc (a[1, 3])

____________________________________________________________________________
= 100 + 2 ( 2 (3-1) + (1-1))
= 100 + 2 ( 4) = 100 + 8 =108
Q5. Explain two methods of representing 2-D array in memory.
____________________________________________________________________________
As you can see in the figure as well, the element with index [1,3] is stored at memory location 108.
___________________________________________________________________________

____________________________________________________________________________ 2.7 Pointer

Pointer is used to store the base address of a memory reference or block. It can be used to store the
Q6. Find the location of a[3,4] using row-major order when base is 130 and the array is of integer type
with size a[5, 6] ? address of any element or node of a given data structure. For example, base is a pointer that points to
____________________________________________________________________________
the base address of the array. Pointer can be of any basic data type and is from derived data type class.
___________________________________________________________________________
Pointers are particularly useful in traversing the data structure. The concept of linked list data structure
____________________________________________________________________________
is not possible without pointers. The link between two nodes of the linked list is maintained with the
help of the pointer. The address of the next node in the list is stored in the link part of the first node.
Column-Major Order
loc (a[ I, J ]) = base (a) + w [ m ( J -1 ) + ( I -1 ) ] where,
2.8 Pointer arithmetic and arrays in terms of pointers
a is the name of any 2-D array
It is possible to perform basic arithmetic operations like addition and subtraction on pointer type. As
I and J are the index number's of the array element whose location is to be accessed base(a)
already stated, pointer is used to point to some memory location. Performing simple add operation on
refers to the base address of the array a.
pointer, makes it point to the block N blocks ahead of the current block it is pointing to and performing

23 24
simple subtract operation on pointer, makes it point to the block N blocks before of the current block it In case of row-major order memory management, the row number for each row in the 2-D matrix points
is pointing to. to the base address of that row alone in programming and in case of column-major order memory
management, the column number for each column in the 2-D matrix points to the base address of that
For example, consider the following array column alone. It is mainly a programming concept.
Index Value Memory
location 2.10 Static and dynamic memory
-2 12 100 Depending on whether the data structure in use is array or linked list, the memory allocated to the data
structure can either be static or dynamic. Array is a fixed size data structure. Its size cannot be changed
-1 11 102
according to the requirement. Also the size of the array to be created is pre-decided.
0 56 104
Hence, the array uses the concept of static memory management whereby the memory is of fixed size
1 7 106
and is allocated to the data structure when the program is compiled. Program is a sequence of
2 26 108 instructions written in any programming language for the given algorithm.

3 54 110
The linked list follows the concept of dynamic memory management whereby memory to its nodes can
4 11 112 be allocated or de-allocated at run time. It is more useful then the static memory management technique
as it reduces the chances of memory wastage. Linked list is flexible in size. It starts with no nodes and
Table 2.5
depending upon the requirement, new nodes can be added to the linked list and can also removed from
the linked list. The decision of adding nodes to the linked list can be taken when the program is in
Let us suppose, pointer PTR is pointing to the array element with index 0 whose address is 104.
execution.
Adding 2 to the value of pointer as follows:
PTR = PTR + 2
Check your progress/ Self assessment questions
Makes it point to the element with index no. 2 and new value of PTR is 108. The value addition to the
pointer is as follows; Q7. Define pointer.
____________________________________________________________________________
PTR = PTR + 2 is interpreted as; PTR=
PTR + 2(w); ___________________________________________________________________________

where w is the size of the word or memory block which is two in this case as the array is of integer type ____________________________________________________________________________
and integer takes 2 bytes in memory.
Q8. Explain the concept of dynamic memory.
PTR= 104 + 2(2) = 104 + 4 = 8 ____________________________________________________________________________

___________________________________________________________________________
It is possible to store the base address of an array in any pointer and then access each element of the
____________________________________________________________________________
array using the concept of pointer addition.
Q9. Find the location of a[3,4] using column-major order when base is 130 and the array is of integer
type with size a[5, 6] ?
2.9 Array of pointers
____________________________________________________________________________
Array can also be created for pointer type. Array of pointer is used to store a series of addresses in it.
___________________________________________________________________________
2-D array is a good example of array of pointers.
____________________________________________________________________________

25 26

2. loc (a[k]) = base (a) + w ( k - LB) loc (a[3]) = 120 + 4 ( 3 - (-1))

2.11 Summary = 120 + 4 ( 4) = 120 + 16 =136
A linear array is collection of homogeneous finite number of data elements that are stored contiguously
in memory. The elements in an array are accessed using an index number. We can access the memory 3. UB refers to the upper bound or largest index number of an array and LB refers to lower bound
location of kth element of the linear array using the following formulae loc (a[k]) = base (a) + w ( k - or smallest index number of an array. The index number of the last element in an array at any given
LB). We can perform all basic operations on arrays.
moment of time is denoted by N.
We can compute the size of an array using following formulae:
2-D array is a logical representation of array elements in the matrix form. The elements in 2-D array
size = UB - LB + 1
can be accessed using two index values. One represents the row number and the other represents the
column number of the element to be accessed. 2-D array can be represented in memory using either
4. 2-D array is a logical representation of array elements in the matrix form. The elements in 2-D
row-major order or column-major order.
array can be accessed using two index values. One represents the row number and the other represents
the column number of the element to be accessed.
Pointer is used to store the base address of a memory reference or block. It can be used to store the
address of any element or node of a given data structure. Pointer can be of any basic data type and is
5. In Row-major order the entire first row is stored in memory allocated to 2-D array and then
from derived data type class. It is possible to perform basic arithmetic operations like addition and
followed by 2nd row and so on.
subtraction on pointer type. Array can also be created for pointer type. Type of pointer is eventually the
In column-major order the entire first column is stored in memory allocated to 2-D array and then
type of pointer array.
followed by 2nd column and so on.

Depending on whether the data structure in use in array or linked list, the memory allocated to the data
6. loc (a[ I, J ]) = base (a) + w [ n ( I -1 ) + ( J -1 ) ] loc (a[3, 4]) = 130 + 2 ( 6 (3-1) + (4-1))
structure can either be static or dynamic. Array follows static memory management and linked list
= 130 + 2 ( 15) = 130 + 30 =160
follows dynamic memory management technique.

7. Pointer is used to store the base address of a memory reference or block. It can be used to store
2.12 Glossary
the address of any element or node of a given data structure. Pointer can be of any basic data type and
Array- is collection of homogeneous finite number of data elements that are stored contiguously in
is from derived data type class.
memory.
Linked List- Collection of heterogeneous data elements that are stored non-contiguously in memory. 8. The linked list follows the concept of dynamic memory management whereby memory to its
Traversing- Visiting each element in the list exactly once. nodes can be allocated or de-allocated at any time. It is more useful then the static memory management
2-D array- 2-D array is a logical representation of array elements in the matrix form. technique as it reduces the chances of memory wastage.
Pointer- Pointer is used to store the base address of a memory reference or block.
Inserting- Operation to add element in array. 9. loc (a[ I, J ]) = base (a) + w [ m ( J -1 ) + ( I -1 ) ] loc (a[3, 4]) = 130 + 2 ( 5 (4-1) + (3-1))
Deleting- Operation to remove element in array. = 130 + 2 ( 17) = 130 + 34 =164

2.14 References/ Suggested Readings

2.13 Answers to check your progress/self assessment questions 1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill 2.
1. A linear array is collection of homogeneous finite number of data elements that are stored Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by
contiguously in memory. The elements in an array are accessed using an index number. Cengage.

27 28
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education. 3.8.1 Inserting at the beginning of the list
3.8.2 Inserting after a given node
2.15 Model questions 3.9 Deleting from linked list
1. Write algorithm to traverse the element of the array in reverse. 3.10 Header linked list
2. Explain the concept of memory representation of 2-D array in memory. 3.11 Two-way or doubly linked list
3. How can we access all members of an array using pointer? 3.12 Summary
4. Explain the concept of static and dynamic memory? 3.13 Glossary
5. Write algorithm to insert ITEM in an array and also check if the array is full before insert operation. 3.14 Answers to check your progress/self assessment questions
3.15 References/ Suggested Readings
3.16 Model questions

3.0 Objective
After Studying this lesson, students will be able to:
1. Define the linear data structure called linked list.
2. Explain the allocation and de-allocation of memory dynamically to linked list.
3. Demonstrate how the links are maintained between the nodes that are stored non-contiguously in
memory.
4. Explain algorithms for basic operations on linked list.
5. Compare and contrast different types of linked list.

3.1 Introduction
In the last lesson we discussed array; a linear data structure stored contiguously in memory. Also the
size of array is fixed. There are lots of problems with the implementation of array like, if needed the
size of the array cannot be increased and also the size of the array cannot be larger than the available
Lesson 3 Linked list single largest block in memory. In this lesson we will discuss another data structure called linked list
Structure of the lesson that over comes the problems faced while implementing arrays.
3.0 Objective
3.1 Introduction 3.2 Definition of linked list
3.2 Definition of linked list Linked list or singly list is a linear data structure consisting of a group of elements called nodes which
3.3 Memory representation of linked list together represent a linear sequence. Each node in linked list is composed of a data called info part and
3.4 Traversing a linked list a reference called link to the next node in the sequence. The link part of the last node contains NULL
3.5 Searching in a linked list value. This type of structural arrangement allows for efficient insertion or removal of elements at any
3.5.1 Searching in sorted LIST position in the linked list. Linked lists can be used to implement several other abstract data types like,
3.5.2 Searching in unsorted LIST stacks, queues, trees, graphs.
3.6 Memory allocation and garbage collection
3.7 Checking underflow and overflow conditions
3.8 Inserting into a linked list

29 30

EXERCISE 1

Take example of any array and draw linked list representation of the same on
a chart paper.

3.3 Memory representation of linked list

Figure 3.1 Simple linked list

The nodes that may seem sequential are not stored contiguously in memory. Link is used to move
from one node to the next node in the list. The major benefit of using a linked list over a conventional
array is that the elements (nodes) of the linked list can easily be inserted or removed without having to
reallocate or reorganize the entire structure.
It is possible because the elements are not stored contiguously and insert/delete operation only requires
you to change the link between the nodes. Let us have a look at some of the advantages and
disadvantages of using linked list.

Advantages:
1. Dimension or size of the Linked list is dynamic in nature, i.e. memory can be allocated and
deallocated as and when needed during the execution of the program.
2. Insert and delete operations are less costly and can be easily implemented in a linked list.
3. Non-primary or abstract linear data structures such as stacks and queues can be easily implemented
with a linked list.

Disadvantages: Figure 3.2 Memory representation of linked list

1. With each node having to save the link to the next node, it results in wastage of memory.
2. We cannot access the nodes in a linked list randomly, i.e. Nodes in a linked list must be read in order
from the beginning as linked lists can only be accessed sequentially. Here START = 2 means that the first node is stored at location 2.
3. Nodes are stored non-contiguously in memory, hence increasing the time required to access INFO[2] = H and LINK[2]= 5. The next node is stored at location 5.
individual elements within the list. INFO[5] = E and LINK[5]= 3. The next node is stored at location 3.
4. Singly linked lists allow you to traverse only in the forward direction. It is possible to traverse INFO[3] = L and LINK[3]= 1. The next node is stored at location 1.
backward using doubly linked list, but it takes a lot of space in memory. INFO[1] = L and LINK[1]= 8. The next node is stored at location 8.
INFO[8] = H and LINK[8]= 0 or NULL. It means that this is the last node in the list.

3.4 Traversing a linked list

31 32
Traversing is the most basic operation on a linked list. Traversing a linked list is visiting each node of ALGORITHM SUM (INFO, LINK, START, COUNT) the algorithm finds the sum of all
elements of the linked list
the linked list exactly once. We can traverse only in the forward direction using the linked list starting
from the first node to the last node. 1. Set COUNT = 0 [initialize the count]

2. Set PTR = START [initialize the pointer to the first node]

Let LIST be the linked list to be traversed. START pointer contains the address of the first node. Each
node consists of two parts: INFO and LINK. LINK part of a node contains the address of the next node 3. Repeat the steps 3 and 4 while PTR != NULL [till the end of the list]
and the LINK part of the last node contains NULL.
4. COUNT = COUNT + INFO[PTR] [compute sum of nodes till the current node]

The algorithm uses a PTR pointer that points to the node being currently processed. The algorithm starts 5. Set PTR = LINK[PTR] [PTR now points to the next node in the list] [End of step
2 loop]
by assigning the address of the first node to the PTR pointer and then processes each node in the
sequence till the last node is processed. PTR can point to the node next to the current node using the 6. Display COUNT
following statement:
7. Exit

PTR = LINK[PTR] Check your progress/ Self assessment questions

Q1. Define linked list.

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Q2. How a linked list is different from array?

____________________________________________________________________________

Figure 3.3 PTR pointing to the next node in the LIST ___________________________________________________________________________

____________________________________________________________________________
ALGORITHM TRAVERSE (TRAVERSING A LINKED LIST) Apply PROCESS operation to
the linked list (LIST). PTR contains the address of the node being currently processed Q3. How we can detect that we have reached the last node of the linked list?
and START contains the address of the first node in the list. ____________________________________________________________________________

1. Set PTR = START [initialize the pointer to the first node] ___________________________________________________________________________

2. Repeat the steps 3 and 4 while PTR != NULL [till the end of the list] ____________________________________________________________________________

3. Apply PROCESS to INFO[PTR] [perform the operation] 3.5 Searching in a linked list
Let LIST be the linked list in memory. Suppose we want to search for ITEM in the linked list. The
4. Set PTR = LINK[PTR] [PTR now points to the next node in the list] [End of step
2 loop] search algorithm returns the LOC of the ITEM stored in memory. Linear search algorithm is used to
search for ITEM in the list. Beginning from the first node, algorithm searches for the ITEM in the list
5. Exit
sequentially. The search algorithm can be categored into following categories:

For example, the following algorithm finds the sum of all elements of the linked list.
3.5.1 Searching in sorted LIST

33 34

The algorithm searches for ITEM in linked list sequentially beginning from the first node until a node 4. Set LOC = NULL [search unsuccessful]
with greater value than ITEM is encountered.
5. Exit

ALGORITHM SRCHSORTED (INFO, LINK, PTR, LOC, START, ITEM) the algorithm
3.6 Memory allocation and garbage collection
searches for ITEM in sorted LIST. START points to the first node in the LIST and PTR
A linked list is dynamic data structure and it is believed to have the possibility of inserting new nodes
is used to traverse through the LIST. 1. Set PTR = START [Initialize PTR]
into the list and hence requires some mechanism which provides information about unused memory
2. Repeat steps While PTR != NULL
space for storing the new nodes. Also, some mechanism is needed whereby during the delete operation
3. if ITEM > INFO[PTR], Then the memory space of deleted node becomes available for future use. Together with the linked lists (that

PTR = LINK[PTR] [PTR now points to the next node in the list] is memory in use) in memory, a special list is maintained which consists of all unused memory cells.
Such a list is called free- storage list or free pool.
else if ITEM = INFO[PTR], Then set LOC = PTR and exit

[search successful] else set LOC = NULL and exit [search The unused memory cells are linked together to form a linked list with AVAIL as its pointer variable.
unsuccessful] AVAIL points to the first node in the free pool list.

[End of if]

[End of step 2 Loop]

4. Set LOC = NULL [search unsuccessful]

5. Exit

3.5.2 Searching in unsorted LIST

The algorithm searches for ITEM in linked list sequentially beginning from the first node till the last
node. Because the LIST is unsorted, there is no mechanism to identify the direction in which the ITEM
is stored in the LIST

ALGORITHM SRCHSORTED (INFO, LINK, PTR, LOC, START, ITEM) The algorithm
searches for ITEM in unsorted LIST. START points to the first node in the LIST and PTR
is used to traverse through the LIST.
Figure 3.4 Memory representation of AVAIL LIST
1. Set PTR = START [Initialize PTR] The memory cells in the figure above are divided into two categories: used and unused cells. The unused

2. Repeat steps While PTR != NULL 3. if ITEM = INFO[PTR], then cells are linked together and the location of the first free node is stored in pointer called AVAIL.
Here AVAIL = 7 means that the first free node in the list is location 7.
set LOC = PTR and exit [search successful]
LINK[7] = 4. The next free node in the list is location 4.
else if LINK[4] = 10. The next free node in the list is location 10.
PTR = LINK[PTR] [PTR now points to the next node in the list] LINK[10] = 6. The next free node in the list is location 6.
LINK[6] = 9. The next free node in the list is location 9.
[End of if]
LINK[9] = 0. The location 9 is the last free node in the list.
[End of step 2 Loop]

35 36
 ____________________________________________________________________________
When a node is inserted in the list, the first node in the AVAIL list is removed and added to the list and
Q6. What do we mean by overflow condition?
the second node in the AVAIL list becomes the first node. Sometimes a node is deleted from the list or ____________________________________________________________________________
even the entire list may be deleted. There needs to be a mechanism to reuse the space deleted for future
___________________________________________________________________________
use. One method is to insert the deleted node into the AVAIL list immediately when it is deleted. Other
____________________________________________________________________________
than this, operating system also provides alternate methods to achieve the same.

The operating system of a computer from time to time collects all the deleted space onto the free pool 3.8 Inserting into a linked list
list. The technique that does this collection is called garbage collection. Garbage collection is done by Before we apply the insert operation on the linked list, one must check for the overflow condition, if
operating system in two steps. Firstly the operating system runs through all lists, tagging cells which AVAIL = NULL
are currently in use, and then the operating system runs through the memory, collecting all untagged The last condition is used to check if the overflow condition is true or not. In case the condition returns
spaces onto the free pool list. Garbage collection by operating system is invisible to the programmer true, the algorithm must exit immediately.
and the programmer doesn’t need to worry about the same. If the overflow condition is false, we can proceed to insert a node to the linked list. The first step is to
obtain a free node from the AVAIL list and store the location of the same in NEW pointer. It can be

3.7 Checking underflow and overflow conditions achieved using the following two statements:

Before we start with the insert and delete operations on the linked list, it is important to understand the
concept of underflow and overflow conditions. The situation when we want to insert new data into the NEW = AVAIL
linked list, but there is no available space as free pool list is empty; is called overflow. The overflow AVAIL = LINK[AVAIL]
condition occurs with our linked lists when AVAIL = NULL and we want to perform insert operation.
Overflow condition should be checked right at the beginning of the insert operation and in case the
condition returns TRUE, the algorithm should display overflow message and terminate. Similarly,
underflow refers to the situation where there is a request for delete operation on the list and list is
empty. The underflow condition occurs with our linked list when START = NULL and we want to
perform delete operation. Underflow condition should be checked right at the beginning of the delete
operation and in case the condition returns TRUE, the algorithm should display underflow message and
terminate.

Check your progress/ Self assessment questions

Figure 3.5 Assigning a node to NEW pointer from the AVAIL list
Q4. What do we mean by garbage collection?
____________________________________________________________________________
(NEW = AVAIL) assigns the location of first node in the free pool list to NEW.
___________________________________________________________________________ (AVAIL = LINK[AVAIL]) assigns the location of second node in the free pool list to AVAIL.

____________________________________________________________________________
Now the second node becomes the first node in the free pool list.

Q5. What is AVAIL list?

3.8.1 Inserting at the beginning of the list
____________________________________________________________________________
The following algorithm is used to insert a NEW node at the beginning of the LIST.
___________________________________________________________________________

37 38

INSBEG (INFO, LINK, START, AVAIL, and ITEM) the Set LINK[NEW] = LINK[LOC] and LINK[LOC] = NEW
algorithm inserts ITEM as the first node of the LIST. [end of if]
1. if AVAIL = NULL then, Display: OVERFLOW and exit. 5. Exit.
2. [Assign node from free pool list to NEW] Set NEW = AVAIL
3. [Assign second node in the free pool list to AVAIL] AVAIL = LINK[AVAIL].
4. Set INFO[NEW] = ITEM. [Copy ITEM to NEW]
5. Set LINK[New] = START [New node now points to previous first node]
6. Set START = NEW. [NEW becomes the first node]
7. Exit.

Figure 3.7 Inserting NEW node after node X in the list

3.9 Deleting from linked list

Before we apply the delete operation on the linked list, one must check for the underflow condition, if
START = NULL

Figure 3.6 Inserting NEW node to the beginning of the linked list
The last condition is used to check if the underflow condition is true or not. In case the condition returns

3.8.2 Inserting after a given node true, the algorithm must exit immediately.

The following algorithm is used to insert a NEW node after a given node.
If the underflow condition is false, we can proceed to delete a node from the linked list. The first step is
to add the node to be deleted to the AVAIL list and change the LINK of the previous node accordingly.
INSLOC(INFO, LINK, START, AVAIL, ITEM, LOC) It can be achieved using the following two statements:
The algorithm inserts ITEM after the node being pointed by LOC.

1. if AVAIL = NULL then, Display: OVERFLOW and exit. LINK[LOC] = AVAIL and AVAIL = LOC

2. [Assign node from free pool list to NEW] Set NEW =

AVAIL
3. [Assign second node in the free pool list to AVAIL]
AVAIL = LINK[AVAIL].
4. Set INFO[NEW] = ITEM. [Copy ITEM to NEW] 5. if
LOC= NULL, then
[make new the first node of the LIST]
Set LINK[New] = START and START = NEW
else

39 40
 When LOCP = NULL (delete first node)

Figure 3.9 Deleting first node

Otherwise,

Figure 3.8 Assigning the location of deleted node to AVAIL

(LINK[LOC] = AVAIL) assigns the location of first node in the free pool list to LOC (node to be
deleted). Figure 3.10 Deleting node other than the first node

(AVAIL = LOC) assigns the node pointed by LOC to AVAIL. So, LOC becomes the first node of Check your progress/ Self assessment questions

the free pool list. Let us have a look at the algorithm to perform delete operation on linked list. Q7. Write the condition to check if it is possible or not to insert or delete a node from the linked list.
____________________________________________________________________________

DELETE (INFO, LINK, START, AVAIL, LOCP, LOC) ___________________________________________________________________________

The algorithm deletes the node LOC. LOCP is the location of the node previous to LOC
in the list. ____________________________________________________________________________

1. if START = NULL, then Q8. What is the meaning of LOCP = NULL in the delete algorithm of linked list?
____________________________________________________________________________
Display: underflow and exit.
___________________________________________________________________________
2. if LOCP = NULL, then
____________________________________________________________________________
[delete first node]

Set START = LINK[START]

3.10 Header linked list
Else

[remove node other than first node] Header linked list is one that contains a special node at the beginning of the list called header node. The
Set LINK[LOCP] = LINK[LOC] header node is not part of the actual list, but it is used to contain information about the linked list such
as, number of nodes, name of the list, purpose of creating list, etc.
[end of if statement]

3. Set LINK[LOC] = AVAIL and AVAIL = LOC Basically we have two types of header lists,
4. EXIT 1. Grounded header list- It is one in which the LINK part of the last node contains NULL value.

41 42

Two-way list is a special list which can be traversed in both directions; forward direction from the first
node to the last node and backward direction from the last node to the first node. Using two-way list,
we can access both the next and previous nodes to the current node, which makes it possible to delete a
node without traversing any part of the list.

Figure 3.11 Grounded header linked list A node in a two-way list is divided into three parts:
Information field INFO that contains the data part of the node.
START points to the first node in the grounded header list. But header node is not the first node on the A pointer field FORW that contains the location of the next node to the current node in the list.
list. LINK[START] is the location of the first node in the list. In case, LINK[START] = NULL means A pointer field BACK that contains the location of the preceding node to the current node in the list.
the list is empty.

2. Circular header list- It is one in which the LINK part of the last node contains location or
address of the first node in the list.

Figure 3.13 Two-way list

The list also requires two list pointer variables: FIRST, which points to the first node in the list, and
LAST, which points to the last node in the list. Observe that the NULL pointer appears in the FORW
field of the last node in the list and also in the BACK field of the first node in the list. Observe that,
using the variable FIRST and the pointer field FORW, we can traverse a two-way list in the forward
Figure 3.12 Circular header linked list
direction as before. On the other hand, using the variable LAST and the pointer field BACK, we can
also traverse the list in the backward direction.
In case of circular header list, if LINK[START] = START means the list is empty.

Check your progress/ Self assessment questions

ALGORITHM TRAVCIR (TRAVERSING A CIRCULAR LINKED LIST) Apply PROCESS
operation to the circular linked list (LIST). PTR contains the address of the node being Q9. What is two-way list?
currently processed and LINK[START] contains the address of the first node in the list. ____________________________________________________________________________
1. Set PTR = LINK[START] [initialize the pointer the first node]
___________________________________________________________________________
2. Repeat the steps 3 and 4 while PTR != START [till the end of the list]
____________________________________________________________________________
3. Apply PROCESS to INFO[PTR] [perform the operation]
Q10. What do we mean by grounded header list and circular header list?
4. Set PTR = LINK[PTR] [PTR now points to the next node in the list] [end of step 2 ____________________________________________________________________________
loop]
___________________________________________________________________________
5. Exit
____________________________________________________________________________

Two-way header list

3.11 Two-way or doubly linked list

43 44
Two-way header list consists of a special header node which has two pointers. One points to the first AVAIL = FORW[AVAIL]
node in the list and the second points to the last node in the list. Also the BACK field of the first node INFO[NEW] = ITEM
in the list points to the header node and FORW field of the last node in the list points to the header node.
FORW[LOCA] = NEW
FORW[NEW] = LOCB
BACK[LOCB] = NEW
BACK[NEW] = LOCA

Check your progress/ Self assessment questions

11. The situation when in a linked list START=NULL is

Figure 3.14 Two-way header list a. underflow
b. overflow
c. housefull
Traversing the two-way list backwards d. saturated
ALGORITHM TRAVERSEBACK (TRAVERSING A two-way LIST) Apply PROCESS
operation to the linked list (LIST). PTR contains the address of the node being currently
12. You can traverse in both directions using
processed and LAST contains the address of the last node in the list.
a. Singly linked list
1. Set PTR = LAST [initialize the pointer to last node] b. Doubly linked list
2. Repeat the steps 3 and 4 while PTR != NULL [till the beginning of the list] c. Header linked list
d. None of the above
3. Apply PROCESS to INFO[PTR] [perform the operation]

4. Set PTR = BACK[PTR] [PTR now points to the preceding node in the list] 3.12 Summary
[end of step 2 loop] Linked list or singly list is a linear data structure consisting of a group of elements called nodes which
5. Exit together represent a linear sequence. Each node in linked list is composed of a data called info part and
a reference called link to the next node in the sequence. Traversing a linked list is visiting each node
We can perform the delete operation on two-way list using the following statements: the linked list exactly once. We can traverse only in the forward direction using the linked list starting
from the first node to the last node. We can only perform only linear search on the linked list.
FORW[ BACK[LOC] ] = FORW[LOC] The list can either be sorted or unsorted.
BACK[ FORW[LOC] ] = BACK[LOC]
There is a need of some mechanism that provides information about unused memory space for inserting
FORW[LOC] = AVAIL nodes in the list and also some mechanism that makes the deleted nodes available for future use. A
AVAIL = LOC special list is maintained which consists of all unused memory cells called free- storage list or free
pool list. AVAIL points to the first node in the free pool list. The situation when we want to insert new
We can perform the INSERT operation on two-way list using the following statements: data into the linked list, but there is no available space as free pool list is empty; is called overflow.
CONSIDER that we want to insert node NEW between nodes LOCA and LOCB in the list. Underflow refers to the situation where there is a request for delete operation on the list and list is
empty.
NEW = AVAIL

45 46

Header linked list is one that contains a special node at the beginning of the list called header node.
The header node is not part of the actual list, but it is used to contain information about the linked list 4. The operating system from time to time collects all the deleted space onto the free pool list. The

such as, number of nodes, name of the list, purpose of creating list, etc. Grounded header list- It is one technique that does this collection is called garbage collection. The operating system initially runs

in which the LINK part of the last node contains NULL value. Circular header list- It is one in which through all lists, tagging cells which are currently in use, and then the operating system runs through

the LINK part of the last node contains location or address of the first node in the list. the memory, collecting all untagged spaces onto the free pool list.

Two-way list is a special list which can be traversed in both directions; forward direction from the first 5. A special list is maintained in memory which consists of all unused memory cells. Such a list is called

node to the last node and backward direction from the last node to the first node. A node in twoway list AVAIL list, free- storage list or free pool. The unused memory cells are linked together to form a list

consists of INFO, BACK AND FORW fields. with AVAIL as its pointer variable. AVAIL points to the first unused node in the free pool list.

3.13 Glossary 6. The situation when we want to insert new data into the linked list, but there is no available space as

Linked list- It is a linear data structure consisting of a group of elements called nodes which together free pool list is empty; is called overflow. The overflow condition occurs with our linked lists when

represent a linear sequence. AVAIL = NULL and we want to perform insert operation.

Avail list- A special list which consists of all unused memory cells also called free- storage list or free
pool list. 7. Condition to check if we cannot insert into linked list:

Garbage collection- It is a process where operating system of a computer from time to time collects all if AVAIL = NULL // we cannot insert

the deleted space onto the free pool list.

Header list- Header linked list is one that contains a special node at the beginning of the list called Condition to check if we cannot delete from linked list:

header node if START = NULL // we cannot delete

Grounded header list- It is one in which the LINK part of the last node contains NULL value.
Circular header list- It is one in which the LINK part of the last node contains location or address of the 8. It means that the node to be deleted is the first node of the linked list and hence the location of the

first node in the list. node previous to the node to be deleted in NULL.

Two-way list- A list in which each node consists of INFO, BACK AND FORW fields. BACK points to
the proceeding node and FORW points to the next node in the list to the current node. 9. A node in a two-way list is divided into three fields; INFO that contains the data part of the node,
FORW that contains the location of the next node and BACK that contains the location of the

3.14 Answers to check your progress/self assessment questions preceding node. Two-way list can be traversed in both directions; forward direction from the first
node to the last node and backward direction from the last node to the first node because it allows
1. Linked list or singly list is a linear data structure consisting of a group of elements called nodes which
you to access both the next and the preceding nodes to the current node.
together represent a linear sequence. Memory is allocated to these nodes in non-contiguous manner.
Each node in linked list is composed of a data called info part and a reference called link to the next
node in the sequence. 10.
a. Grounded header list- It is one in which the LINK part of the last node contains NULL value.

2. Memory allocated to array elements is contiguous and memory allocated to nodes of the linked list b. Circular header list- It is one in which the LINK part of the last node contains location or address of

is non-contiguous. It is costly and time consuming to perform insert and delete operation on array as the first node in the list.

compared to linked list.

11. a.

3. When traversing a linked list, if the value of LINK[PTR] ( where PTR is pointing to the current node) 12. b.

is NULL, it means you have reached the last node in the list.

47 48
3.15 References/ Suggested Readings Structure of the lesson
1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill 4.0 Objective
2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage. 4.1 Introduction
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education. 4.2 Definition of Stack
4.3 Applications of stacks
3.16 Model questions 4.4 Array representation of stacks
1. Write algorithm to delete a node from linked list. Also explain the same with the help of an example. 4.5 Linked representation of stacks
2. Define linked list. What are its advantages and disadvantages? 4.6 Polish notation and stacks
3. Explain two-way list with the help of a neat diagram. How can we delete a node from a two-way list? 4.7 Converting infix expression to postfix expression
4. Write algorithm to traverse circular header linked list. 4.8 Evaluating postfix notation
5. What do we mean by garbage collection? How it is done by operating system and how can it be done 4.9 Recursion
by the programmer? 4.10 Queues
4.11 Array representation of queue
4.12 Deque
4.13 Priority queue
4.14 Linked representation of priority queue
4.15 2-D array representation of priority queue
4.16 Summary
4.17 Glossary
4.18 Answers to check your progress/self assessment questions
4.19 References/ Suggested Readings
4.20 Model questions

4.0 Objective
After Studying this lesson, students will be able to:
1. Identify and define the linear data structure called stack.
2. Identify and define the linear data structure called Queue.
3. Discuss various applications of queue and stack data structures.
4. Explain the array and linked representation of both stack and queue data structures.
5. Evaluate arithmetic expressions using stacks.
6. Explain algorithms for basic operations on stack and queue data structures.

4.1 Introduction
In this lesson we will study two linear data structures which are insertion and deletion restricted. We
will also see the various applications of both these data structures. Also, stacks and queues can be
implemented in memory using either of two primary data structures; arrays or linked list. Stacks are
Lesson- 4 Stacks and Queues extremely important data structure in the field of computer science and lots of internal operations of

49 50

computer systems are performed using stacks. In this lesson we will also study the algorithms to insert
and delete elements in both these data structures.

4.2 Definition of Stack

A stack is liner data structure in which elements can be inserted and deleted at one end only, called the
top of the stack. Stack is LIFO structure in which the last element to be inserted in the list is the first
element to be removed from the list.

Basically two operations are allowed on the stack:

1. Push operation- the operation to insert element into the stack.
2. Pop operation- the operation to delete element from the stack.
Figure 4.1 (b) Stack in upper memory
Let us consider that following element are pushed onto an empty stack in order: Red,
green, yellow, purple, white 4.3 Applications of stacks
Following are some of the applications of stacks:
White is the last element to be inserted onto the stack, and hence it is the element on top of the stack. 1. Stacks are used to implement recursive function calls.
Whenever pop operation is performed, the first element to be deleted from the stack will be white. 2. Evaluation of expressions in polish notation is done using stacks.
The stack can be stored in memory using following two methodologies: 3. Solution to the problem of tower of Hanoi is possible only with the help of stacks.
1. Stack in lower memory 4. Implementation of quick sort algorithm.
2. Stack in upper memory
4.4 Array representation of stacks
There are multiple ways to represent a stack in memory of which linear array is the easiest and most
efficient one. If not specified explicitly, stacks are maintained in memory using linear single
dimensional array STACK.

The dimension or size of the stack is represented using a variable called MAXSTK, i.e. the maximum
number of elements that can be stored in a STACK. Another variable called TOP indicates the total
number of element currently stored in the STACK and it points to the element on top of the stack.

Let is consider the following example,

Figure 4.1 (a) Stack in lower memory

51 52
 ALGORITHM POP (STACK, TOP, ITEM) STACK is a linear array. TOP points to the top
most element in the STACK. Algorithm assigns the deleted element to ITEM.
1. if TOP = 0, then [underflow condition] Display: underflow and exit.
[end of if]
2. Set ITEM = STACK[TOP] [assign PUSH TOP element to ITEM]
3. Set TOP = TOP -1 [decrement value of TOP by 1]
4. Exit

4.5 Linked representation of stacks

The push and pop operation are performed at the beginning of the list. TOP points to the first node in
the list and it is where push and pop operation are performed. Each node consists of two fields; INFO
and LINK.
Figure 4.2 Array representation of stack. Let us consider a stack with three elements pushed in the order:
C, B, A.
The STACK in figure 4.2 has 4 elements. The value of variable TOP is 4 and it is pointing to 21. The
dimension or size of the STACK is MAXSTK =8. There is a possibility of pushing 4 elements onto the
STACK and also popping 4 elements from the STACK.
Figure 4.3 Linked representation of Stack with three elements

The condition “TOP=MAXSTK” indicates that the STACK is full and no more elements can be pushed
Let us consider that we want to push an element “D” onto the stack. First of all we need to check if
onto the STACK and the condition “TOP = NULL OR 0” indicates that the STACK is empty and op
there is space available in AVAIL list or not and if yes, then assign the first unused node to NEW.
operation cannot be performed on it.

EXERCISE 1
Collect images of at least 5 real life examples where we create stacks of
various objects. For example stack of books, crockery, etc.

ALGORITHM PUSH (STACK, MAXSTK, TOP, ITEM) STACK is a linear array with Figure 4.4 Assigning first free node to NEW pointer.
maximum capacity of MAXSTK locations. TOP points to the top most element in the STACK
and ITEM is the element to be inserted onto it.
1. if TOP = MAXSTK, then [overflow condition] Display: Overflow and exit.
PUSH_LINK (INFO, LINK, TOP, AVAIL, ITEM) the algorithm pushes ITEM into the
[end of if]
linked list
2. Set TOP = TOP + 1 [Increment value of TOP by 1]
3. Set STACK[TOP] = ITEM [PUSH ITEM on TOP of STACK] 1. if AVAIL = NULL then, Display: OVERFLOW and exit.
4. Exit 2. [Assign node from free pool list to NEW] Set NEW = AVAIL

3. [Assign second node in the free pool list to AVAIL] AVAIL = LINK[AVAIL].

53 54

4. Set INFO[NEW] = ITEM. [Copy ITEM to NEW] ____________________________________________________________________________

5. Set LINK[New] = TOP [New node now points to TOP node] ___________________________________________________________________________

____________________________________________________________________________
6. Set TOP = NEW. [TOP is reset to NEW node]
Q2. List various applications of stack.
7. Exit. ____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Q3 How can we represent stack in memory?

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

4.6 Polish notation and stacks

Figure 4.5 Pushing new node to the TOP of linked stack.
Basically the arithmetic expressions are written in the form in which the operators come in-between the
The pop operation can be similarly performed by simply removing the first node from stack and adding two operands. For example,
the same to the AVAIL list.
a + b
POP_LINK (INFO, LINK, TOP, AVAIL, ITEM) The algorithm deletes the TOP element in
the linked STACK and assigns it to ITEM.
This type of expression is called infix expression. Computer science algorithms do not evaluate
1. if TOP = NULL, then
arithmetic expression directly that is written in infix notation. It is because of the different levels
Display: underflow and exit.
precedence between the operators. Let us consider the precedence of most basic five binary operators.
2. Set ITEM = INFO[TOP] [copy the TOP element to ITEM]
3. Set TEMP = TOP and TOP = LINK[TOP] [saves the location of deleted node to TEMP]
^ exponential highest precedence
4. Set LINK[TEMP] = AVAIL and AVAIL = TEMP [add the deleted node to AVAIL list] 5.
*, / multiply and divide next highest precedence
EXIT
+, - add and subtract lowest precedence

The sub expressions written in parenthesis are evaluated before the other expressions, plus the
operations on the same level are performed from left to right. These expressions written in infix notation
can be easily evaluated with the help of stacks by converting these expressions to either of the following
two forms and then evaluating them:
Figure 4.6 Popping TOP node of linked stack.

Check your progress/ Self assessment questions Polish notation or prefix expression: It is one in which the operator comes before the two operands.
For example,
Q1. Define stack data structure.

55 56
 + a b Step-1 Push “(“left parenthesis onto stack and “)” right parenthesis to the end of expression L.

Reverse-polish notation or postfix expression: It is one in which the operator comes after the two STACK: (
operands. For example,
Expression: 12 * ( 4 + 6 ) )
a b +
Step-2 Scan each element of expression L and act as per the algorithm given above until the STACK is
4.7 Converting infix expression to postfix expression empty.

IN_TO_POST (L, P) the algorithm coverts an infix expression L to its equivalent postfix Symbol scanned Status of STACK Expression P
expression P. (
1. Push “(“ left parenthesis onto stack and “)” right parenthesis to the end of expression L. 2.
12 ( 12
Scan L from left to right and repeat step 3 for each element of L

until the stack is empty. * (* 12

3. If the scanned element is:
( (*( 12
(a) an operand, then simply add the same to P.

(b) a left parenthesis, then simply push the same onto stack.
4 (*( 12, 4
(c) an operator, then:

(i) Pop from stack and add to P each operator which has same or + (*(+ 12, 4
higher precedence then the scanned operator.

(ii) Add newly scanned operator to stack. 6 (*(+ 12, 4, 6

(d) a right parenthesis, then:

) (* 12, 4, 6, +
(i) Pop from stack and add to P each operator until a left parenthesis
is encountered.
) 12, 4, 6, +, *
(ii) Remove the left parenthesis from the stack.

[End of step 3 If]

[End of step 2 Loop] 4.8 Evaluating postfix notation \

4. Exit.
EVA_POST (P, RESULT) the algorithm evaluated the postfix expression P and assigns
the value to variable RESULT
Consider the following infix expression L
1. Add “)” right parenthesis at the end of P.

Expression: 12 * ( 4 + 6 ) 2. Scan P from left to right and repeat steps 3 & 4 for each element of P until “)” right
parenthesis is encountered.

57 58

3. If an operand is encountered, then push the same onto stack.

4. If an operator [O] is encountered, then The final value on top of the STACK is 120.

(a) Pop the top two elements from stack, assign the TOP element to X and
Check your progress/ Self assessment questions
the next element to Y.
Q4. What is an infix expression?
(b) Evaluate Y [O] A
____________________________________________________________________________
(c) Place the result of step (b) back onto stack.
___________________________________________________________________________
[End of Step 4 If] [End
____________________________________________________________________________
of step 2 For Loop]
Q5. What is a postfix expression?
5. Set RESULT equal to the value of the TOP element on the stack. ____________________________________________________________________________

6. Exit. ___________________________________________________________________________

____________________________________________________________________________
Consider the following postfix expression P
Q6. Give the order of precedence for the operators *, - , ^, +, / ?
____________________________________________________________________________
Expression: 12 4 6 + *
___________________________________________________________________________

____________________________________________________________________________
Step-1 add “)” to the end of expression P

Expression: 12 4 6 + * ) 4.9 Recursion

Recursion is a process that has a reference to itself. A recursive function is one that contains a call to
Step-2 scan each element and act as per the algorithm given above until a “)” is encountered. itself. There are number of problems in computer science for which recursive solutions can be defined,
but not for all problems. The problems for which recursive solutions exist or can be designed are
Symbol scanned Status of STACK iterative in nature.
12 5
You can give mathematical representation for every recursive function. In this section, example of
4 12, 4 recursive factorial function is taken:

6 12, 4, 6 The mathematical representation of factorial function is given as follows:

+ 12, 10

* 120
It is a recursive function because the right side of the equation contains a reference of the same function.

) There are two possible outcomes of the above mathematical equation depending on the value of n. For
n =0, the function will return 1 and for n > 0, the function places a call to itself by passing value 1 less
than n to the function.

59 60
With every recursive call, the function moves one step closer to the base value, which in case of factorial
function is 0. Once the base value is reached, the function starts to return. Stack is used to implement
the concept.

Let us see the implementation of recursive factorial function:

5! = 5 * 4 * 3 * 2 * 1 Eq-1

and

4! = 4 * 3 * 2 * 1 Eq-
2

It is can concluded from Eq-1 and Eq-2, that 5! can also be written in terms of 4! as:
5! = 4 * 4!

Similarly, 4! can be written in terms of 3!

5! = 5 *4 *3!

and 3! can be written in terms of 2!. Figure 4.7 Recursive call for factorial function.
5! = 5 *4 *3 * 2!
ALGORITHM FACTORIAL (N) Recursive algorithm to compute the factorial of N.
and 2! can be written in terms of 1!. 1. if N = 0 return 1;
5! = 5 *4 *3 * 2 * 1! [end of if]
finally 1! can be written in terms of 0! 2. return n * FACTORIAL(n-1);
4. Exit
5! = 5 *4 *3 * 2 * 1 * 0! Eq-3
4.10 Queues
From the mathematical equation of factorial function given earlier, 0! is 1. Put the value of 0! in Eq-3 Queue is yet another linear data structure in which elements are inserted at one end and deleted at other
and you will get the factorial of 5. end. Elements in queue are deleted from the beginning called the FRONT of the queue and elements in
queue are inserted at the end called the REAR of the queue. Queue is FIFO structure in which the first
element to be inserted in the list is the first element to be deleted from the list.

4.11 Array representation of queue

61 62

Two pointers are maintained to represent a queue as linear array. FRONT points to the first element in Now, that the queue is circular, we can check if the Queue is full using the following statement:
the queue and REAR points to the last element in the queue. If (FRONT = 1 and REAR = N) OR (FRONT = REAR +1)
IF either of the two conditions is true, the queue is full.
FRONT = NULL indicated that there are no elements in the queue and it is empty.
FRONT = REAR indicates that there is only one element in the queue.
FRONT = 1 AND READ = N indicates that the queue is full.

Figure 4.8 Representation of circular queue

INSERT (QUEUE, FRONT, REAR, ITEM, N) the algorithm inserts ITEM at the REAR of the QUEUE of
size N.

[Check for overflow]

Figure 4.7 Representation of simple queue 1. If ( FRONT = 1 and REAR = N ) OR ( FRONT = REAR +1 ), then Display: Overflow and exit.

[Check if QUEUE is empty]

Circular queue 2. If FRONT = NULL, then
Set FRONT = 1 and REAR = 1
Generally a Queue is always circular in nature, i.e. the last element in the queue in linked back to first Else if REAR = N
element in the queue. Set REAR =1
Else
Set REAR = REAR + 1
Delete operation is performed at the FRONT by simply incrementing the value of FRONT by 1 as [end of if]
3. Set QUEUE[REAR] = ITEM [assign ITEM to the rear of the queue]
follows: 4. Exit
FRONT = FRONT + 1
DELETE (QUEUE, FRONT, REAR, ITEM, N) the algorithm deletes the element at the
FRONT of the QUEUE of size N and assigns the same to ITEM.
In case the value of FRONT = N, then the FRONT is repositioned to the start of the queue as:
[Check for underflow]
FRONT =1. 1. If FRONT = NULL, then
Display: Underflow and exit.
Similarly, insert operation is performed at the REAR by simply incrementing the value of REAR by 1
[Check if QUEUE is empty]
as follows: 2. Set ITEM = QUEUE[FRONT] [assign element at front of queue to ITEM]
REAR = REAR + 1
3. If FRONT = REAR, then [only one item in the queue] Set FRONT = NULL and REAR =
NULL
In case the value of REAR = N, then the REAR is repositioned to the start of the queue as: Else if FRONT = N
Set FRONT =1
REAR =1.
Else

63 64
 Set FRONT = FRONT + 1 as circular queue with its own FRONT and REAR pointers that can be maintained using two linear
[end of if] arrays of size equal to the number of priority levels.
4. Exit
FRONT[5] and REAR[5] represents the front and rear element of row 5 in the 2-D array, i.e. the queue
4.12 Deque for priority level 5.
Deque is also known as double-ended queue. It is linear data structure in which the elements can be For example,
inserted or deleted at either end of the queue, but not from the middle of the queue. Instead of FRONT
and REAR, LEFT and RIGHT points to the two ends of the deque represented as circular array.

Deque comes with two variations called the insertion restricted deque and deletion restricted deque.
In insertion restricted deque; insertion is permitted at only end where as delete operation is permitted to
both ends and in deletion restricted deque; insertion is permitted at both ends where as delete operation
is permitted at one end only.

4.13 Priority queue

Fig 4.10 2-D array representation of priority queue
Priority queue is a special queue in which each element in queue is stored along with its priority that
decides the order in which the element is inserted and deleted from the queue. Following two rules are
Check your progress/ Self assessment questions
followed while processing elements in priority queue:
Q7. Define queue. What do we mean by circular queue and how to check if the circular queue is full or
1. Elements with higher priority are processed or deleted from the queue before the elements with the
not?
lesser priority. ____________________________________________________________________________
2. Elements with same priority are processed in order of their arrival.
___________________________________________________________________________
The priority queue may be represented in memory using either of two methods:
____________________________________________________________________________

4.14 Linked representation of priority queue Q8. Define deque. Discuss insertion restricted and deletion restricted deques?
____________________________________________________________________________
Every node in list representation of priority queue consists of three fields; INFO the data part of the
node, PRN the priority of element and LINK the link to the next node. A node A comes before node B ___________________________________________________________________________
in case node A has higher priority than node B or in case two nodes have same priority and node A was ____________________________________________________________________________

inserted to list before node B. Q9. What is priority queue? How can we maintain priority queue in memory using 2-D array?
____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Fig 4.9 Linked representation of priority queue

10. Which of the following does not relate to stacks?
4.15 2-D array representation of priority queue a. FIFO list
Priority queue can also be represented in memory using different queue for each level of priority using b. LIFO list
2-D array. Each row in 2-D array represents a queue for one level of priority. Each row is represented c. PUSH and POP operations

65 66

d. TOP element Queue- Queue is a linear data structure in which elements are deleted from FRONT of the queue and
inserted at the REAR of the queue.
11. The term "push" and "pop" is related to the Priority queue- It is a special queue in which each element in queue is stored along with its priority that
a. array decides the order in which the element is inserted and delete from the queue.
b. lists Deque- It is linear data structure in which the elements can be inserted or deleted at either end of the
c. stacks queue, but not from the middle of the queue.
d. all of above
4.18 Answers to check your progress/self assessment questions
12. A data structure where elements can be added or removed at either end but not in the middle a. 1. A stack is liner data structure in which elements can be inserted and deleted at one end only, called
Linked lists the top of the stack. Stack is LIFO structure in which the last element to be inserted in the list is the
b. Stacks first element to be removed from the list.
c. Queues
d. Deque 2. Following are some of the applications of stacks:

4.16 Summary  Stacks are used to implement recursive function calls.

A stack is linear data structure in which elements can be inserted and deleted at one end only, called the  Evaluation of expressions in polish notation is done using stacks.
top of the stack. Stack is LIFO structure in which the last element to be inserted in the list is the first  Solution to the problem of tower of Hanoi is possible only with the help of stacks.
element to be removed from the list. Push operation inserts element onto the stack and Pop operation  Implementation of quick sort algorithm.
deletes element from the stack. Stacks are used to implement recursive function calls, evaluation of
expressions in polish notation, Solve the problem of tower of Hanoi and implementation of quick sort 3. We can represent stack in memory either using a linear array or linked list. The dimension or size of
algorithm. Infix notation is the form in which the operators come in-between the two operands, polish the stack using linear array is represented using a variable called MAXSTK and TOP indicates the
notation is one in which the operator comes before the two operands and reversepolish notation is one total number of element currently stored in the STACK and it points to the element on top of the
in which the operator comes after the two operands. stack. In case of linked list, TOP points to the first node in the list and it is where push and pop
operation are performed. Each node consists of two fields; INFO and LINK.
Queue is a linear data structure in which elements are deleted from the beginning called the FRONT of
the queue and elements in queue are deleted from the end called the REAR of the queue. Queue is FIFO 4. Infix expression is an arithmetic expression that is written in the form in which the operators come

structure in which the first element to be inserted in the list is the first element to be deleted from the in-between the two operands.

list. A circular queue is one in which the last element in the queue in linked back to first element in the For example, x + y

queue.
4.17 Glossary 5. Postfix expression is one in which the operator comes after the two operands.

TOP- Elements can be inserted and deleted in stack at one end only, called the top of the stack. Stack- For example, a b +

Stack is LIFO structure in which the last element to be inserted in the list is the first element to be
removed from the list. 6. The order of precedence:

FRONT- The end of queue data structure at which deletion takes place. ^ exponential highest precedence

REAR- The end of queue data structure at which insertion takes place. *, / multiply and divide next highest precedence

Circular queue- Queue data structure in which the last element is linked to the first element in the queue. +, - add and subtract lowest precedence

67 68
7. Queue is a linear data structure in which elements are deleted from the beginning called the FRONT
of the queue and elements in queue are deleted from the end called the REAR of the queue. Queue is
FIFO structure in which the first element to be inserted in the list is the first element to be deleted
from the list.
A circular queue is one in which the last element in the queue in linked back to first element in the
queue. We can check if the queue is full using the following condition:
If (FRONT = 1 and REAR = N) OR (FRONT = REAR +1)

8. Deque is a linear data structure in which the elements can be inserted or deleted at either end of
the queue. LEFT and RIGHT points to the two ends of the deque represented as circular array. In
insertion restricted deque; insertion is permitted at only end where as delete operation is permitted to
both ends and in deletion restricted deque; insertion is permitted at both ends where as delete operation
is permitted at one end only.

9. Priority queue is a special queue in which each element in queue is stored along with its priority
that decides the order in which the element is inserted and delete from the queue. Priority queue can be
represented in memory using different queue for each level of priority using 2-D array. Each row in 2-
D array represents a queue for one level of priority. Each row is represented as circular queue with its
own FRONT and REAR pointers that can be maintained using two linear arrays of size equal to the
number of priority levels.

11. a.
12. c.
13. d

4.19 References/ Suggested Readings Lesson- 5 Introduction to Trees

1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill Structure of the lesson
2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage 5.0 Objective
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education. 5.1 Introduction
5.2 Binary tree
4.20 Model questions 5.2.1 Tree Terminologies
1. Write algorithm to convert infix expression to postfix expression. 5.2.2 Type of binary trees
2. Write algorithm to perform push operation on linked stack. 5.3 Memory representation of binary tree
3. Write algorithm to evaluate postfix expression. 5.3.1 Sequential or array representation of trees
4. What we mean by circular queue? Write algorithm to delete element from circular queue. 5.3.2 Linked representation of binary trees
5. Explain In detail the two methods of representing priority queue in memory. 5.4 Summary
5.5 Glossary

69 70

5.6 Answers to check your progress/self assessment questions

5.7 References/ Suggested Readings The tree in figure 5.1 consists of 13 nodes. The root node the tree T is “8”. The left successor or child
5.8 Model questions of root node is “3” and the right successor or right child of root node is “9”. The binary tree can
recursively be looked as collection of many sub-trees with the left and right successors of the root node
5.0 Objective acting as root nodes of left and right sub-trees.
After studying this lesson, students will be able to:
1. Define tree data structure.
2. Represent mathematical expressions in terms of binary trees.
3. Explain different terminologies associated with the binary tree data structure.
4. Identify types of binary trees.
5. Discuss array and linked representation of tree in memory

5.1 Introduction
So far we have discussed only linear data structures in this book. In this lesson you will be introduced
to the most important non-linear data structure called tree. Trees are used in various domains of
computer science. Trees are basically used to represent the hierarchical relationship among elements.
The most basic type of tree that you will study in this lesson is binary tree. Often we need describe a
group of real life objects that have hierarchical relation to one another and they cannot be described
using linear data structures.

Figure 5.2 Recursive representation of tree

5.2 Binary tree
A binary tree T is defined as collection of elements called nodes, such that T is either an empty tree or
T contains a distinguished node R called the root node and the remaining nodes of T form the two As you can see in the last figure, the root R of the binary tree T is divided into two sub-trees called the
disjoint binary tree LT1 and RT2 called the left sub-tree and the rights sub-tree. left sub-tree and the right sub-tree. The left successor or left child of the root node is the root of the left
sub-tree and right successor or right child of the root node is the root of the right sub-tree.

For example, We can represent any mathematical or algebraic expression in form of a tree. Consider
the following mathematical expression:
X = ( A * B + C) / (D / E – F )
X can be represented in terms of binary tree as follows:

Figure 5.1 Binary Tree

71 72
 ____________________________________________________________________________

Q3. What is a root node and why the left and right child of root are called root of left and root of right
sub-tree respectively?
____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

5.2.1 Tree Terminologies

1. Root is called the node without parent. For example,

Figure 5.3 Tree representation of mathematical expression X = ( A * B + C) / (D / E – F )

Another example,
X = (A + B) ^ 2 + C
X can be represented in terms of binary tree as follows:

Figure 5.5 Root node of the tree

In the figure above, "-" is the root node.

2. Leaf node is a node without child nodes. For example,

Figure 5.4 Tree representation of mathematical expression X = (A + B) ^ 2 + C

Check your progress/ Self assessment questions

Q1. Define binary tree.

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________
Figure 5.6 Leaf nodes the tree
In the figure above, "A", "B" and "D" are leaf nodes.
Q2. Show the binary tree for mathematical expression (A + B ) - D?
____________________________________________________________________________

___________________________________________________________________________

73 74

3. Internal nodes are the nodes, which are neither leaf or root. These are the nodes which have parent
and at least one child. For example,

Figure 5.9 Example of path length between two nodes

Figure 5.7 Internal nodes the tree
In the figure above, "+" is the internal node.
Path length of path from node "-" to "B" is 2.

4. Path is called a sequence of connected nodes. There can be more than one path in a tree. For example,
6. Level Each node in a binary tree T is assigned a level number staring from the root R which is
assigned the level number 0. The children of the root R are assigned level 1. In other words each node
is assigned a level number 1 more than the level number of its parent.

Figure 5.8 Example of path between two nodes

Figure 5.10 Levels of a tree

In the figure above, there is a path from node "-" to node "B" ("-" ----> "+" ----> "B").

7. Height or depth of a binary tree T is the maximum number of nodes in a branch of T. Branch refers
5. Path length is the number of edges connecting the sequence of nodes in that very path. Path length
to a path that ends at the leaf node from the root R. Depth is always 1 more than the largest level of
is one less than the number of nodes in the path. For example,
the tree.

75 76
 For example, The parent of node 11 = int(11 / 2) = 5

Extended binary tree

Extended tree is also called 2-tree. A binary tree T is said to be an extended binary tree if and only if
each node N of the binary tree has either 0 or 2 children. It may be possible that it is not filled to its
fullest. The nodes with two children are called internal nodes (denoted with circle), and the nodes with
0 children are called external nodes (denoted with square).

Figure 5.11 Height of a tree

5.2.2 Type of binary trees

Complete Binary Tree

We call a binary tree T to be complete if it is filled to the fullest. A binary tree T is a complete tree if it
has the maximum possible nodes at all its levels, except possibly the last, also all the nodes at the last
level are as far left as possible.

The array representation of a complete tree has no blank entries in between as it is filled to the fullest
and starting from the left.
Figure 5.13 Extended Tree

Check your progress/ Self assessment questions

Q4. Define height of the tree.

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Q5. Explain complete binary tree.

____________________________________________________________________________

Figure 5.12 Complete Tree ___________________________________________________________________________

____________________________________________________________________________
Because all levels except the last level are filled to the fullest, it is easy to compute the address of
Q6. Differentiate between internal and leaf nodes.
the parent node for any given node using array memory representation. The address of parent ____________________________________________________________________________
node of k can be computed as int(k / 2).
___________________________________________________________________________
____________________________________________________________________________

77 78

5.3 Memory representation of binary tree

There are two methods of representing binary trees in memory:
 array representation and
 linked representation

5.3.1 Sequential or array representation of trees

Array representation is very straightforward technique. For every node in the tree, the location of its
children and parent in the array is computed using a formulae.

Parent of node N = int ( N / 2 )

Left child of node N = N * 2
Right child of node N = ( N * 2 ) + 1

where K is the location of any node in the array.

Figure 5.15 Array representation of binary tree

You can see in the figure above that entry at location number 6 is empty. This location is for the left
child of the node stored at location 3, which is "H". As you can see in figure 5.14, there is no left child
of node "H". This location is reserved for its left child and is not assigned to any other node. Whenever
a left child for the node "H" is inserted, it will be stored at location 6. Similarly you can see that many
more entries at different locations in the array are empty.

5.3.2 Linked representation of binary trees

Another logical representation of binary tree in memory is called linked representation based on linked
Figure 5.14 Binary tree
list data structure. Linked representation of binary tree can be also be maintained in memory with the
help of arrays for physical storage of its locations in memory. A binary tree T is maintained in memory
The root R node of the binary tree is always stored at location 1 in the array. So "F" is stored location
by means of linked representation that uses a 2-D array with columns, each representing INFO, LEFT,
1. Now the left child of root node "G" is stored at location 2 which is (1 * 2) and, The right child of root
and RIGHT respectively.
node "H" is stored at location 3 which is (1 * 2) + 1.

(1) INFO[K] contains the data stored at node N.

Following is the array representation of binary tree in figure 5.14.
(2) LEFT[K] contains the location of the left child of node N.
(3) RIGHT[K] contains the location of the right child of node N.

A special pointer ROOT is used to maintain the address of the root node R of the binary tree. If the
ROOT contains NULL, it means that the tree is empty.

79 80
If for any node, it does not have a left, right or both children, the LEFT [K], RIGHT [K] or both will
contain NULL value respectively.

Consider the following binary tree:

Figure 5.17 2-D array showing physical representation of binary tree in memory

Check your progress/ Self assessment questions

Figure 5.16 Linked representation of binary tree Q7. Write the formulae's to compute the location for parent, left child and right child nodes for any node
N.
____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Q8. Explain linked representation of binary tree in memory.

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Q9. Why some of the entries at different locations empty when using sequential representation to store
binary trees in memory?
____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

5.4 Summary

81 82

A binary tree T is defined as collection of element called nodes, such that T is either an empty tree or T 5.6 Answers to check your progress/self assessment questions
contains a distinguished node R called the root node and the remaining nodes of T form the two disjoint 1. A binary tree T is defined as collection of element called nodes, such that T is either an empty tree or
binary tree LT1 and RT2 called the left sub-tree and the rights sub-tree. Mathematical or algebraic T contains a distinguished node R called the root node and the remaining nodes of T form the two
expressions can be represented in form of a binary tree that shows the order of execution. disjoint binary trees LT1 and RT2 called the left sub-tree and the rights sub-tree.

A binary tree T is a complete tree if it has the maximum possible nodes at all its levels, except possibly 2.
the last, also all the nodes at the last level are as far left as possible. Extended tree is also called 2-tree.
A binary tree T is said to be an extended binary tree if and only if each node N of the binary tree has
either 0 or 2 children.
There are two methods of representing binary trees in memory:
 array representation and
 linked representation
Array representation is very straightforward technique. For every node in the tree, the location of its
children and parent in the array is computed using a formulae.

Parent of node N = int ( N / 2 ) 3. Root node is the first node or node on top of the tree. If there is no root node, tree is called empty

Left child of node N = N * 2 tree. Left and right child of root node are called root of left and root of right sub-tree because the tree

Right child of node N = ( N * 2 ) + 1 is recursive in nature. The left child of root node is virtually the root of all nodes on the left of root
node and right child of root node is virtually the root of all nodes on the right of root node.
A binary tree T is maintained in memory by means of linked representation that uses a 2-D array with 4. Height of a binary tree T is the maximum number of nodes in a branch of T. Branch refers to a path
columns, each representing INFO, LEFT, and RIGHT respectively. that ends at the leaf node from the root R. Height is always 1 more than the largest level of the tree.

(1) INFO[K] contains the data stored at node N.

(2) LEFT[K] contains the location of the left child of node N. 5. Binary tree T is a complete tree if it is filled to the fullest and it has the maximum possible nodes at

(3) RIGHT[K] contains the location of the right child of node N. all its levels, except possibly the last where all the nodes are as far left as possible. The array

A special pointer ROOT is used to maintain the address of the root node R of the binary tree. representation of a complete tree has no blank entries in between as it is filled to the fullest and
starting from the left.

5.5 Glossary
Binary Tree is either an empty tree or contains a distinguished node R called the root node and the 6. Leaf node is a node without child nodes and Internal node is a node which are neither leaf or root.

remaining nodes of T form the two disjoint binary tree LT1 and RT2 called the left sub-tree and the rights These are the nodes which have parent and at least one child.

sub-tree.
Root node is the node without parent. 7. Parent of node N = int ( N / 2 )

Leaf node is a node without child nodes. Left child of node N = N * 2

Internal nodes are the nodes that are neither leaf or root. Right child of node N = ( N * 2 ) + 1

Path is called a sequence of connected nodes.

Path length is the number of edges connecting the sequence of nodes in that very path. 8. A binary tree T is maintained in memory by means of linked representation that uses a 2-D array with

Height or depth is the maximum number of nodes in a branch of T. columns, each representing INFO, LEFT, and RIGHT respectively.

83 84
(1) INFO[K] contains the data stored at node N.
(2) LEFT[K] contains the location of the left child of node N. Lesson- 6 Traversing binary tree

(3) RIGHT[K] contains the location of the right child of node N. Structure of the lesson
6.0 Objective

9. There are empty entries at certain locations in the array to show that some nodes do not have left, 6.1 Introduction

right, or both children Whenever the child for the said node " is inserted, it is stored at the same location 6.2 Traversing a binary tree

which is reserved for it. 6.2.1 Preorder traversal:

6.2.2 Inorder traversal:

5.7 References/ Suggested Readings 6.2.3 Postorder traversal:

1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill. 6.3 Summary

2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage. 6.4 Glossary

3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education. 6.5 Answers to check your progress/self assessment questions
6.6 References/ Suggested Readings

5.8 Model questions 6.7 Model questions

1. Create binary tree for the following mathematical expression:

A * B + (C - D) / E 6.0 Objective

2. Explain the sequential representation of binary tree in memory with the help of an example. After Studying this lesson, students will be able to:

3. What is a complete binary tree? 1. Define different methods available for traversal of binary trees.

4. Explain the linked representation of binary tree in memory with the help of an example. 2. Explain the role of stacks in implementation of binary tree traversal algorithms.
3. Explain recursive and non-recursive algorithms for implementing each method of binary tree
5. Explain following terms with the help of an example:
traversal.
a) DEPTH OF TREE
4. Re-create original tree when the order of traversal is given using different binary tree traversal
b) LEAF NODES
methods.
c) PATH

6.1 Introduction
Traversal of tree data structure is complicated as it is a non-linear data structure. Each node in a binary
tree may further be divided into two sub-trees called the left sub-tree and right sub-tree. Challenge lies
in the fact that we need to process each node exactly once. There are three popular methods of traversing
binary tree called Pre-order traversal, In-order traversal and Post-order traversal. These are discussed in
great detail later in this lesson. Stack plays a significant role in implementing all the three methods,
whether using recursive or non-recursive algorithms.

6.2 Traversing a binary tree

Traversing a binary tree means to visit each node of the binary tree exactly once. Consider the following
binary tree to be traversed.

85 86

PREORD(INFO, ROOT) the algorithm performs preorder traversal on binary tree T and
applies an operation PROCESS to each node of T. An array STACK is used to
temporarily store the locations of nodes)

[push NULL onto STACK, and initialize PTR with ROOT]

1. Set TOP = 1, STACK[1] = NULL and PTR = ROOT

2. Repeat Steps 3 to 5 while PTR != NULL

3. Apply PROCESS to INFO[PTR]

[check if the right child exists]

4. if RIGHT[PTR] != NULL, then [push the right child onto stack]

Figure 6.1 Simple binary tree Set TOP = TOP + 1 and STACK[TOP] = RIGHT[PTR]

[End of If]
Traversing of the binary tree can be implemented using following methods:
[check if the right child exists]
5. If LEFT[PTR] != NULL, then
6.2.1 Preorder traversal:
Preorder traversal of the binary tree can be carried-out by following the sequence as given below: a. Set PTR = LEFT[PTR] [move to the left child]

Visit the root. else: [Pop from STACK.]

b. Traverse the left sub-tree.
Set PTR = STACK[TOP] and TOP = TOP - 1
c. Traverse the right sub-tree
[End of If]
[End of Step 2 loop]
Order of processing for binary tree in figure 6.1: 2, 7, 2, 6, 5, 11, 5, 9, 4 Recursive
Algorithm 6. Exit.

For example, consider the binary tree given in figure 6.1.

R_PREORD(INFO, ROOT) the algorithm performs preorder traversal on non-empty
binary tree T and apply an operation PROCESS to each node of T. An array STACK is
used to temporarily store the locations of nodes)

[initialize PTR with ROOT]

1. Set PTR = ROOT

2. Apply PROCESS to INFO[PTR]

[apply R_PREORD to left sub-tree]

3. R_PREORD (INFO, LEFT[PTR])

[apply R_PREORD to RIGHT sub-tree]

4. R_PREORD (INFO, RIGHT[PTR])

5. Exit.

Non-recursive Algorithm
1. Push Φ onto STACK and,

87 88
 Process 9,
Set PTR = 2. Set PTR = 4.
STACK Φ STACK Φ

2. Process 2, 10. Process 4,

Push right child of 2, i.e. 5 onto STACK and,
Pop Φ from STACK and set PTR = Φ
Set PTR = 7.
STACK Φ 5 Check your progress/ Self assessment questions

Q1. Why the traversing of binary tree is difficult task as compared to data structures like array, linked
3. Process 7, list, stack and queues?
Push right child of 7, i.e. 6 onto STACK and, ____________________________________________________________________________

Set PTR = 2. ___________________________________________________________________________

STACK Φ 5 6
____________________________________________________________________________

4. Process 2, Q2. Name the three techniques used to traverse the binary sub-tree.
____________________________________________________________________________
STACK Φ 5 6
___________________________________________________________________________
5. Pop 6 from STACK
____________________________________________________________________________
Process 6,
Q3. Define Preorder traversal of binary tree.
Push right child of 6, i.e. 11 onto STACK and,
____________________________________________________________________________
Set PTR = 5.
___________________________________________________________________________
STACK Φ 5 11
____________________________________________________________________________
6. Process 5,
STACK Φ 5 11
6.2.2 Inorder traversal:
Inorder traversal of the binary tree can be carried-out by following the sequence as given below: a.
7. Pop 11 from STACK
Traverse the left sub-tree.
Process 11,
b. Visit the root.
STACK Φ 5
c. Traverse the right sub-tree.

8. Pop 5 from STACK

Order of processing for binary tree in figure 6.1: 2, 7, 5, 6, 11, 2, 5, 4, 9 Recursive
Process 5,
Algorithm
STACK Φ 5
Push right child of 5, i.e. 9 onto STACK
R_INORD(INFO, ROOT) the algorithm performs Inorder traversal on non-empty binary
STACK Φ 9 tree T and apply an operation PROCESS to each node of T. An array STACK is used to
temporarily store the locations of nodes)
9. Pop 9 from STACK [initialize PTR with ROOT]

89 90

1. Set PTR = ROOT For example, consider the binary tree given in figure 6.1.

[apply R_INORD to left sub-tree]

2. R_INORD (INFO, LEFT[PTR])

3. Apply PROCESS to INFO[PTR]

[apply R_INORD to RIGHT sub-tree]

4. R_INORD (INFO, RIGHT[PTR])

5. Exit.

Non-recursive Algorithm
INORD(INFO, ROOT) the algorithm performs Inorder traversal on binary tree T and apply
an operation PROCESS to each node of T. An array STACK is used to temporarily store
the locations of nodes)

[push NULL onto STACK, and initialize PTR with ROOT]

1. Set TOP = 1, STACK[1] = NULL and PTR = ROOT

[push the left most path onto stack]

2. Repeat Steps 3 and 4 while PTR != NULL
1. Push Φ onto STACK and,
3. Set TOP = TOP + 1 and STACK[TOP] = PTR Set PTR = 2.
4. Set PTR = LEFT[PTR] [ move to left child] STACK Φ

[end of loop]
2. Move to the left most path starting from root node and push all elements onto the stack
[pop the top element of the stack] STACK Φ 2 7 2
5. Set PTR = STACK[TOP] and TOP = TOP - 1

[backtrack] 3. Backtrack and pop nodes one by one from the stack and process them till you find a node that
6. Repeat Steps 7 to 9 while PTR != NULL has right child, in this case we will pop 2 and 7.

7. Apply PROCESS to INFO[PTR]

Process 2, 7
[check if the right child exists] Set PTR = 6, the right child of 7
8. if RIGHT[PTR] != NULL, then
STACK Φ 2
8.a Set PTR = RIGHT[PTR]
8.b goto step 2
4. Move to the left most path starting from node 6 and push all elements onto the stack
[End of If]
STACK Φ 2 6 5
9. Set PTR = STACK[TOP] AND TOP = TOP – 1 [perform pop operation]

[end of step 6 loop] 5. Backtrack and pop nodes one by one from the stack and process them till you find a node that
has right child, in this case we will pop 5 and 6.
10. Exit.

91 92
 Process 5, 6 Postorder traversal of the binary tree can be carried-out by following the sequence as given below: a.
Set PTR = 11, the right child of 6 Traverse the left sub-tree.
STACK Φ 2 b. Traverse the right sub-tree.
c. Visit the root.
6. Since node 11 does not have a left child, push 11 to stack
STACK Φ 2 11 Order of processing for binary tree in figure 6.1: 2, 5, 11, 6, 7, 4, 9, 5, 2

7. Backtrack and pop nodes one by one from the stack and process them till you find a node that Recursive Algorithm
has right child, in this case we will pop 11, 2 R_POSTORD(INFO, ROOT) the algorithm performs Postorder traversal on non-empty
binary tree T and apply an operation PROCESS to each node of T. An array STACK is
used to temporarily store the locations of nodes)
Process 11, 2
Set PTR = 5, the right child of 2 [initialize PTR with ROOT]
1. Set PTR = ROOT
STACK Φ
[apply R_POSTORD to left sub-tree]
2. R_POSTORD (INFO, LEFT[PTR])
8. Since node 5 does not have a left child, push 5 to stack
[apply R_POSTORD to RIGHT sub-tree]
STACK Φ 5 3. R_POSTORD (INFO, RIGHT[PTR])

4. Apply PROCESS to INFO[PTR]

9. Backtrack and pop nodes one by one from the stack and process them till you find a node that
5. Exit.
has right child, in this case we will pop 5

Non-recursive Algorithm
Process 5
POSTORD(INFO, ROOT) the algorithm performs Postorder traversal on binary tree T
Set PTR = 9, the right child of 5 and applies an operation PROCESS to each node of T. An array STACK is used to
temporarily store the locations of nodes)
STACK Φ
[push NULL onto STACK, and initialize PTR with ROOT]
10. Move to the left most path starting from node 9 and push all elements onto the stack 1. Set TOP = 1, STACK[1] = NULL and PTR = ROOT

[push the left most path onto stack]

STACK Φ 9 4 2. Repeat Steps 3 to 5 while PTR != NULL

3. Set TOP = TOP + 1 and STACK[TOP] = PTR

11. Backtrack and pop nodes one by one from the stack and process them till you find a node that
has right child, in this case we will pop 5 [check if the right child exists, push it onto the stack]
4. if RIGHT[PTR] != NULL, then

Process 4, 9 4.a Set TOP = TOP +1 and STACK[TOP] = -RIGHT[PTR]

STACK
[end of if]

6.2.3 Postorder traversal: 5. Set PTR = LEFT[PTR] [ move to left child]

[end of step 2 loop]

93 94

[pop the top element of the stack] STACK Φ 2 -5 7 -6 2

6. Set PTR = STACK[TOP] and TOP = TOP - 1

[backtrack] 3. Backtrack and pop nodes one by one from the stack and process them till you find a negative
7. Repeat Steps 8 and 9 while PTR > 0
entry in the stack, do not process negative element. In this case we will pop 2 and -6.
8. Apply PROCESS to INFO[PTR]
Process 2
[pop the top element of the stack] Set PTR = - (-6) = 6, the right child of 7
9. Set PTR = STACK[TOP] AND TOP = TOP – 1
STACK Φ 2 -5 7
[end of step 7 loop]

10. if PTR < 0, then 4. Move to the left most path starting from node 6 and push all elements onto the stack along
with the negative values of their right child if exists. Now that 6 has a right child 11, the stack
11. Set PTR = -PTR will look like this
12. goto step 2
STACK Φ 2 -5 7 6 -11 5
[end of if]

11. Exit 5. Backtrack and pop nodes one by one from the stack and process them till you find a negative
entry in the stack, do not process negative element. In this case we will pop 5 and -11.
For example, consider the binary tree given in figure 6.1.

Process 5
Set PTR = - (-11) = 11, the right child of 6
STACK Φ 2 -5 7 6

6. Move to the left most path starting from node 11 and push all elements onto the stack along
with the negative values of their right child if exists.

STACK Φ 2 -5 7 6 11

7. Backtrack and pop nodes one by one from the stack and process them till you find a negative
entry in the stack, do not process negative element. In this case we will pop 11, 6, 7, -5

1. Push Φ onto STACK and, set PTR = 2. Process 11, 6, 7

STACK Φ Set PTR = - (-5) = 5, the right child of 2

STACK Φ 2

2. Move to the left most path starting from root node and push all elements onto the stack along
with the negative values of their right child if exists. Now that node 2 has right child 5 and 8. Move to the left most path starting from node 5 and push all elements onto the stack along

node 7 has a right child 6, the stack will look like this with the negative values of their right child if exists.

95 96
 (Inorder) 4 2 6 5 1 7 3 12 10 8 11
STACK Φ 2 5 -9
(preorder) 1 2 4 5 6 3 7 8 10 12 11
9. Backtrack and pop nodes one by one from the stack and process them till you find a negative
entry in the stack, do not process negative element. In this case we will pop -9 Order of processing (Inorder) LEFT ROOT RIGHT
Set PTR = - (-9) = 9, the right child of 5 Order of processing (Preorder) ROOT LEFT RIGHT
STACK Φ 2 5 9
From the order of processing using preorder method, we can conclude that the first node to be processed
10. Move to the left most path starting from node 9 and push all elements onto the stack along is the root of the tree and hence “1” is the root of the original tree. Now that we have
with the negative values of their right child if exists. 4nodes to the left of “1” and 6 nodes to the right of “1” in Inorder processing, we are assured of the
following:
STACK Φ 2 5 9 4

11. Backtrack and pop nodes one by one from the stack and process them till you find a
negative entry in the stack, do not process negative element. In this case we will pop 4, 9, 5, 2, Φ

Process 4, 9, 5, 2
Set PTR = Φ
STACK Φ 2 5 9

Check your progress/ Self assessment questions The second node to be processed using Preorder technique is “2” and it can be concluded that it is the
root node of the left sub-tree. Also we have one node to the left of “2” in the left sub-tree and 2 nodes
Q4. Define Postorder traversal.
____________________________________________________________________________ to the right of “2” in the left sub-tree, we are assured of the following:

___________________________________________________________________________

____________________________________________________________________________

Q5. Write Recursive Inorder traversal algorithm.

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

It is possible to verify if the order of traversal using above method is correct or not. It can be
achieved by regenerating the original binary tree from the order of processing given for two
methods

Consider the following example After “4”, the next node to be processed using Preorder technique is “5” and hence it can be concluded
that “5” which is on the right side of “2” is the root node of the right sub-tree of node “2”.

97 98

Also there is no node to the right of “5” and only one node to the left of “6”, the left sub-tree needs no
more expansion:

Because “10” comes before “12” in Preorder processing, node “10” will be the root node of left subtree
of “8” and the final tree will look like this:
The first node to be processed using Preorder from the right sub-tree of root “1” is “3”. The left subtree
of “3” will contain only one node that does not require further expansion and the right sub-tree of
“3” will contain 4 nodes.

The first node to be processed using Preorder from the right sub-tree of root “3” is “8”. The left subtree 6.3 Summary
of “8” will contain two nodes and the right sub-tree of “8” will contain only one node that does not Traversal of tree data structure is complicated as it is a non-linear data structure. Each node in a binary
require further explain. tree may further be divided into two sub-trees called the left sub-tree and right sub-tree. There are three

99 100
popular methods of traversing binary tree called Pre-order traversal, In-order traversal and Post-order 2. The three popular methods of traversing binary tree are as follows:
traversal. a. Pre-order traversal.
Preorder traversal of the binary tree can be carried-out by following the sequence as given below: b. In-order traversal.
c. Post-order traversal.
a. Visit the root.
b. Traverse the left sub-tree. 3. Preorder traversal of the binary tree can be carried-out by following the sequence as given below: a.
c. Traverse the right sub-tree Visit the root.
b. Traverse the left sub-tree.
Inorder traversal of the binary tree can be carried-out by following the sequence as given below: a. c. Traverse the right sub-tree
Traverse the left sub-tree.
b. Visit the root. For example,
c. Traverse the right sub-tree.

Postorder traversal of the binary tree can be carried-out by following the sequence as given below: a.
Traverse the left sub-tree.
b. Traverse the right sub-tree.
c. Visit the root.

We can also construct the original binary tree in case we are supplied with the Inorder and Preorder The order of processing is: A B C
traversal of binary tree.
4. Postorder traversal of the binary tree can be carried-out by following the sequence as given below: a.
6.4 Glossary Traverse the left sub-tree.
Preorder- method of traversing binary tree in which the node is processed first, then the left sub-tree and b. Traverse the right sub-tree.
then the right sub-tree. c. Visit the root.
Postorder- method of traversing binary tree in which the left sub-tree is processed first, then the right
sub-tree and then the root node. For example,
Inorder- method of traversing binary tree in which the left sub-tree is processed first, then the root and
then the right sub-tree.
Recursive algorithm- Algorithm that contains a call to itself is called recursive algorithm.

6.5 Answers to check your progress/self assessment questions

1. Traversal of tree data structure is complicated because it is a non-linear data structure as compared
to linear data structures like arrays, linked list, stacks and queues. Each node in a binary tree may The order of processing is: B C A
further be divided into two sub-trees called the left sub-tree and right sub-tree. Challenge lies in the
fact that we need to process each node exactly once. 5.
a. Set PTR = ROOT

101 102

b. R_INORD (INFO, LEFT[PTR])

c. Apply PROCESS to INFO[PTR]
d. R_INORD (INFO, RIGHT[PTR])
e. Exit.

6.6 References/ Suggested Readings

1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill
2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage.
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education.

6.7 Model questions Give the order of Inorder traversal of the tree T.
1. Following is the Inorder and preorder traversal of binary tree T with 9 nodes
Inorder: 5 1 3 11 6 8 4 2 7 5. Write the recursive solution to Inorder traversal of binary tree.
Preorder: 6 1 5 11 3 4 8 7 2

Draw the binary tree T.

2. Consider the following binary tree T,

Give the order of Preorder traversal of the tree T.

3. Write the non-recursive Postorder traversal of a binary tree.

4. Consider the following binary tree T,

Lesson- 7 Binary Search Tree

103 104
Structure of the lesson The value at each node N is greater than the value at all nodes in the left sub-tree of N and is less
7.0 Objective than the value at all nodes in the right sub-tree of N.
7.1 Introduction The binary search tree defined using the above property ensures that there is no duplicate nodes that
7.2 Definition of BST exist in the binary search tree.
7.3 Creating a BST
7.4 Searching in BST For example, consider the following binary search tree:
7.5 Inserting in BST
7.6 Deleting in BST
7.7 Summary
7.8 Glossary
7.9 Answers to check your progress/self assessment questions
7.10 References/ Suggested Readings
7.11 Model questions

7.0 Objective
After studying this lesson, students will be able to:
1. Discuss the concept of binary search tree.
2. Explain the search operation in BST.
3. Explain the insert operation in BST.
Figure 7.1 Binary search tree
4. Explain the delete operation in BST.

Now in figure 7.1, values at all nodes in the left sub-tree from level 1 are less than that of the root node
R and values at all nodes in the right sub-tree from level 1 are greater than that of the root node R. The
7.1 Introduction
same applies for all other nodes in the tree.
In the last two lessons you saw the basic terminologies and traversal algorithms for binary trees. Other
then traversal, the other basic operations like insertion, deletion and searching are extremely expensive
Binary search tree does not satisfy any other property of binary tree other than the one used to define it.
on basic binary trees. To reduce the cost in terms of time and effort for implementing basic operations
on trees, you will be introduced to more advanced version of binary tree called BST.
7.3 Creating a BST
In this section you will learn to create a BST from scratch. Suppose you have a NULL tree, a tree
7.2 Definition of BST
without any node, and you have to create a binary search tree for a given list of numbers.
Binary search tree is an advanced binary tree with a very good average running time to search for an
Let us consider the following list:
ITEM in the tree, i.e. f(n) =0(log2 n),where n is the number of nodes or data items in the binary search
tree. Insert and delete operations on binary search tree also takes lesser time then the basic binary tree.
50 80 30 12 90 65 40 68 55
Let me define the binary search tree for you:

Element 50
Binary tree T is a binary search tree if is satisfies the following property:

Because the tree is NULL, the first element in the list becomes the ROOT node of the binaty search
tree.

105 106

Element 80

It is greater than 50, and hence will be stored as right child of the ROOT node.

Element 90
It is greater than 50, and also greater than 80, hence will be stored as right child 80 which is again
right child of the ROOT node.

Element 30
It is lesser than 50, and hence will be stored as left child of the ROOT node.

Element 65
It is greater than 50, but lesser than 80, hence will be stored as left child 80 which is right child of
Element 12
the ROOT node.
It is lesser than 50, and also lesser than 30, hence will be stored as left child 30 which is again left
child of the ROOT node.

107 108
Element 40
It is lesser than 50, but greater than 30, hence will be stored as right child 30 which is left child of
the ROOT node. Element 55
It is greater than 50, Lesser than 80 and also lesser than 65, hence will be stored as left child 65
which is again left child of 80, which further is right child of ROOT node.

Element 68
It is greater than 50, Lesser than 80 and greater than 65, hence will be stored as right child 65
which is left child of 80, which further is right child of ROOT node.

This is how the final Binary Search Tree will look like if it is created using the given string os
numbers: 50 80 30 12 90 65 40 68 55

Check your progress/ Self assessment questions

Q1. Define binary search tree.

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

109 110

4. If ITEM = INFO[PTR], Then [If the ITEM is successfully found] Set LOC = PTR
Q2. What is the average search time to find an item in binary search tree? PAR = PRE ITEM = INFO[PTR]
____________________________________________________________________________ and return.

___________________________________________________________________________ 5. If ITEM < INFO[PTR], Then [If the ITEM is less then INFO[ROOT], search for the] Set
PRE = PTR [ITEM in the left sub-tree of PTR] PTR = LEFT[PTR]
____________________________________________________________________________
Else
Q3. If we construct a binary search tree for a given list of elements:
6.
50 23 47 67 65 45 90 52 69 33 Set PRE = PTR [else search for the ITEM in the right sub-tree of PTR]
PTR = RIGHT[PTR] [End of If Loop]
A. Which nodes come to the left of 67
[End of Step 4 Loop]
B. Which nodes come to the right of 33
7. Set LOC = NULL and PAR = PRE [If the ITEM does not exist in the binary search tree]
C. Which is going to be the right child of ROOT node
8. Exit.
____________________________________________________________________________
Let us consider the following binary search tree.
___________________________________________________________________________

____________________________________________________________________________

7.4 Searching in BST

Searching in BST is much faster than searching in simple binary tree. Average running time to search
for an ITEM in the tree is f(n) =0(log2 n),where n is the number of nodes or data items in the binary
search tree.

Starting from the root node R, we compare the ITEM to be searched with the current node. If it does not
match the current node, depending on the value of the ITEM, it is searched in the left or right subtree. Figure 7.2 Binary Search Tree
It follows the principle of divide-and-conquer methodology.
For Example, let the ITEM to be searched is 7.
The search operation will start from the root node R. In the first iteration, ITEM is compared with
ALGORITHM SEARCH_BST (SEARCH FOR ITEM IN BST) For a given Binary Search Tree
INFO[R]. The value of ITEM is less than INFO[R]. In the next iteration the ITEM will be searched in
T, the algorithms searches for an ITEM in the BST T. The location of the ITEM is BST is
saved in LOC and the location of its parent node is saved in PAR. the left sub-tree.

1. If ROOT = NULL, Then [If the tree is empty]

Set LOC = NULL
PAR = NULL and
return.

2. Set PTR = ROOT [Start the search process from ROOT node] PRE =
NULL

3. Repeat while PTR != NULL

111 112
 The ITEM is equal to root of right sub-tree. Hence the ITEM is located at level 3.

The ITEM is greater than the root of left sub-tree. Hence the ITEM will now be searched in the right
sub-tree.
7.5 Inserting in BST
Insertion in binary search tree always happen at the bottom of the of tree. The process in finding in the
location where the ITEM will be inserted is similar to searching an ITEM in the binary search tree.

By definition, no two nodes in the binary search tree can have same value. Hence, if the ITEM to be
inserted in the binary search tree already exists, the ITEM is not inserted in the binary search tree.

The algorithm first looks for the correct location in the binary search tree where the item can be inserted.
Starting from the root node R, the ITEM is compared with the INFO of root node to identify, if the
ITEM is to be inserted in the left or right sub-tree.

The ITEM is greater than the root of right sub-tree. Hence the ITEM will now be searched in the right The same process is iterated again and again till we reach the bottom level of the binary search tree.
sub-tree. Depending on the ITEM is smaller or greater than the leaf node, The item is inserted as the left or right
child of that leaf node respectively.

ALGORITHM INSERT_BST (INSERT AN ITEM IN BST) The location of its parent node
PAR is returned by SEARCH_BST algorithm. Also if the ITEM already exists in the BST
is also returned by SEARCH_BST.

1. Call SEARCH_BST [To know if the ITEM already exists]

[in BST and also the LOC of its parent]

2. If LOC != NULL, Then [It means the ITEM already exists]

PRINT "Duplicate entry not allowed"
And Exit.

113 114

3. If AVAIL = NULL [No free space exists to insert node]

PRINT "OVERFLOW"
And Exit.

4. Set LOC = AVAIL [assign free node from AVAIL list to]
AVAIL = LEFT[AVAIL] [LOC & assign the value of ITEM to it]
INFO[LOC] = ITEM
LEFT[LOC]= NULL
RIGHT[LOC] = NULL

5. If PAR = NULL, Then [if the existing BST is NULL]

Set ROOT = LOC

6. Else If ITEM < INFO[PTR], Then [insert the new node to the left of]
Set LEFT[PAR] = LOC [parent node]
Now the ITEM is compared with the root node of the respective left sub-tree. ITEM is greater than the
7. Else
INFO of root node and hence the location of the ITEM should be searched in the right sub-tree.
Set RIGHT[PAR] = LOC [insert the new node to the right of]
[End of If] [parent node]

8. Exit.

Consider the following binary search tree.

Again the ITEM is compared with the root node of the respective right sub-tree. ITEM is greater than
the INFO of root node and hence the location of the ITEM should be searched in the right sub-tree.

Figure 7.3 Binary Search Tree.

Suppose the ITEM to be inserted is 8.

In this case, ITEM is less than the INFO of root node and hence the location of then ITEM should be
searched in the left sub-tree.

115 116
Again the ITEM is compared with the root node of the respective right sub-tree. ITEM is greater than
Q6. What is the role of PRE or PAR pointer in the search algorithm for BST?
the INFO of root node and hence the location of the ITEM should be searched in the right sub-tree.i
____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

7.6 Deleting in BST

The delete operation in BST is more complex than the insert operation in BST. The delete operation in
BST is classified into:
1. Deleting a node with no or single child.
2. Deleting a node with 2 children.
DELETING A NODE WITH NO OR SINGLE CHILD IN BST
Now that the RIGHT[R] is NULL, the location where ITEM should be inserted is on the right of node
Simply replace the value of PTR, (pointer pointing to the location of the node to be deleted) with the
with INFO = 7.
value of CHILD (pointer pointing to the location of the child node for the node to be deleted).
The binary search tree after insert operation will look like as follows:

DELETING A NODE WITH NO CHILD

Let us consider the following binary search tree:

Check your progress/ Self assessment questions

Q4. What is the role of AVAIL list in insert operation of BST.

Figure 7.4 Binary Search Tree
____________________________________________________________________________

___________________________________________________________________________ Consider that you wish to delete the node with INFO[PTR] = 20.
____________________________________________________________________________ The node PTR does not have any child and hence the value of CHILD is NULL.

Q5. Why the existence of ITEM in BST is done during insert operation in BST?
____________________________________________________________________________ Simply replace the value of PTR with that of CHILD. In this case PTR will become NULL. After this
step the BST after the delete operation will look like this.
___________________________________________________________________________

____________________________________________________________________________

117 118

DELETING A NODE WITH SINGLE CHILD

Again consider the BST given in figure 7.4. DELETING A NODE WITH TWO CHILDREN
Again consider the BST given in figure 7.4.

Consider that you wish to delete the node with INFO[PTR] = 22.
The node PTR has only one child and hence the value of CHILD will be the location of either the left Consider that you wish to delete the node with INFO[PTR] = 4.

or right child of that node. The delete rule says, replace the node to be deleted with the node next to it in the in-order traversal

It is decided using the following rule: of the tree.

If LEFT[PTR] != NULL, Then In-Order traversal of the BST given in figure 7.4 is

CHILD = LEFT[PTR] 3 4 5 6 7 9 17 20 22

Else Now, the node next to node with INFO = 4 is the node with INFO = 5.
CHILD = RIGHT[PTR]
Simply replace the node with INFO = 4 with the node with INFO = 5, the delete operation will be

In this case CHILD = LEFT[PTR] complete.

Simply replace the value of PTR with that of CHILD. In this case PTR after this step will point to node
with INFO = 20. After this step the BST after the delete operation will look like this.

119 120
 Algorithm- Step by Step solution to a problem in hand.
In-Order Traversal- Technique of traversing a binary tree in which the left node is processed first, than
the root node and then the right node.

7.9 Answers to check your progress/self assessment questions

1. Binary tree T is a binary search tree if is satisfies the following property:
The value at node N is greater than the value at all nodes in the left sub-tree of N and is less than the
value at all nodes in the right sub-tree of N.

2. Binary search tree is an advanced binary tree with a very good average running time to search for an
7.7 Summary
ITEM in the tree, which is f(n) =O(log2 n),where n is the number of nodes or data items in the binary
Binary tree T is a binary search tree if is satisfies the following property:
search tree.
The value at node N is greater than the value at all nodes in the left sub-tree of N and is less than
the value at all nodes in the right sub-tree of N. The binary search tree defined using the above
3. A. Nodes to the left of 67 are 65 and 52. B. Nodes to the right of 33 are 47 and 45.
property ensures that there is no duplicate nodes that exist in the binary search tree.
C. Right child of root node will be 67.
Searching in BST is much faster than searching in simple binary tree. Average running time to search
for an ITEM in the tree is f(n) =0(log2 n),where n is the number of nodes or data items in the binary
4. If the AVAIL list is empty, it means that there is no node in the free pool list and hence the
search tree.
insert operation cannot be completed for the given BST.
Insertion in binary search tree always happen at the bottom of the of tree. The process in finding in the
location where the ITEM will be inserted is similar to searching an ITEM in the binary search tree.
5. Existence of ITEM in BST is checked during the insert operation in BST because of the
Depending on the ITEM is smaller or greater than the leaf node, The item is inserted as the left or right
following property of BST:
child of that leaf node respectively.
The value at node N is greater than the value at all nodes in the left sub-tree of N and is less than
The delete operation in BST is more complex than the insert operation in BST. The delete operation in
the value at all nodes in the right sub-tree of N.
BST is classified into:
The binary search tree defined using the above property ensures that there is no duplicate nodes that
1. Deleting a node with no or single child.
exist in the binary search tree.
2. Deleting a node with 2 children.
For delete operation on a node with no or single child, Simply replace the value of PTR, (pointer
6. In case you wish to search the location for an ITEM to be inserted in the BST, The PAR or PRE
pointing to the location of the node to be deleted) with the value of CHILD (pointer pointing to the
pointer returns the location of the parent node of the new node that will be inserted.
location of the child node for the node to be deleted).
For delete operation on a node with two children, replace the node to be deleted with the node next to it
7.10 References/ Suggested Readings
in the in-order traversal of the tree.
1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill.
2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage.
7.8 Glossary
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education.
Tree- A non linear data structure with hierarchal relation among nodes.
BST- A BST is one on which value at each node N is greater than the value at all nodes in the left sub-
7.11 Model questions
tree of N and is less than the value at all nodes in the right sub-tree of N.
1. Define BST with the help of an example.
ROOT- The very first node or the node at the top of the tree.

121 122

2. Explain the process of searching an ITEM in BST and also discuss the complexity of the search 8.1 Introduction
operation. 8.2 AVL Tree
3. Write the algorithm to search for an ITEM in BST. 8.2.1 Inserting in AVL tree
4. Create binary search tree for the following string of elements: 8.2.2 Deleting in AVL tree
67 80 90 76 34 56 12 23 1 78 47 8.3 M-way Tree
5. Explain in detail the process of delete operation in BST. 8.4 B Tree
8.4.1 Inserting in B tree
8.4.2 Deleting in B tree
8.5 B+ Tree
8.6 Summary
8.7 Glossary
8.8 Answers to check your progress/self assessment questions
8.9 References/ Suggested Readings
8.10 Model questions

8.0 Objective
After studying this lesson, students will be able to:
1. Define AVL tree.
2. Explain insert and delete operation on AVL tree.
3. Describe the notion of M-way tree.
4. Define B Tree
5. Explain insert and delete operation on B Tree
6. Define B+ Tree.

8.1 Introduction
In the last lesson you learned the concept of binary search tree and the advantages it has to offer. But a
binary search tree is not a guarantee of good performance. You need to maintain the balance of the tree.
How do you manage the balance in height of the tree is discussed in this lesson. Also in the binary
search tree, each node can have maximum of two children which makes it difficult to represent practical
problems. In this lesson you will learn about a special type of tree that allows each node to have more
than two children and still maintain the properties of the binary search tree. You will also learn to
balance this special tree as well. I am sure you will enjoy studying this lesson and especially enjoy doing
exercises.

Lesson- 8 Height Balanced Trees 8.2 AVL Tree

Structure of the lesson The average search time of a BST is f(n) =0(log2 n). But for certain BST's the search time can almost
8.0 Objective be equal to linear search. It happens when there is a significant difference between the height's of the

123 124
left and the right sub-trees of the binary search tree. By definition, Binary tree T is a binary search AVL tree is a very popular balanced binary search tree that was designed by the trio of Adelson, Velskii
tree if is satisfies the following property: and Landis in the year 1962.

The value at each node N is greater than the value at all nodes in the left sub-tree of N and is less An AVL tree can be defined as follows:
than the value at all nodes in the right sub-tree of N. 1. Either the binary search tree T is empty, or
2. For the given binary search tree T, the difference in the height of the left sub tree and the right sub
To have better understanding of the height difference between left and right sub-trees of BST and the tree should not be more than one.
problems faced due to it, consider the following two types of trees:
Let TL be the left sub tree and TR be the right sub tree.
Also let h( TL ) be the height of left sub tree and h(TR ) be the height of the right sub tree.
According to the definition | h( TL ) - h(TR ) | should not be greater than 1.
This difference in the height of the sub trees is also called balance factor (BF). It means the balance
factor BF = h( TL ) - h(TR ).

In case of AVL tree BF can have only three possible values, i.e. 0, 1 or -1.
0 means that the height of the left tree is equal to the height of the right sub tree. 1 means that the height
of the left tree is 1 more than the height of the right sub tree. -1 means that the height of the left tree is
1 less than the height of the right sub tree.

Figure 8.1 Right and Left skewed binary search trees BF is computed for each node in the AVL tree including the leaf nodes. Because the leaf nodes do not
have a child, the BF is always zero.
Right skewed binary search tree is one in which all nodes except the leaf node have one child and are
less than their child node. Hence the tree is moving towards the right direction as no node has a left Consider the following AVL Tree for example,
child.

Left skewed binary search tree is one in which all nodes except the leaf node have one child and are
greater than their child node. Hence the tree is moving towards the left direction as no node has a right
child.

If you observe carefully, both the trees in Figure 8.1 are binary search trees and but are of little help. If
Figure 8.2 AVL with BF for each node.
you wish to search for an element in left or right skewed binary search tree, the complexity is equal to
the linear search algorithm as all elements are arranged linearly.
Height of the left sub tree of root node is 1 and the height of the right sub tree of root node is 2. Hence
the BF for the root node is, BF = h( TL ) - h(TR ) = 1 -2 = -1.
The problem with both the trees shown in the figure 8.1 is that they are imbalanced. There is significant
difference in the heights of left and right sub-tree. The solution to this problem is to balance the binary
Balance factor for all other nodes is 0.
tree.

125 126

Check your progress/ Self assessment questions -1

This tree after insert operation is not an AVL tree any more. So, you need to perform rotation to get this
Q1. What is left skewed binary search tree?
____________________________________________________________________________ tree back to AVL tree.

___________________________________________________________________________
Rotation operation after insert operation on AVL tree depending on the position of the newly inserted
____________________________________________________________________________
node is classified as follows:
Q2. Define AVL tree?
____________________________________________________________________________
LL rotation- Inserted node is in the left sub tree of the left sub tree of the node X.
___________________________________________________________________________ RR rotation- Inserted node is in the right sub tree of the right sub tree of the node X.
RL rotation- Inserted node is in the left sub tree of the right sub tree of the node X. LR
____________________________________________________________________________
rotation- Inserted node is in the right sub tree of the left sub tree of the node X.
[Link] is balance factor in AVL tree?

You will learn all rotations directly with the help of examples:
____________________________________________________________________________ Single Rotation:
LL rotation and RR rotation are also called single rotation operations. It is because a single rotation of
___________________________________________________________________________
key nodes results in balancing the AVL tree.
____________________________________________________________________________

LL rotation:
8.2.1 Inserting in AVL tree Consider the following AVL tree
Insertion operation in the AVL tree is divided into two phases of which the second phase is not
mandatory. Insert operation in the first phase is similar to the insert operation in the BST. In case after
the insert operation, if the balance factor BF for any node in the AVL tree becomes 2 or -2, there arises
the need of technique called rotation.

In this phase a node A in the AVL tree is searched for which is the closest ancestor of inserted node and
whose balance factor BF after the insert operation has become 2 or -2.

Consider the following AVL tree,

Consider if a node is inserted in YL sub-tree, the AVL tree will look the following:

Figure 8.3 AVL tree after insert operation on AVL tree in figure 8.2

127 128
 Consider if a node is inserted in YR sub-tree, the AVL tree will look the following:
It is not an AVL tree any more as the balance factor of node X has become 2. There is need to
balance this AVL tree that can happen with the rotation as shown in the figure below:

It is not an AVL tree any more as the balance factor of node X has become -2. There is need to
After rotating the nodes as shown with the help of arrows, the right sub-tree of Y (YR) becomes balance this AVL tree that can happen with the rotation as shown in the figure below:
the left sub-tree of node X. Also the balance factor of all nodes in AVL is within limits.

RR rotation:

Consider the following AVL tree

129 130

Consider if a node is inserted in ZL sub-tree which is in the right sub-tree of the left sub-tree of
X, the AVL tree will look the following:

After rotating the nodes as shown with the help of arrows, the left sub-tree of Y (YL) becomes the
right sub-tree of node X. Also the balance factor of all nodes in AVL is within limits.

Double Rotation:
LR rotation and RL rotation are also called double rotation operations. It is because they need two
rotations to balance the AVL tree.
It is not an AVL tree any more as the balance factor of node X has become 2. There is need to
balance this AVL tree that can happen with two rotations as shown in the figures below:
LR rotation:
Consider the following AVL tree

131 132
 It is not an AVL tree any more as the balance factor of node X has become -2. There is need to
balance this AVL tree that can happen with two rotations symmetric to one shown in LR rotation.
The balanced AVL tree after two rotations will look like as shown in the figure below:
LR rotation:

Consider the following AVL tree:

8.4.2 Deleting in B tree

Consider the following AVL tree:

Consider if a node is inserted in ZR sub-tree which is in the left sub-tree of the right sub-tree of
X, the AVL tree will look the following:

133 134

Figure 8.4 AVL tree

If we delete node 1 to the left of the node 2, the tree will become imbalanced.

If you delete a node from sub-tree XL, the AVL tree will look as follows:

Figure 8.5 AVL tree with balance factor -2 after delete operation

Balancing AVL tree if needed after the delete operation can be classified as follows: R0,
R1, LO and L1

Let X be the closest ancestor to the delete node LOC whose balance factor after delete operation has
become +2 or -2. Y be the ROOT node of the left or right sub-tree of the X in which the node LOC is
deleted. R0 or L0 means that the balance factor of Y before deletion is 0 and R1 or L1 means that the
balance factor of Y before deletion is 1.

It is not an AVL tree any more, rotation is need to balance the tree. The LO rotation is shown as
The balance factor of ancestor node after rotation depends on whether the balance factor of Y before
follows:
deletion was 0 or 1.

If balance factor of Y is 0, after deletion the balance factor of ancestor node becomes -1 and if balance
factor of Y is 1, after deletion the balance factor of ancestor node becomes 0.
In this section, only the LO rotation is given. Rest of the rotations you should practice yourself.

Consider the following AVL tree for example:

135 136
 Order of the m- way tree is m, i.e. the maximum number of child nodes each node can have.

Consider the following m-way tree,

Figure 8.5 M-way tree

Check your progress/ Self assessment questions -2

It is a 4-way binary tree in which each node can have maximum of 3 keys and 4 child nodes.
Q4. List rotation types possible after insert operation in AVL tree.
____________________________________________________________________________ 8.4 B Tree
___________________________________________________________________________ Just like an AVL tree which is a balanced binary search tree, B Tree is a balanced m-way tree. The main
objective of using a B Tree is to minimize the height of the tree so as to improve the performance of
____________________________________________________________________________
search and other operations on B Tree.
Q5. Consider X to be the closest ancestor to deleted node N with BF -2 or 2 and Y to be the ROOT
node of the left or right sub-tree of the X in which the node LOC is deleted. What will be the balance B Tree acquires all the properties of the m-way tree including the following properties.
factor of ancestor node X after delete operation if BF of Y is 0 or 1?
____________________________________________________________________________ 1. ROOT node should have at least 2 child nodes.
___________________________________________________________________________
2. Internal nodes beside the ROOT node should have at least m/2 child nodes.
____________________________________________________________________________ 3. All leaf nodes should be at the same level.

8.3 M-way Tree If you think of a 6 way B tree, it is also called 3-6 tree as the degree of the internal nodes is between 3
For data stored in external memories like disks, BST or AVL trees are not the preferred choice. Mway to 6.
search trees are used to retrieve information from external memories. Consider the following B Tree:

M-way search tree is extension or generalization of binary search tree. In case of binary search tree,
there can be a maximum of two children of each node. Only one key is saved at each node. In case of
m-way search tree, you can store more than one key, to be exact m-1 keys that results into maximum of
m child nodes for each node. It helps to improve the complexity of the search operation exponentially.

Defining m-way tree:

For some value of m, each node can have maximum of m child nodes. A node can have maximum of k
Figure 8.6 B Tree
keys, such that k < m. Each node with k keys can have maximum of k+1 child nodes.

137 138

8.4.1 Inserting in B tree Consider the following B Tree or order 5.

The element is inserted in the B Tree at the leaf node. Depending on the value, search operation is used
to find the appropriate leaf node. If the leaf node is full before the insert operation, i.e. it already contains
m-1 keys, the element is added to its correct position in the leaf node, its median is selected and pushed
to the parent node one level up and the leaf node is split into two. If the parent node is also full, the
same process is repeated again.

Consider the following B Tree of order 5

Figure 8.9 B Tree of order 5

Suppose you want to delete key 200. The internal node containing 200 after delete operation will only
be left with 1 key which is less than m/2 = 2. Hence a key will be promoted from the child nodes. Keys
of two child nodes, one with keys greater than 200 and one with keys between 150 and 200 are
combined.

Figure 8.7 B Tree of order 5 166 190 210 218 267

Suppose you want to insert ITEM 48 in the B Tree. It should be added to the second child of ROOT Median of the combination is 210 and hence it will be promoted to replace 200. Both the leaf nodes will

node. But the node is already full. be left with two keys each.

If we add 48 at its correct position in the node, we get:

B Tree after delete operation will look like this:
33 45 46 48 52

Median is 46, and hence the same is added to the parent node and the leaf node is split into two. After
the insert operation, the B Tree looks like this:

Figure 8.10 B Tree of figure 8.8 after deleting key 200

Figure 8.8 B Tree of figure 8.7 after inserting key 48

Check your progress/ Self assessment questions -3

8.4.1 Deleting in B tree Q6. Define m-way tree.

____________________________________________________________________________
Deleting a key from leaf node is easy as compared to deleting a key from internal node. Minimum
number of keys have to maintained and if needed, key from lower nodes is promoted to satisfy the ___________________________________________________________________________

criteria. Sometimes you may also need to find a key from siblings. ____________________________________________________________________________
Keeping the minimum number of keys is the main consideration.
Q7. Define B Tree.
____________________________________________________________________________

139 140
 2. For the given binary search tree T, the difference in the height of the left sub tree and the right sub
___________________________________________________________________________
tree should not be more than one.
____________________________________________________________________________ This difference in the height of the sub trees is also called balance factor (BF). It means the balance
factor BF = h( TL ) - h(TR ). In case after the insert operation in AVL tree, if the balance factor BF for
Q8. How a key is inserted in B Tree? any node in the AVL tree becomes 2 or -2, there arises the need of technique called rotation.
____________________________________________________________________________ LL rotation- Inserted node is in the left sub tree of the left sub tree of the node X.
___________________________________________________________________________ RR rotation- Inserted node is in the right sub tree of the right sub tree of the node X.
RL rotation- Inserted node is in the left sub tree of the right sub tree of the node X.
____________________________________________________________________________
LR rotation- Inserted node is in the right sub tree of the left sub tree of the node X.
Balancing AVL tree if needed after the delete operation can be classified as R0, R1, LO and L1. M-
8.5 B+ Tree way tree is one in which for some value of m, each node can have maximum of m child nodes. A node
As suggested by the name itself, it is an variation of B Tree. B+ tree is used to implement the data can have maximum of k keys such that k < m and for each node with k keys, can have k+1 child nodes.
indexes. Queries can be worked upon more effectively if the data or records are stored in order. But it B Tree acquires all the properties of the m-way tree including the following properties.
is not easy and practical to store all records in a table in sorted order as it requires shifting of rows after 1. ROOT node should have at least 2 child nodes.
every insert or delete operation. 2. Internal nodes beside the ROOT node should have at least m/2 child nodes.
3. All leaf nodes should be at the same level.
The solution to this problem can be to use a tree and recording all our table rows in a tree structure. B+
tree is one in which each node has max of d references to child nodes and up to d-1 keys. B+ Tree does 8.7 Glossary
not allow you to save data in internal nodes. All data is stored in leaf nodes. AVL Tree- Balanced Binary search tree in which the difference in the height of the left sub tree and the
right sub tree is not more than one.
Maintaining a database or file system, the value of d can be extremely large. The actual values are all
Balance Factor- Difference in the height of the left and right sub trees is also called balance factor (BF).
stored at the leaf nodes and all leaf nodes are at equal distance from the ROOT node. The leaf nodes are
Rotation- Process of balancing the AVL tree after the insert or delete operation.
also linked to each other.
M-way tree- A tree in which each node can have maximum of m child nodes. A node can have maximum
of k keys such that k < m and for each node with k keys, can have k+1 child nodes.
The major advantage of using a B+ Tree is that all keys are saved in the leaf nodes in orderly
B Tree- Balanced AVL tree.
fashion and because the leaf nodes are linked to each other, all keys can be traversed in one go.

8.8 Answers to check your progress/self assessment questions

1. Left skewed binary search tree is one in which all nodes except the leaf node have one child and are
greater than their child node. Hence the tree is moving towards the left direction as no node has a
right child.

Figure 8.11 B+ Tree 2. An AVL tree can be defined as follows:

a. Either the binary search tree T is empty, or
8.6 Summary b. For the given non-empty binary search tree T, the difference in the height of the left sub tree and the
An AVL tree is: right sub tree should not be more than one.
1. Either the binary search tree T is empty, or According to the definition | h( TL ) - h(TR ) | should not be greater than 1.

141 142

3. This difference in the height of the left and right sub-trees is called balance factor (BF). It means 3. Explain with the help of an example the insert operation B Tree when all leaf nodes are full.
the balance factor BF = h( TL ) - h(TR ). In case of AVL tree BF can have only three possible values, 4. What is an m-way tree?
i.e. 0, 1 or -1. 0 means that the height of the left tree is equal to the height of the right sub tree. 1 means 5. Explain the LR rotation in AVL tree.
that the height of the left tree is 1 more than the height of the right sub tree. -1 means that the height of
the left tree is 1 less than the height of the right sub tree.

4. Rotation operation after insert operation on AVL tree depending on the position of the newly
inserted node is classified as follows:
LL rotation- Inserted node is in the left sub tree of the left sub tree of the node X.
RR rotation- Inserted node is in the right sub tree of the right sub tree of the node X.
RL rotation- Inserted node is in the left sub tree of the right sub tree of the node X. LR
rotation- Inserted node is in the right sub tree of the left sub tree of the node X.

5. If balance factor of Y is 0, after deletion the balance factor of ancestor node becomes -1 and if balance
factor of Y is 1, after deletion the balance factor of ancestor node becomes 0.

6. M-way tree is one in which for some value of m, each node can have maximum of m child nodes. A Lesson- 9 Heap
node can have maximum of k keys such that k < m and for each node with k keys, can have k+1 child Structure of the lesson
nodes. 9.0 Objective
9.1 Introduction
7. B Tree acquires all the properties of the m-way tree including the following properties: 9.2 Heap
a. ROOT node should have at least 2 child nodes. 9.3 Inserting in heap
b. Internal nodes beside the ROOT node should have at least m/2 child nodes. 9.4 Deleting from Heap
c. All leaf nodes should be at the same level. 9.5 Applications of heap
9.6 Summary
8. Depending on the key, search operation is used to find the appropriate leaf node. If the leaf 9.7 Glossary
node is full before the insert operation, the key is added to its correct position in the leaf node, its median 9.8 Answers to check your progress/self assessment questions
is selected and pushed to the parent node one level up and the leaf node is split into two. 9.9 References/ Suggested Readings
9.10 Model questions
8.9 References/ Suggested Readings
1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill 9.0 Objective
2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage After studying this lesson, students will be able to:
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education. 1. Define heap structure.
2. Explain the insert operation in heap.
8.10 Model questions 3. Rewrite algorithm to insert in heap.
1. Define AVL tree with the help of an example. 4. Explain the delete operation in heap.
2. What is a B+ Tree. 5. Rewrite algorithm to delete in heap.

143 144
 9.1 Introduction 2. Min-Heap- A binary tree H is called a Heap or Min-Heap if each node N in the binary tree H
In the last unit you studied in detail about the tree data structure, its representation in memory and also is less than or equal to all nodes in the left and right sub-trees of N.
about various type of tree structures. In this lesson you will study yet another important type of tree
structure called heap. Heap has important applications in the field of computer science. In this lesson
you will learn the algorithms to implement insert and delete operations on the heap. One of important
application of heap, i.e. heap sort is discussed later in this SLM. There are many more applications of
heap that are listed in this lesson.

9.2 Heap
Figure 9.3 Min-Heap
Heap is a special type of tree structure. Heap is always a complete binary tree and complete binary tree
has already been defined earlier in this SLM. Recall that you call a binary tree T to be complete if it is
Deleting elements one by one from the Min-heap and saving them to an array gives you the sorted
filled to the fullest. A binary tree T is a complete tree if it has the maximum possible nodes at all its
list of elements.
levels, except possibly the last. Also all the nodes at the last level are as far left as possible.

For ease of implementation, in this lesson it is assumed that the heap is represented in memory using
the array.

The array representation of a complete tree H has no blank entries in between as it is filled to the fullest
except the last level, and all nodes are as far left as possible. Because all levels except the last level are
filled to the fullest, it is easy to compute the address of the parent node for any given node using array
memory representation.

The address of parent node of k can be computed as int(k / 2).

Figure 9.1 Complete binary Tree For example, The parent of node 11 = int(11 / 2) = 5
The address of left child of k can be computed as k * 2.
Heap is of two types: For example, The left child of node 11 = 11 * 2 = 22
1. Max-Heap- A binary tree H is called a Heap or Max-Heap if each node N in the binary tree H The address of right child of k can be computed as (k * 2) + 1.
is greater than or equal to all nodes in the left and right sub-trees of N. For example, The right child of node 11 = (11 * 2) + 1 = 23

It is particularly useful when you implement the insert or delete operation on the heap.

Check your progress/ Self assessment questions- 1

Q1. Define complete binary tree.

____________________________________________________________________________

___________________________________________________________________________
Figure 9.2 Max-Heap
____________________________________________________________________________

145 146

Q2. Define Max-Heap and Min-Heap.

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Q3. What is the advantage of using array representation for heap?

____________________________________________________________________________

___________________________________________________________________________ Figure 9.5 Heap in figure 9.4 after inserting ITEM at the last level

____________________________________________________________________________
You can observe that tree is figure 9.5 after step 1 is not a heap because 21 is larger than its ROOT node
9.3 Inserting in heap and the ROOT node of tree H.
The insert operation in the heap is carried out in two steps: So in step 2, the ITEM 21 is promoted to its correct position in the heap.
1. The ITEM is inserted immediately next to the right most filled node in the in the last level. With
this the heap still remains to be a complete binary tree with all nodes in the last level are still as left as
possible.

2. Because the Max-Heap and Min-Heap are based on some rules, the newly inserted ITEM is
promoted in the heap to its appropriate position in the heap.

Main points to consider during the insert operation on heap is that after the insert operation the
tree H should still be a complete binary tree and satisfy all properties of the heap.
Consider the following heap for example,

Figure 9.5 Heap in figure 9.4 after step 2 of insert operation

The Tree shown in figure 9.5 after insert operation is heap as it is both complete binary tree and it
satisfies the properties of Max-Heap.

ALGORITHM_INSERTHEAP (It is used to insert ITEM in array HEAP representing heap in memory ).
Figure 9.4 Heap

1. Set N= N + 1 AND LOC = N

Let us suppose you want to insert ITEM 21 in heap.
After step 1, the heap will look like as shown in the figure below, 2. Repeat following steps while LOC > 1

3. Set PARENT = LOC/2

4. if ITEM <= HEAP[PARENT], then

5. Set HEAP[LOC] = ITEM

147 148
6. Return

[end of step 4 if statement]

7. Set HEAP[LOC] = HEAP[PARENT]

8. Set LOC= PARENT

[End of step 2 while loop]

9. Set HEAP[LOC] = ITEM

10. Return.

Step 5 ELEMENT 60
Creating Heap
Consider the following list of elements:
50, 44, 40, 48, 60, 58, 70, 19, 57, 78, 45

Step 1 ELEMENT 50

Step 2 ELEMENT 44

Step 6 ELEMENT 58

Step 3 ELEMENT 40

Step 7 ELEMENT 70

Step 4 ELEMENT 48

149 150

Step 8 ELEMENT 19

Step 10 ELEMENT 78

Step 9 ELEMENT 57

Step 11 ELEMENT 45

151 152
 2. The ROOT node is then replaced by the last node in the heap.
3. The new ROOT node or element in the ROOT node is demoted to its correct position in the heap.

Just like the insert operation, Tree after the delete operation again should be a complete binary tree and
also satisfy the properties of heap.

Consider the following heap:

Check your progress/ Self assessment questions- 2

Q4. Explain the process of insert operation in heap.

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Q5. Consider that in case of Max-Heap the newly inserted ITEM is less than the parent node. Will the
To delete the Root Node, the Root node is replaced by the last node in the tree.
ITEM be promoted one level up or not?
____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Q6. What is the purpose of following two statement in insert algorithm?

a. Set HEAP[LOC] = HEAP[PARENT]

b. Set LOC= PARENT

____________________________________________________________________________

___________________________________________________________________________ It ensures that it is still a complete binary tree, but it is not a heap at this moment. The next step
is to push the root node down the tree so that it can reach to a position where the tree again
____________________________________________________________________________
becomes the heap.

9.4 Deleting from Heap 45 is smaller than both the left and right child. But the right child is greater than the left child and hence
The node to be deleted in the heap is considered to be the ROOT node of the sub-tree or entire heap. the root will be interchanged with the right child.
The delete operation on heap or sub-heap can be achieved using following steps:
1. The value of the ROOT node is saved in ITEM.

153 154

10. Set HEAP[LOC] = HEAP[LEFTCHILD] AND LOC = LEFTCHILD

else
11. Set HEAP[LOC] = HEAP[RIGHTCHILD] AND LOC = RIGHTCHILD
[End of step 9 if statement]
12. Set LEFTCHILD = LOC * 2 AND RIGHTCHILD = (LOC * 2) + 1
[End of step 7 while loop]
13. if LEFTCHILD = N AND NEW < HEAP[LEFTCHILD], then
14. Set LOC = LEFTCHILD
Now, 45 is smaller than only the right child, hence the node 45 will be interchanged with the right child.
[End of step 13 if statement]
15. Set HEAP[LOC] = NEW
16. Exit

Check your progress/ Self assessment questions- 3

Q7. Explain the process of delete operation in heap.

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Q8. Consider that in case of Max-Heap the ROOT node is replaced with last node in the heap called
The tree in the figure above after the delete operation is both the complete binary tree and also satisfy ITEM which is less than both the child nodes of ROOT. Will the ITEM be demoted one level down? If
the properties of max-heap. yes, will it be replaced by left child or right child.
____________________________________________________________________________

ALGORITHM_DELETEHEAP (It is used to delete ROOT in array HEAP representing heap in memory ). ___________________________________________________________________________

1. Set ITEM = HEAP[1] ____________________________________________________________________________

2. Set NEW = HEAP[N]

3. Set N = N - 1 9.5 Applications of heap
4. Set LOC = 1 Following are some of the applications heap:

5. Set LEFTCHILD = 2 1. Priority Queue: heap structure can be effectively used to maintain a special queue called priority
queue. Recall that priority queue is one in which each element in the queue has an associated priority.
6. Set RIGHTCHILD = 3
Binomial heap is best suited to represent the priority queue. Binomial heap is one of the variations of
7. Repeat following steps while RIGHTCHILD <= N
heap tree structure. There are other ways to represent the priority queue like 2-D array and linked
8. IF NEW >= HEAP[LEFTCHILD] AND HEAP[RIGHTCHILD], then
representation. But both the representations are not as effective as the binomial heap.
9. Set HEAP[LOC] = NEW 2. Heap Sort- Heap sort is one of the sorting algorithms and one of the applications heap. Given
[End of step 8 if statement] MinHeap, elements can be deleted one by one and added to a list. List in the end will consist of sorted

9. if HEAP[LEFTCHILD] >= HEAP[RIGHTCHILD], then elements.

155 156
3. Order Statistics- Heap structure is widely used to find the ith largest or smallest number in the list. Priority Queue- A special queue in which each element in the queue has an associated priority. Max-
Heap- Complete binary tree H in which each node N in the binary tree H is greater than or equal to all
9.6 Summary nodes in the left and right sub-trees of N.
Heap is always a complete binary tree. A binary tree T is a complete tree if it has the maximum possible Min-Heap- Complete binary tree H in which each node N in the binary tree H is less than or equal to all
nodes at all its levels, except possibly the last, also all the nodes at the last level are as far left as possible. nodes in the left and right sub-trees of N.
Max-Heap is a complete binary tree H if each node N in the binary tree H is greater than or equal to all Binary Tree- A tree in which each node can have maximum of two child nodes.
nodes in the left and right sub-trees of N. Min-Heap is a complete binary tree H if each node N in the Complete Binary tree- Binary tree T filled to the fullest. A binary tree T is a complete tree if it has the
binary tree H is less than or equal to all nodes in the left and right sub-trees of N. The array maximum possible nodes at all its levels, except possibly the last, also all the nodes at the last level are
representation of a complete tree H has no blank entries in between as it is filled to the fullest and as far left as possible.
starting from the left. Because all levels except the last level are filled to the fullest, it is easy to compute Array- Collection of similar type of elements stored continuously in memory.
the address of the parent node for any given node using array memory representation.

The address of parent node of k can be computed as int(k / 2). 9.8 Answers to check your progress/self assessment questions

The address of left child of k can be computed as k * 2. 1. A binary tree T is a complete binary tree if it is filled to the fullest or it has the maximum possible

The address of right child of k can be computed as (k * 2) + 1. nodes at all its levels, except possibly the last. Also all the nodes at the last level are as far left as

The insert operation in the heap is carried out in two steps: possible.

1. The ITEM is inserted immediately next to the right most filled node in the in the last level. With
this the heap still remains to be a complete binary tree with all nodes in the last level are still as left as 2.

possible. a. Max-Heap- A binary tree H is called a Heap or Max-Heap if each node N in the binary tree H

2. Because the Max-Heap and Min-Heap are based on some rules, the newly inserted ITEM is is greater than or equal to all nodes in the left and right sub-trees of N.

promoted in the heap to its appropriate position in the heap. b. Min-Heap- A binary tree H is called a Heap or Min-Heap if each node N in the binary tree H

The node to be deleted in the heap is considered to be the ROOT node of the sub-tree or entire heap. is less than or equal to all nodes in the left and right sub-trees of N.

The delete operation on heap or sub-heap can be achieved using following steps:
1. The value of the ROOT node is saved in ITEM. 3. The array representation of a heap which is also a complete tree H has no blank entries in between as

2. The ROOT node is then replaced by the last node in the heap. it is filled to the fullest and starting from the left. Because all levels except the last level are filled to

3. The new ROOT node or element in the ROOT node is demoted to its correct position in the heap. the fullest, it is easy to compute the address of the parent and child nodes for any given node using

Following are some of the applications of heap: array memory representation.

1. Priority Queue: Heap structure can be effectively used to maintain a special queue called priority
queue. Recall that priority queue is one in which each element in the queue has an associated priority. 4. The insert operation in the heap is carried out in two steps:

Binomial heap is best suited to represent the priority queue. a. The ITEM is inserted immediately next to the right most filled node in the in the last level. With

2. Heap Sort- Heap sort is one of the sorting algorithms and one of the applications heap. Given this the heap still remains to be a complete binary tree with all nodes in the last level are still as left as

MinHeap, elements can be deleted one by one and added to a list. List in the end will consist of sorted possible.

elements. b. Because the Max-Heap and Min-Heap are based on some rules, the newly inserted ITEM is

3. Order Statistics- Heap structure is widely used to find the ith largest or smallest number in the list. promoted in the heap to its appropriate position in the heap.

9.7 Glossary 5. In case of Max-Heap, the parent node should be greater than the child nodes. Hence, if the newly
inserted ITEM is less than the parent node, it will not be promoted one level up.

157 158

6.
a. Set HEAP[LOC] = HEAP[PARENT]
The statement above is used to demote the Element in PARENT node one level down in the heap. b.
Set LOC= PARENT
The above statement is used to set the location of ITEM to be inserted to the parent node of the current
location of ITEM.
7. The delete operation on heap or sub-heap can be achieved using following steps:
a. The value of the ROOT node is saved in ITEM.
b. The ROOT node is then replaced by the last node in the heap.
c. The new ROOT node or element in the ROOT node is demoted to its correct position in the heap.

8. In case of Max-Heap the ROOT node is always greater than the child nodes. Yes the ITEM which is Lesson- 10 Fundamentals of graph
less than both the child nodes of ROOT will be demoted one level down. It will it be replaced by the Structure
child node which is greater in value than the other. 10.0 Objective
10.1 Introduction
9.9 References/ Suggested Readings 10.2 Definition of graph
1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill 10.3 Basic Types of graph
2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage 10.4 Difference between tree and graph
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education. 10.5 Graph representation
10.5.1 Adjacency Matrix
9.10 Model questions 10.5.2 Adjacency List
1. Define min and max heaps with the help of example each. 10.6 Applications of Graph
2. Write the algorithm to insert an ITEM in heap. 10.7 Summary
3. Create heap for the following list 10.8 Glossary
12 88 90 43 77 43 8 10.9 Answers to check your progress/self assessment questions
4. Write the algorithm to delete ROOT from heap. 10.10 References/ Suggested Readings
5. List various applications of heap. 10.11 Model questions

10.0 Objective
After studying this lesson, students will be able to:
1. Define non-linear data structure called graph
2. Explain different types of graphs
3. Discuss adjacency matrix representation of graph
4. Discuss adjacency list representation of graph
5. List various differences between graph and tree data structures.

10.1 Introduction

159 160
In this lesson you will learn about the second non-linear data structure called graph. Graph has a wide
range of applications in the field of computer science and solution to many complex problems lies in
the basic properties of graph. Graph may seem similar to tree but is lot different from the tree data
structure. Graphs comes in large number of variations and you can select the graph type depending upon
the problem in hand. In this lesson, beside learning various types of graphs, you will also learn two
techniques that are used to represent graph in memory. You need to pay attention to the fundamentals
of graphs as they form the basis for the next lesson in which you will learn different operations on graph.

10.2 Definition of graph

Figure 10.2 Directed Graph
As already stated that graph is a non-linear data structure. You may define a graph as follows:
A graph G=(V,E) consists of
The graph shown in the figure above is called a directed graph. The above graph consists of following
a. set of vertices or nodes (V)
set of vertices and edges:
b. and a set of edges (E).

V= {1, 2, 3, 4, 5, 6}
Consider the following two sets for example,
E = {1->2, 2->3, 2->4, 4->5, 4->6, 5->6, 6->3 }
V= {A, B, C, D, E, F}
An edge 1->2 in directed graph means that there is an edge or path from node 1 to node 2, but the vice
E = {( A, B), (A,C), (A,D), (B,C), (B,E), (D,E), (D,F) }
versa is not true.

Basic terminologies of graph:

You already know the meaning of edges and vertices. In this section you will learn a few more terms
associated with graph data structure.
1. Adjacent vertex: vertex (v1) is adjacent to a vertex (v2), if there is an edge (v2, v1). In case of
undirected graph v2 is also adjacent to v1, but the same is not true in case of directed graph.
2. Degree: In case of undirected graph, the degree of a vertex V is the number of vertices that are
Figure 10.1 Undirected Graph adjacent to V.

This is the simplest form of a graph that consists of 5 nodes or vertices and 7 edges. This type of graph In case of undirected graph, there is an in-degree and out-degree. In-degree for a vertex V refers to
is also known as undirected graph which means there is no direction defined for any edge. An the number of incoming edges or the number for which V is adjacent to other nodes. Out-degree for a
Edge (A, B) means that there is path or edge from A to B and B to A. vertex V refers to the number of outgoing edges or the number of edges that are adjacent to V. edges
(an edge from a vertex to itself counts in both the in and out degrees).
Another form of a graph is one which consists of directed edges rather simple edges and it is called
directed graph 3. Isolated Node: In case of un-directed graph, if a vertex V does not belong to any edge, it is called
isolated node. In case of directed graph, if there is no edge that contains vertex V as destination node,
Consider the following graph for example, it is called isolated node.

161 162

4. Path: A path of length n from vertex V0 to vertex Vn consists of n + 1 nodes such that V1 is adjacent
to V0 and V2 is adjacent to V1 and so on till Vn is adjacent to Vn-1.

5. Cycle: Cycle in itself is a path in which the first and the last node are same or V0 = Vn.
A cycle is a simple path if all vertices from V1, V2, V3, ..., Vn are distinct. In cycle path V0 will obviously
be same as Vn.

Figure 10.3 Weighted Graph

A cycle in which a vertex contains an edge to itself is called a self-loop.

Check your progress/ Self assessment questions- 1 For instance, there is an edge from node A to node C that can be represented using triplet (A, B, 5). It
means that there is an edge from node A to node B having weight 5. Weighted graphs are used to
Q1. Define graph.
____________________________________________________________________________ represent parameters like cost or distance. It is particularly useful in applications that are used to find
the minimum path between two nodes or cities.
___________________________________________________________________________

____________________________________________________________________________ 2. Labelled edge graph- Labelled edge graph in one in which each edge is assigned a label. So each

Q2. What is the difference between directed and un-directed graph?

edge in the labelled edge graph is represented using a tripled (u, v, L) which indicates that there is an
____________________________________________________________________________ edge from node u to node v having a label L.

___________________________________________________________________________
Consider the following graph for example:

____________________________________________________________________________

Q3. Define:

A. Adjacent Vertex.

B. Isolated node.

____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

10.3 Basic Types of graph

You have already seen two very basic types of graphs called the directed and undirected graphs.
In this section you will learn more graph types. Figure 10.4 Labelled edge Graph
1. Weighted graph- weighted graph in one in which each edge is assigned a weight. So each edge in
the weighted graph is represented using a tripled (u, v, w) which indicates that there is an edge from For instance, there is an edge from node a to node b that can be represented using triplet (a, b, makes).
node u to node v having a weight w. It means that there is an edge from node a to node b labelled as makes. Labelled graphs are particularly
useful in the field of computer science to represent automata states, networks etc. Like in automata,
Consider the following graph for example: How can you move between states is reflected by the labelled edges.

163 164
3. Connected and Disconnected graphs:
Connected graph is one in which there exists at least a single path between any two vertices of the graph.

Figure 10.7 Cyclic Graph

Figure 10.5 Connected Graph

In the graph shown in the figure above, there exists an cycle between nodes 4, 5 and 6. It means there
You can select any two nodes from the graph shown in the figure above and there exists a minimum of
is an path from node 4 back to itself (4, 5, 6, 4).
one path between the two.

Disconnected graph is one in which there exists at least two nodes that do not have any path to connect Acyclic graph is a simple directed graph in which there is no cycle. It means you do not have a path
them. from a node back to itself.

.
Figure 10.6 Disconnected Graph

Consider the graph shown in the figure above, there is no path between nodes 3 and 7. But there is path Figure 10.8 Acyclic Graph
between nodes 2 and 3. Such a graph is called disconnected graph.
This graph does not contain any cycle. The same cyclic graph has been turned into acyclic graph by
4. Cyclic and Acyclic graph: changing the directed edge 6 -> 4 to 4 -> 6. In this graph there is no path from any node that returns
back to the same node.
Cyclic graph is a directed graph in which there is at least one cycle. A cycle is a path from a vertex
back to itself. Cycle can be a simple cycle or looped cycle. Looped cycle is one in which there is an 10.4 Difference between tree and graph
edge from a vertex to itself. Every tree is a graph. Every graph may not be a tree.

In case of a tree, there is only one path In case of a graph, there can be more than one path
between any two nodes. between two nodes

165 166

A tree data structure does not have any loops A graph data structure can have loops or circles. For a graph with n nodes, adjacency matrix is a 2-D array of size ADJACENCY[n, n]. Each element in
or circles. the 2-D array represents whether there is an edge from node U to V or not.

Trees are less complex then graphs as Graphs are more complex in compare to trees as it can Consider the following directed graph for example,
having no cycles, no self-loops and still have cycles, loops etc
connected.

Traversal in tree data structure is done using Traversal in graph data structure is done using Depth
Pre-Order, In-Order and Post-Order First Search and in BFS and Breadth First Search
algorithms. algorithms.

Tree data structure always comprise of n-1 In case of graph data structure there is no connection
edges, where n is the number of nodes. between the number of nodes and number of edges a
graph can have.
Figure 10.9 Directed Graph
Tree is used to represent a hierarchical Graph is used to represent a network model in which
model in which there is root node at the top. nodes are connected to each other and there is no root It can be represented in memory using adjacency matrix as follows:
node like concept.

Check your progress/ Self assessment questions- 2

Q4. Give one application each of weighted and labelled edge graphs.
____________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

Q5. What is the difference between tree and graph in terms of number of edges and nodes?
____________________________________________________________________________

___________________________________________________________________________
An entry of 1 at ADJACENCY[1, 2] means that there is an edge from node 1 to node 2 and an entry of
____________________________________________________________________________ 0 at ADJACENCY[1, 5] means that there is no edge from node 1 to node 5.

Q6. What is the difference between connected and disconnected graphs?

____________________________________________________________________________ Another Example,

___________________________________________________________________________

____________________________________________________________________________

10.5 Graph representation

Graph is a non-linear and non-primary data structure just like tree data structure. It can be represented
in memory using either adjacency matrix or adjacency list.

10.5.1 Adjacency Matrix

167 168
 Figure 10.10 Directed Graph Concept of linked list is used to represent the graph in memory using adjacency list. Two LISTS are
maintained to represent the graph using adjacency list.

a. Node List: It consists of all nodes in the graphs. As and when the node is created it is added to
node list. The list represents the order in which the nodes are added to the graph, but it does not represent
the link or edges between the graph.

Figure 10.12 Structure of node in node list

Each node in the node list consists of three members: NODE, NEXT and ADJ. NODE represents the
name or key value of node. NEXT points to the node created next to the current node in the graph.

Last node created in graph consists NULL in NEXT member. ADJ points to the adjacency list for the
node.
Adjacency matrix can also be used to represent the weighted graph as follows: b. Edge List: ADJ member for each node in the node list points to a edge list if there are nodes
adjacent to the current node.

Figure 10.13 Structure of node in edge list

Each node in the edge list consists of two members: DEST and LINK. DEST points to the node in the
node list which is adjacent to the current node and LINK points to the next edge if there is another

Figure 10.11 Weighted Graph adjacent node.

It can be represented in memory using adjacency matrix as follows: Consider the following directed graph:

10.5.2 Adjacency List

169 170

Figure 10.16 Directed graph

Figure 10.14 Directed graph

Lets us assume that nodes were created in the order 1, 2, 3, 4, 5, 6 and 7.

Hence the node and edge list will look like the following:

Figure 10.17 Adjacency List representation for directed graph in figure 10.16

10.6 Applications of Graph

1. Social network graphs: The social networking sites and networks have become very popular.
Data structure plays an important role in maintaining the size and complexities of these social networks.
Graph plays an important role. The relationship between the members, communication between the
members, sharing of data or topic among the members, everything is maintained with the help of graphs.
2. Transportation networks: GPS has become a necessity. People are able to move to new places

Figure 10.15 Adjacency List representation for directed graph in figure 10.14 Another without the fear of getting lost. These transportation networks are maintained with the help of graphs.

Example: You are able to find routes between two cities and also able to select a route of your choice based on
some parameters.
3. Utility graphs: Utility graphs help to reduce the costs to build infrastructure. Some of the
popular examples of utility graphs are power grid, Internet, the water networks, etc. Nodes or vertices
represent the communication points and the edges represent the transportation medium like wires or

171 172
pipes. Creating and managing utility graphs are important from the point of view of creating new quality
____________________________________________________________________________
infrastructure at minimum cost.
4. Link Graphs: Internet has become so popular today that it has not just reached the homes of
billions, but to the pockets and hands of billions. Everyone is surfing on net and finding new 10.7 Summary
information. Graphs play an important role here too. Each web page acts as a node or vertex of the Graph is a non-linear data structure. You may define a graph as follows:
graph and each hyperlink acts as a directed edge. A graph G=(V,E) consists of
5. Network packet traffic graphs: With the growing popularity of internet, comes the challenge a. set of vertices or nodes (v)
to address the issues related to it. Graph for network traffic packets consists of Internet protocol b. and a set of edges (E).
addresses as nodes and packets as edges. Tracking criminal activities or understanding of network Undirected graph is one that does not have directions defined for any edge. An Edge (A, B) means
security issues become easy with NPT graphs. Such graphs are used for analyzing network that there is path or edge from A to B and B to A. Graph that consists of directed edges rather simple
6. Scene Graphs: How can you forget entertainment. Entertainment in the form of video games edges and it is called directed graph. An edge 1->2 in directed graph means that there is an edge or
or graphics in cartoons. Graphs are used to represent the spatial relationships between objects in a scene. path from node 1 to node 2, but the vice versa is not true.
Only graphs can manage the speed at which the scenes change and help display the new scene without Graph can be represented in memory using either adjacency matrix or adjacency list.
any delay. For a graph with n nodes, adjacency matrix is a 2-D array of size ADJACENCY[n, n]. Each element in
7. Finite state machine graph: Graphs are used to define the finite state machine or automata. the 2-D array represents whether there is an edge from node U to V or not. An entry of 1 at
Automata is expressed in terms of states. States include initial and final state. Labelled edge graph is ADJACENCY[1, 2] means that there is an edge from node 1 to node 2 and an entry of 0 at
used to show the transition between states. Various states are shown as vertices or nodes in the finite ADJACENCY[1, 5] means that there is no edge from node 1 to node 5.
state machine graph and transition rules as edges. Two LIST'S are maintained to represent the graph using adjacency list. Node List consists of all nodes
8. Graphs in compilers: Graphs play an important role in compilers. Compiler as a whole is in the graphs. As and when the node is created it is added to node list. Each node in the node list consists
divided into number of phases and graphs play important role in most of these phases. Graphs are used of three members: NODE, NEXT and ADJ. . NODE represents the name or key value of node. NEXT
in data flow analysis, register allocation and many other functions. Graphs are also used for query points to the node created next to the current node in the graph. Last node created in graph consists
optimization compilers in database languages. NULL in NEXT member. ADJ points to the adjacency list for the node.
ADJ member for each node in the node list points to a Edge list if there are nodes adjacent to the current
Check your progress/ Self assessment questions- 3 node. Each node in the edge list consists of two members: DEST and LINK. DEST points to the node
Q7. What is adjacency matrix? in the node list which is adjacent to the current node and LINK points to the next edge if there is another
____________________________________________________________________________ adjacent node.
___________________________________________________________________________ Graphs have a number of applications in the form of:
1. Social network graphs
____________________________________________________________________________
2. Transportation networks
Q8. What is node list in adjacency list representation of graph? 3. Utility graphs
____________________________________________________________________________
4. Link Graphs
___________________________________________________________________________ 5. Network packet traffic graphs

____________________________________________________________________________ 6. Scene Graphs

7. Finite state machine graph
Q9. Explain the concept of link graphs.
____________________________________________________________________________
8. Graphs in compilers

___________________________________________________________________________
10.8 Glossary
173 174

Graph- A non-linear Data structure that consists of a set of vertices (v) and a set of edges (E) to connect particularly useful in the field of computer science to represent automata states, networks etc. Like in
the nodes. automata: what How can you move between states is reflected by the labelled edges.
Weighted graph- weighted graph in one in which each edge is assigned a weight
Directed Graph- That consists of directed edges between two vertices. An edge 1->2 in directed graph 5. Tree data structure always comprise of n-1 edges, where n is the number of nodes. In case of
means that there is an edge or path from node 1 to node 2, but the vice versa is not true graph data structure there is no connection between the number of nodes and number of edges a graph
Undirected Graph- That consists of simple undirected edges between 2 vertices. An Edge (A, B) means can have.
that there is path or edge from A to B and B to A.
Labelled edge graph- Labelled edge graph in one in which each edge is assigned a label 6. Connected graph is one in which there exists at least a single path between any two vertices of
Connected graph is one in which there exists at least a single path between any two vertices of the graph. the graph. Disconnected graph is one in which there exists at least two nodes that do not have any path
Disconnected graph is one in which there exists at least two nodes that do not have any path to connect to connect them
them.
7. For a graph with n nodes, adjacency matrix is a 2-D array of size ADJACENCY[n, n]. Each
Cyclic graph is a directed graph in which there is at least one cycle. A cycle is a path from a vertex back
element in the 2-D array represents whether there is an edge from node U to V or not. An entry of 1 at
to itself.
ADJACENCY[X, Y] means that there is an edge from node X to node Y and an entry of 0 at
Acyclic graph is a simple directed graph in which there is no cycle. It means you do not have a path
ADJACENCY[X, Y] means that there is no edge from node X to node Y.
from a node back to itself.
Tree- Tree is a non-linear data structure used to represent a hierarchical model in which there is root
8. Node List consists of all nodes in the graphs. As and when the node is created it is added to
node at the top.
node list. Each node in the node list consists of three members: NODE, NEXT and ADJ. . NODE
represents the name or key value of node. NEXT points to the node created next to the current node in
10.9 Answers to check your progress/self assessment questions
the graph. Last node created in graph consists NULL in NEXT member. ADJ points to the adjacency
1. A graph G = (V,E) is a non-linear data structure that consists of:
list for the node.
a. Set of vertices or nodes (v)
b. and a set of edges (E) that connects nodes.
9. Internet has become so popular today that it has not just reached the homes of billions, but to
the pockets and hands of billions. Everyone is surfing on net and finding new information. Graphs play
2. An Edge (A, B) in an un-directed graph means that there is path or edge from A to B and B to A,
an important role here too. Each web page acts as a node or vertex of the graph and each hyperlink acts
where as in case of directed graph an edge (A -> B) means there is an edge from A to B but not from
as a directed edge
B to A.

3.
10.10 References/ Suggested Readings
A. Adjacent vertex: vertex (v1) is adjacent to a vertex (v2), if there is an edge (v2, v1). In case of
1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill
undirected graph v2 is also adjacent to v1, but the same is not true in case of directed graph.
2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage
B. Isolated Node: In case of un-directed graph, if a vertex V does not belong to any edge, it is
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education.
called isolated node. In case of directed graph, if there is no edge that contains vertex V as destination
node, it is called isolated node.
10.11 Model questions
1. Explain graph with the help of an example.
4. Weighted graphs are used to represent parameters like cost or distance. It is particularly useful
2. Explain various types of graphs.
in applications that are used to find the minimum path between two nodes or cities. Labelled graphs are
3. List various application of graph.

175 176
4. Explain adjacency matrix representation of graph. In the last lesson of this SLM you learned about the fundamentals of graph data structure and how it is
5. Explain adjacency list representation of graph. different from tree data structure. You also learned about different types of graphs and how the graph
6. Explain various differences between graph and tree data structure. is represented in memory using adjacency matrix and adjacency list. Now you are ready to learn various
operations that are possible on graph. In this lesson you will first of all learn the most basic operations
like traverse, insert and delete on graph data structure. In the end you will come across one of the most
popular application of graph and that is to find the shortest path between two vertices in graph. For that,
you will learn one of the most popular shortest path algorithm called Dijkstra's shortest path algorithm.
I am sure that you will enjoy reading this lesson.

11.2 Traversing
Traversing is the most basic operation on any data structure and important one when it comes to
Lesson- 11 Graph Operations nonlinear data structures. As you learned earlier in this SLM, traverse operation on tree was slightly
Structure complicated than traverse operation on any of the linear data structures.
11.0 Objective There are two techniques widely followed to traverse the graph data structure namely:
11.1 Introduction 1. Breadth First Search.
11.2 Traversing 2. Depth First Search
11.2.1 Breadth First Search
11.2.2 Depth First Search 11.2.1 Breadth First Search
11.3 Inserting Breadth first search traverses the entire graph with the help of linear data structure called queue.
11.4 Deleting Traverse operation on data structure however is not able to visit the isolated nodes in the graph. The
11.5 Dijkstra’s Shortest Path Algorithm approach of breadth first search is to process the starting node and add all adjacent nodes of the starting
11.6 Summary node in the queue. A node is deleted from the queue and is processed. Then its adjacent nodes are
11.7 Glossary inserted to the rear of the queue. The process is repeated until the queue becomes empty. The approach
11.8 Answers to check your progress/self assessment questions is called breadth first search because all adjacent nodes to the entire breadth of the starting node are
11.9 References/ Suggested Readings processed first. It is then followed by the adjacent nodes of all adjacent nodes of starting node and so
11.10 Model questions on.

11.0 Objective To avoid processing a node twice or even considering a node for processing twice, each node goes
After studying this lesson, students will be able to: through three states:
1. Explain Depth First Search traversal algorithm.
2. Explain Breadth First Search traversal algorithm. STATUS = 1, The initial state of node.
3. Discuss insert operation on graph. STATUS = 2, Node is waiting in the Queue.
4. Discuss delete operation on graph. STATUS =3, The node has been processed.
5. Describe Dijkstra's shortest path algorithm.
ALGORITHM BREADTH_FS(TRAVERSING GRAPH) It traverses a graph from starting
node A.
11.1 Introduction

177 178

1. Initialize all nodes with STATUS = 1, i.e. initial state. F 1

2. Put Node A onto Queue and change the status of the same to 2, i.e. STATUS =2, waiting state. G 1

3. Repeat until queue is empty

Step 2
4. Remove the FRONT node K from Queue, Apply process to it and also change the status Queue: A
of node from 2 to 3, i.e. STATUS = 3, PROCESSED.
Processed:
5. Add all nodes in the Adjacency list of K to Queue whose STATUS is still 1, i.e. initial state, and
also change the status of each node from 1 to 2. Node Status

[End of Step 3 Loop] A 2

B 1
6. Exit
C 1

For example, D 1
Consider the following Graph E 1
F 1
G 1

Step 3
Queue: B
Processed: A

Node Status
A 3
B 2
Figure 11.1 Directed Graph
C 1
D 1
Let the starting Node be A, Following is the step by step processing of each node starting from A.
E 1
Step 1
F 1
Queue:
G 1
Processed:

Node Status Step 4

A 1 Queue: C D

B 1 Processed: A B

C 1
Node Status
D 1
A 3
E 1
B 3

179 180
C 2 Node Status
D 2 A 3
E 1 B 3
F 1 C 3
G 1 D 3
E 2
Step 5 F 2
Queue: D G 3
Processed: A B C

Step 8
Node Status
Queue: F
A 3
Processed: A B C D G E
B 3
C 3 Node Status
D 2 A 3
E 1 B 3
F 1 C 3
G 1 D 3
E 3
Step 6 F 2
Queue: G G 3
Processed: A B C D

Step 8
Node Status
Queue:
A 3
Processed: A B C D G E F
B 3
C 3 Node Status
D 3 A 3
E 1 B 3
F 1 C 3
G 2 D 3
E 3
Step 7 F 3
Queue: E F G 3
Processed: A B C D G

181 182

Check your progress/ Self assessment questions- 1 ALGORITHM DEPTH_FS(TRAVERSING GRAPH) It traverses a graph from starting node
A.
Q1. Which two techniques are used to traverse graph? 1. Initialize all nodes with STATUS = 1, i.e. initial state.

____________________________________________________________________________ 2. Put Node A onto Stack and change the status of the same to 2, i.e. STATUS =2, waiting state.

___________________________________________________________________________ 3. Repeat until Stack is empty

____________________________________________________________________________ 4. POP the TOP node K from Stack, Apply process to it and also change the status of node
from 2 to 3, i.e. STATUS = 3, PROCESSED.

Q2. Explain the approach of breadth first search traversal algorithm for graph. 5. PUSH all nodes in the Adjacency list of K to Stack whose STATUS is still 1, i.e. initial state, and
also change the status of each node from 1 to 2.
____________________________________________________________________________
[End of Step 3 Loop]
___________________________________________________________________________ 6. Exit

____________________________________________________________________________ Q3.
What are the different states or status each node in graph goes through during breadth first search
traversal algorithm? For example,
Consider the following Graph

___________________________________________________________________________

___________________________________________________________________________

____________________________________________________________________________

11.2.2 Depth First Search

Depth first search traverses the entire graph with the help of linear data structure called stack. Stack
follows the approach of LIFO. The approach of depth first search is to process the starting node and
PUSH all adjacent nodes of the starting node in the stack. A node is POPED from the stack and is Figure 11.2 Directed graph

processed. Then its adjacent nodes are PUSHED to the stack. The process is repeated until the stack
becomes empty. Step 1 Stack:
Processed:

The approach is called depth first search because one path from the starting node is processed to the
Node Status
entire depth first followed by the second path and so on.
A 1
B 1
To avoid processing a node twice or even considering a node for processing twice even in case of depth
first search, each node goes through three states: C 1
D 1
STATUS = 1, The initial state OF NODE. E 1
STATUS = 2, Node is waiting in the STACK. F 1
STATUS =3, The node has been processed. G 1

183 184
Step 2 F 1
Stack: A G 1
Processed:

Step 5
Node Status
Stack: C E G
A 2
Processed: A B D
B 1 Node Status
C 1 A 3
D 1 B 3
E 1 C 2
F 1 D 3
G 1 E 2
F 1
Step 3 G 2
Stack: B
Processed: A Step 6
Stack: C E
Node Status
Processed: A B D G
A 3 Node Status
B 2 A 3
C 1 B 3
D 1 C 2
E 1 D 3
F 1 E 2
G 1 F 1
G 3
Step 4
Stack: C E D Step 7
Processed: A B Stack: C F
Processed: A B D G E
Node Status Node Status
A 3 A 3
B 3 B 3
C 2 C 2
D 2 D 3
E 2

185 186

E 3
Q5. Why the second technique of graph traversal using stack is called depth first search?
F 2
G 3 ____________________________________________________________________________

___________________________________________________________________________
Step 8
____________________________________________________________________________
Stack: C
Processed: A B D G E F
Node Status 11.3 Inserting
A 3 Insert operation on graph can be divided into two tasks. The first task is to add the new node to the node
B 3 list and the second task is to add edges starting from the new node and ending at the new node in the
C 2 edge lists.
D 3
E 3 INSERTNODE_GRAPH (ALGORITHM INSERTS NODE in the graph) Node KEY is added to the
beginning of the node list of the GRAPH. START points to the last node added to the graph.
F 3
G 3 1. if AVAILNODE == NULL then, // AVAILNODE
is empty
2. Print "Overflow" 3. Exit.
[End of step 1 if statement]
Step 9 4. Set NEW = AVAILNODE //assign free node to NEW
Stack: 5. Set AVAILNODE = LINK[AVAILNODE] //set 2nd node as 1st node
6. Set ADJ[NEW] = NULL //no nodes adjacent to new node yet
Processed: A B D G E F C 7. Set NODE[NEW] = KEY
Node Status 8. NEXT[NEW] = START
9. START = NEW //START now points to the NEW node
A 3 10. Exit.
B 3
INSERTEDGE_GRAPH (ALGORITHM INSERTS EDGE in the graph) an edge from node A to node
C 3
B is added. It is done by adding an edge in the edge list of node A pointing to location of node
D 3 B.

E 3 1. if AVAILEDGE == NULL then, //

AVAILEDGE is empty
F 3
2. Print "Overflow" 3. Exit.
G 3 [End of step 1 if statement]
4. Set NEW = AVAILEDGE //assign free node to NEW
5. Set AVAILEDGE = LINK[AVAILEDGE] //set 2nd node as 1st node
Check your progress/ Self assessment questions- 2 6. Set DEST[NEW] = LOCB //edge points to LOCB
7. Set LINK[NEW] = ADJ[LOCA]
Q4. Which data structure is used to assist the depth first search traversal algorithm and how it different 8. ADJ[LOCA] = NEW
from queue? 9. Exit.

____________________________________________________________________________ 11.4 Deleting

___________________________________________________________________________
Deleting a node is also divided into two tasks. Before you delete the node, the edges in the edge lists
starting from the node to be deleted and ending at the node to be deleted are removed first and then the
____________________________________________________________________________
actual node is deleted.

187 188
DELETENODE_GRAPH (ALGORITHM DELETES NODE in the graph) Node KEY is deleted from the Following is an example is simple greedy approach.
node list of the GRAPH.
Consider the following graph
1. Find the location of node KEY to be deleted in the graph.
2. Delete all edges that end at KEY; it means delete edges from the adjacency list of all nodes in the
node list that points to location of KEY and add the edges to AVAILEDGE list.
3. Delete all edges that begin from KEY; it means delete all edges in the adjacency list of node KEY
and add the edges to AVAILEDGE list.
4. Delete node KEY from the node list of the graph.
5. End

DELETEEDGE_GRAPH (ALGORITHM DELETES EDGE in the graph) Edge from location of node A
to location of node B is deleted.
Figure 11.3 Graph
1. Find the location of node A and node B in the graph.
2. Delete the edge that begin from location of A and ends at location of B; it means delete the edge in Suppose you want to go from node F to node D.
the adjacency list of node A pointing to node B and add it to AVAILEDGE list.
3. End Select the edge or road with minimum weight. It is A -> B with 2 weight. Hence the same is selected.

11.5 Dijkstra’s Shortest Path Algorithm

Computing the shortest path between two nodes or vertices is the most important application of graph
data structure. You can compute the shortest path between two vertices only if the graph is a weighted
graph. You already know that in case of tree data structure, there is only one path between two vertices.
But in case of graph data structure, you can have multiple paths to reach a node from a specified node.

In practical application of graph, finding the shortest path or route to minimize the cost is very important.
Suppose you are planning a trip and going to a city for the first time. You don't know the route. Also it
may be possible that more than one route exist. You for very obvious reason would like to select the
shortest route or path from the source to destination. Applications like google map and GPS systems Next select the edge or road from remaining edges with minimum weight. It is C -> D with 3 weight.
allow you to select your route from source to destination on basis of various parameters. Hence the same is selected.
From among those parameters, of the most preferred parameter is shortest distance.

Dijkstra’s algorithm is very popular algorithm to finds the shortest path between two nodes. Dijkstra’s
algorithm is an example of greedy algorithm. The idea behind the concept of greedy algorithm is that
you can make progress to the destination node by always choosing the best choice (shortest edge or
path) available at each point. You could design an algorithm that selects paths from the graph based on
shortest path length. Once you have a path between the source to destination node, you simply stop the
process of selecting paths and then compute the total path length between the source and destination
Next select the edge or road from remaining edges with minimum weight. It is F -> E with 4 weight.
nodes. It does not produce the most optimal result. It is so because it does not take into account the
Hence the same is selected.
total sum of the paths needed to join the two nodes.
A simple greedy approach selects a path based on shortest distances between two cities or nodes.
The path is not guaranteed to be optimal, but a path is selected in less time.

189 190

Figure 11.4 Graph

Next select the edge or road from remaining edges with minimum weight. It is G -> C with 5 weight. Consider the graph given in figure 11.4 and suppose you want to find shortest path between nodes A
Hence the same is selected. and D. If we assume that any node XYZ is part of the complete shortest path, then not only is the length
between A and XYZ optimal, but all other nodes before XYZ in the shortest path are also optimal with
respect to A.

The real benefit of Dijkstra's algorithm is that when you find the shortest path between two nodes, you
end up finding shortest path from source node to all nodes that are part of the overall shortest path.

SHORTESTPATH_DJIKSTRA (ALGORITHM FINDS SHORTEST PATH BETWEEN TWO NODES

in the graph) Given a source node and destination node in the graph, the algorithm finds the
shortest path between the two nodes.
Next select the edge or road from remaining edges with minimum weight. It is E -> G with 6 weight.
1. Set the distance value for source node to 0, and all remaining nodes in the graph to ∞.
Hence the same is selected.
2. Mark all nodes in the graph as non-finalized and set the source node as Current node.

[Link] all non-finalized adjacent nodes of current node , using current's distance, re-compute their
distances from source node and if this distance is less than the previously computed distance,
overwrite it.

4. Mark the current node as finalized.

(Once the node has been finalized, its distance value is optimal and is not checked again).

[Link] the next non-finalized node in the graph as current node with the smallest distance.

Now you have path from F to D with path length = 4 + 6 + 5 + 3 = 18. If you look at the graph carefully,
it is not the optimal path.

Dijkstra’s Algorithm

191 192
 11.6 Summary
Traversing is the most basic operation on any data structure and important one when it comes to
nonlinear data structures. There are two techniques widely followed to traverse the graph data structure
namely:
1. Breadth First Search.
2. Depth First Search
Breadth first search traverses the entire graph with the help of linear data structure called queue. The
approach of breadth first search is to process the starting node and add all adjacent nodes of the starting
node in the queue. A node is deleted from the queue and is processed. Then its adjacent nodes are
inserted to the rear of the queue. The process is repeated until the queue becomes empty. Depth first
search traverses the entire graph with the help of linear data structure called stack. Stack follows the
approach of LIFO. The approach of depth first search is to process the starting node and PUSH all
adjacent nodes of the starting node in the stack. A node is POPED from the stack and is processed.
Then its adjacent nodes are PUSHED to the rear of the queue. The process is repeated until the stack
becomes empty.
Insert operation on graph can be divided into two tasks. The first task is to add the new node to the node
list and the second task is to add edges starting from the new node and ending at the new node in the
edge lists. Deleting a node is also divided into two tasks. Before you delete the node, the edges in the
edge lists starting from the node to be deleted and ending to the node to be deleted are removed first
and then the actual node is deleted.
In practical application of graph, finding the shortest path or route to minimize the cost is very important.
The idea behind the concept of greedy algorithm is that you can make progress to the destination node
Figure 11.5 Steps to compute the shortest bath between Node A and D. by always choosing the best choice (shortest edge or path) available at each point. The real benefit of
Check your progress/ Self assessment questions- 3 Dijkstra's algorithm is that when you find the shortest path between two nodes, you end up finding
shortest path from source node to all nodes that are part of the overall shortest path. For example, if the
Q6. What is the approach of simple greedy technique to find shortest path between two nodes?
shortest path returned by Dijkstra's algorithm from node A to D is (A, B, C, D), it means that shortest
____________________________________________________________________________
path from node A to C has also been found which is (A, B, C).
___________________________________________________________________________
11.7 Glossary
____________________________________________________________________________
Traverse- Visiting each element of the data structure exactly once.
Breadth First Search- It is graph traversal technique in which all adjacent nodes of the start node to its
Q7. What is the advantage of using Dijkstra's algorithm to find shortest path?
entire breadth are processed first. It is then followed by the adjacent nodes of all adjacent nodes of
____________________________________________________________________________ starting node and so on.

___________________________________________________________________________
Depth First Search- - It is graph traversal technique in which one path from the starting node is processed
to the entire depth first followed by the second path and so on.
____________________________________________________________________________

193 194

Queue- FIFO based data structure in which elements are inserted at one end called rear and deleted from
other end called front. 11.9 References/ Suggested Readings
Stack- LIFO based data structure in which element are PUSHED and POPED from one one only called 1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill
the TOP of stack. 2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education.
11.8 Answers to check your progress/self assessment questions
1. There are two techniques widely followed to traverse the graph data structure namely: a. 11.10 Model questions
Breadth First Search. 1. Write the depth first search algorithm to traverse a graph.
b. Depth First Search 2. Explain the concept of breadth first search traversal technique by taking example of a graph with
minimum 8 nodes.
2. The approach of breadth first search is to process the starting node and add all adjacent nodes of the 3. Write the algorithm to insert a node in graph.
starting node in the queue. A node is deleted from the queue and is processed. Then its adjacent 4. Write Dijkstra's shortest path algorithm.
nodes are inserted to the rear of the queue. The process is repeated until the queue becomes empty. 5. Write the algorithm to delete a node from graph.

3. Each node goes through following three states during the breadth first search traversal algorithm:
STATUS = 1, The initial state OF NODE.
STATUS = 2, Node is waiting in the Queue.
STATUS =3, The node has been processed.

4. Stack is used to assist the depth first search traversal algorithm. It is a LIFO based data structure in
which elements are inserted and removed from one end only against queue which is a FIFO based
data structure in which element is inserted at one end called rear and inserted at other end called front
of queue.

5. The approach of graph traversal using stack is called depth first search because one path from the
starting node is processed to the entire depth first followed by the second path and so on.
Lesson 12 Sorting 1
Structure of the lesson
6. The idea behind the concept of greedy algorithm is that you can make progress to the destination
12.0 Objective
node by always choosing the best choice (shortest edge or path) available at each point. Greedy
12.1 Introduction
algorithm selects paths from the graph based on shortest path length. Once you have a path between
12.2 Ordering
the source to destination node, you simply stop the process of selecting paths and then compute the
12.3 Stability
total path length between the source and destination nodes.
12.4 Bubble Sort
12.4.1 Bubble Sort Algorithm
7. The real benefit of Dijkstra's algorithm is that when you find the shortest path between two nodes,
12.4.2 Bubble Sort Example
you end up finding shortest path from source node to all nodes that are part of the overall shortest
12.4.3 Complexity Bubble Sort
path. For example, if the shortest path returned by Dijkstra's algorithm from node A to D is (A, B, C,
12.5 Selection Sort
D), it means that shortest path from node A to C has also been found which is (A, B, C).

195 196
 12.5.1 Selection Sort Algorithm 2. Descending order
12.5.2 Selection Sort Example
12.5.3 Complexity Selection Sort Ascending order is the arrangement of elements of the list in non-decreasing order.
12.6 Insertion Sort Such as, A1 <= A2 <= A3 ...... <= An-1 <= An
12.6.1 Insertion Sort Algorithm
12.6.2 Insertion Sort Example Some of the examples of ascending order are as follows:
12.6.3 Complexity Insertion Sort 1. 52, 52, 67, 68, 68, 90
12.7 Summary 2. 52, 54, 67, 67, 67
12.8 Glossary
12.9 Answers to check your progress/self assessment questions Descending order is the arrangement of elements of the list in non-increasing order.
12.10 References/ Suggested Readings Such as, A1 >= A2 >= A3 ...... >= An-1 >= An
12.11 Model questions
Some of the examples of descending order are as follows:
12.0 Objective 1. 23, 34, 66, 66, 67, 67, 67
After studying this lesson, students will be able to: 2. 23, 23, 23, 45
1. Discuss the concept of sorting.
2. Explain selection sort. Sorting comes after the ordering. Once the rules have been specified, the process of arranging the
3. Explain bubble sort elements according to that order is called sorting.
4. Explain Insertion sort.
5. Implement all three sorting algorithms. 12.3 Stability
Stability in sorting, also known as stable-sorting: A sorting algorithm is understood to be stable if
12.1 Introduction two objects in the input list that have equal keys appear in the same order in sorted output list as they
Sorting is a vital operation of data structure. Sorting operations help to simplify other data structure appear in the input unsorted list. Not all sorting algorithms are stable-sorting algorithms. The sorting
operations like, insert, delete and search. Searching in sorted list is much faster than searching in algorithms that are not stable also produce correct results. Stability is not the measure of correctness of
unsorted list. Sorting refers to systematic ordering (rules for sequencing) of element in a list. A sorting algorithm.
number of sorting algorithms have evolved over time. Selection of sorting algorithm can be based on
type of data available, storage space and most importantly the time complexity of each algorithm. Some of the examples stable sorting algorithms are Insertion sort, Merge Sort, Bubble Sort and some
examples of sorting algorithms are Heap Sort, Quick Sort, etc.
12.2 Ordering
Sorting refers to a systematic arrangement of elements in a list. Sorting is of two types: Consider, for example a list of 7 words:
1. Ordering: Arrangement of elements in some sequence. white, green, red, black, orange, yellow, blue
2. Categorizing: Arrangement of similar elements in a group or cluster.

If you apply stable-sorting based on the first letter, the sorted output list will be as follows:
In this lesson you will be studying all concepts relating to ordering and not categorization. black blue green orange red white yellow
Ordering specifies the rules that decides which element will come before or after a given element in the
list. Ordering can be of two types In case you apply unstable algorithm, there is a possibility that blue may come before black. It does not
1. Ascending order and break the rule of ordering, but it changes the order in which they appeared in the input list.

197 198

Check your progress/ Self assessment questions Step N-1 (only one comparison is made in this step as the un-sorted sub-list consists of 2 elements only)
Compare element A[1] and A[2] and arrange them in the order such that A[1] <= A[2].
Q1. Define sorting.
____________________________________________________________________________
In the end after N-1 steps or passes and total of ( (N (N-1))/2 comparisons, the list is sorted.
___________________________________________________________________________

____________________________________________________________________________
12.4.1 Bubble Sort Algorithm
Q2. Explain ascending ordering with an example.
____________________________________________________________________________
ALGORITHM BUBBLE_SORT(SORTING AN ARRAY) It sorts an un-sorted array with N
elements.
___________________________________________________________________________

____________________________________________________________________________
1. Repeat For J = 1 to N-1 // n-1 passes
Q3. Define stable-sorting.
2. Repeat For K = 1 to N-J // number of comparisons in each pass
____________________________________________________________________________
3. If (A[K] > A[K+1]) Then // if the element on left is greater
___________________________________________________________________________

4. Swap A[K] and A[K+1]

____________________________________________________________________________

[End of If]
12.4 Bubble Sort
[End of Step 2 For Loop]
Process of bubble sorting involves N-1 steps where N stands for number of elements in the list. With
N-1 comparisons in step 1, number of comparisons keep decreasing by 1 with every step. [End of Step 1 For Loop]
Bubble sort algorithm works as follows ASCENDING ORDER]: 5. Exit
Step 1 Compare element A[1] and A[2] and arrange them in the order such that A[1] <= A[2]. Further
compare A[2] and A[3] and arrange them in the order such that A[2] <= A[3]. Repeat the process till
12.4.2 Bubble Sort Example
the last element, i.e. compare A[N-1] and A[N] and arrange them in the order such that A[N-1] <=
For, Example consider the following array with N= 6 elements
A[N].

Value 12 67 54 34 28 47
Total of N-1 comparisons are made and the largest element in the list is placed at index position
Index 1 2 3 4 5 6
N. Now you are left with N-1 unsorted elements.

Step 2 Again Compare element A[1] and A[2] and arrange them in the order such that A[1] <= A[2]. Pass 1 j=1, Number of

Further compare A[2] and A[3] and arrange them in the order such that A[2] <= A[3]. Repeat the process comparisons 5

till the last element which in step 2 is N-1, i.e. compare A[N-2] and A[N-1] and arrange them in the
Value 12 67 54 34 28 47
order such that A[N-2] <= A[N-1].
Index 1 2 3 4 5 6
Total of N-2 comparisons are made and the largest element in the sub-list of N-1 elements is placed
at index position N-1. Now you are left with N-2 unsorted elements. K 1

.......
Value 12 67 54 34 28 47
.......

199 200
Index 1 2 3 4 5 6 Index 1 2 3 4 5 6

K 2 K 2

Value 12 54 67 34 28 47 Value 12 34 54 28 47 67

Index 1 2 3 4 5 6 Index 1 2 3 4 5 6

K 3 K 3

Value 12 54 34 67 28 47 Value 12 34 28 54 47 67

Index 1 2 3 4 5 6 Index 1 2 3 4 5 6

K 4 K 4

Value 12 54 34 28 67 47 Value 12 34 28 47 54 67

Index 1 2 3 4 5 6 Index 1 2 3 4 5 6

K 5
Array after pass 2 looks as shown above. the last two elements are sorted and placed at the end of
Value 12 54 34 28 47 67 the array.

Index 1 2 3 4 5 6 Pass 3 j=3, Number of

comparisons 3
Array after pass 1 looks as shown above. the last element is largest and placed at the end of the
array. Value 12 34 28 47 54 67

Index 1 2 3 4 5 6

Pass 2 K 1
j=2, Number of comparisons 4
Value 12 34 28 47 54 67
Value 12 54 34 28 47 67
Index 1 2 3 4 5 6
Index 1 2 3 4 5 6
K 2
K 1

Value 12 28 34 47 54 67
Value 12 54 34 28 47 67

Index 1 2 3 4 5 6

201 202

K 3 K 1

Value 12 28 34 47 54 67 Value 12 28 34 47 54 67

Index 1 2 3 4 5 6 Index 1 2 3 4 5 6

Array after pass 3 looks as shown above. the last three elements are sorted and placed at the end After pass 5, only one element is left and all other elements are sorted and placed after the first
of the array. element in the sorted form. There is no need to sort the first element, as it is the shortest element
and list with single element is always sorted.

Pass 4 12.4.3 Complexity Bubble Sort

j=4, Number of comparisons 2 Bubble sort complexity in terms on number of comparisons.

Value 12 28 34 47 54 67 No. of comparisons made in step 1 = N-1

No. of comparisons made in step 2 = N-2
Index 1 2 3 4 5 6 No. of comparisons made in step 3 = N-3
K 1 .....
.......
Value 12 28 34 47 54 67 No. of comparisons made in step N-2 = 2
No. of comparisons made in step N-1 = 1
Index 1 2 3 4 5 6

K 2 Hence, f(n) = (n-1) + (n-2) + ..... + 2 + 1 = (N(N-1))/2 = (N2 - N)/2

Big Oh Notation = O(n2)

Value 12 28 34 47 54 67
12.5 Selection Sort
Index 1 2 3 4 5 6 Selection sort works on the principle of finding the smallest element in the list and interchanging the
same with the first element in the list. Hence the first element is placed at its correct position and then
the same process is applied to the remaining N-1 elements starting from index position two and so on
Array after pass 4 looks as shown above. the last four elements are sorted and placed at the end
of the array. till N-1. Once the N-1 elements are placed at their correct position, the last element automatically is
placed at its correct position too.

Pass 5
Step 1 Find the location LOC of the smallest element in the list and interchange the element A[LOC]
j=5, Number of comparisons 1
with A[1]. Hence the first element is sorted.
Value 12 28 34 47 54 67
Step 2 Find the location LOC of the smallest element in the sub-list and interchange the element
Index 1 2 3 4 5 6 A[LOC] with A[2]. Hence the first two elements are sorted.
.................................

203 204
.................................
Value 54 67 19 24 39 20

Step N-1 Find the location LOC of the smallest element in the sub-list of 2 elements and interchange
the element A[LOC] with A[N-1]. Hence the N-1 elements are sorted. Index 1 2 3 4 5 6
K MIN=1 3
With this the sorting is complete.
Value 54 67 19 24 39 20

12.5.1 Selection Sort Algorithm

Index 1 2 3 4 5 6
ALGORITHM SELECTION_SORT(SORTING AN ARRAY) It sorts an un-sorted array with K MIN=3 4
N elements. 1. Repeat For J = 1 to N

2. Set MIN = J Value 54 67 19 24 39 20

3. Repeat For K = J+1 to N

Index 1 2 3 4 5 6
4. If (A[K] < A[MIN]) Then K MIN=3 5

5. Set MIN = K
Value 54 67 19 24 39 20
[End of If]

[End of Step 3 For Loop] Index 1 2 3 4 5 6

6. Interchange A[J] and A[MIN] K MIN=3 6

[End of Step 1 For Loop]

Value 54 67 19 24 39 20
7. Exit
Index 1 2 3 4 5 6

12.5.2 Selection Sort Example K MIN=3

For, Example consider the following array with N= 6 elements
Interchange A[1] with A[3],
Value 54 67 19 24 39 20 Value 19 67 54 24 39 20
Index 1 2 3 4 5 6
Index 1 2 3 4 5 6
Pass 1 j=1, MIN=1, Number of
comparisons 5 After pass 1, the shortest element is sorted and placed at the first position in the array

Value 54 67 19 24 39 20 Pass 2 j=2, MIN=2, Number of

comparisons 4
Index 1 2 3 4 5 6
K MIN=1 2 Value 19 67 54 24 39 20

205 206

Index 1 2 3 4 5 6
Index 1 2 3 4 5 6 K MIN=3 4

K MIN=2 3
Value 19 20 54 24 39 67
Value 19 67 54 24 39 20
Index 1 2 3 4 5 6
Index 1 2 3 4 5 6 K MIN=4 5

K MIN=3 4
Value 19 20 54 24 39 67
Value 19 67 54 24 39 20
Index 1 2 3 4 5 6

Index 1 2 3 4 5 6 K MIN=4 6
K MIN=4 5
Value 19 20 54 24 39 67
Value 19 67 54 24 39 20
Index 1 2 3 4 5 6

Index 1 2 3 4 5 6 K MIN=4
K MIN=4 6
Interchange A[3] with A[4],
Value 19 67 54 24 39 20 Value 19 20 24 54 39 67

Index 1 2 3 4 5 6 Index 1 2 3 4 5 6

MIN= 6
After pass 3, the 3 shortest elements are sorted and placed at the first three positions in the array

Interchange A[2] with A[6],

Value 19 20 54 24 39 67 Pass 4 j=4, MIN=4, Number of
comparisons 3
Index 1 2 3 4 5 6
Value 19 20 24 54 39 67

After pass 2, the 2 shortest elements are sorted and placed at the first two positions in the array
Index 1 2 3 4 5 6

Pass 3 j=3, MIN=3, Number of K MIN = 4 5

comparisons 3
Value 19 20 24 54 39 67
Value 19 20 54 24 39 67
Index 1 2 3 4 5 6

207 208
K MIN = 5 6 No. of comparisons made in step 2 = N-2
No. of comparisons made in step 3 = N-3
Value 19 20 24 54 39 67 .....
.......
Index 1 2 3 4 5 6 No. of comparisons made in step N-2 = 2

K MIN = 5 No. of comparisons made in step N-1 = 1

Hence, f(n) = (n-1) + (n-2) + ..... + 2 + 1 = (N(N-1))/2 = (N2 - N)/2

Interchange A[4] with A[5],
Value 19 20 24 39 54 67 Big Oh Notation = O(n2)

Index 1 2 3 4 5 6 Check your progress/ Self assessment questions

Q4. Which algorithm places the smallest element at first position in pass1 and which algorithm places
the largest element at last position in pass1?
After pass 4, the 4 shortest elements are sorted and placed at the first four positions in the array ____________________________________________________________________________

___________________________________________________________________________
Pass 5 j=5, MIN=5, Number of
comparisons 3 ____________________________________________________________________________

Q5. How many comparisons are made in bubble sort?

Value 19 20 24 39 54 67 ____________________________________________________________________________

___________________________________________________________________________
Index 1 2 3 4 5 6

K MIN = 5 6 ____________________________________________________________________________

Q6. What is the complexity of both selection and insertion sort in term of Big Oh notation?
Value 19 20 24 39 54 67 ____________________________________________________________________________

___________________________________________________________________________
Index 1 2 3 4 5 6
___________________________________________________________________________

After pass 5, only one element is left and all other elements are sorted and placed in the sorted 12.6 Insertion Sort
form. There is no need to sort the last element, as it is the largest element and list with single Insertion sort also goes through N-1 steps or passes. Starting from 2nd element in the list,
element is always sorted. Considering that element 1 is logically already sorted, places each element K (2 to N) to its correct
position in the sorted list.
12.5.3 Complexity Selection Sort
Complexity of selection sort is same as that of Bubble sort. Step 1 A[2] is placed at its correct position either after or before the element A[1].
Following is the detail of number of comparisons made to find the smallest element in the list
during each step. Step 2 A[3] is placed at its correct position, i.e. before A[1] or between A[1] and A[2] or after A[2].
Similarly all elements up to N are placed at their correct position.
No. of comparisons made in step 1 = N-1

209 210

12.6.1 Insertion Sort Algorithm Because A[K] is not greater than TEMP, there is no change in the array and is the end of pass 1.
ALGORITHM INSERTION_SORT(SORTING AN ARRAY) It sorts an un-sorted array with
N elements.
Pass 2 j=3,
1. Set A[0] = - ∞
TEMP=19,
2. Repeat For J = 2 to N
Value -∞ 54 67 19 24 39 58
3. Set TEMP = A[J]
Index 0 1 2 3 4 5 6
4. Set K = J - 1
K 2
5. Repeat While (A[K] > TEMP)

6. Set A[K+1] = A[K] Now, A[2] > TEMP , hence set A[3] = A[2]
Value -∞ 54 67 67 24 39 58
7. Set K = K - 1

[End of While Loop] Index 0 1 2 3 4 5 6

K 1
8. Set A[K+1] = TEMP

[End of For Loop]

Now, A[1] > TEMP , hence set A[2] = A[1]
9. Exit Value -∞ 54 54 67 24 39 58

Index 0 1 2 3 4 5 6
12.6.2 Insertion Sort Example
K 1
For, Example consider the following array with N= 6 elements

Value 54 67 19 24 39 58
Index 1 2 3 4 5 6 Now, A[0] is not greater than TEMP , hence set A[1] = TEMP
Value -∞ 19 54 67 24 39 58
step 1 inserts minus infinity before the array at index 0. It is not part of array, but the array is Index 0 1 2 3 4 5 6
simply pre-fixed with minus infinity. K 0

Value -∞ 54 67 19 24 39 58
Index 0 1 2 3 4 5 6
Pass 3 j=4,
TEMP=24,
Pass 1 j=2,
TEMP=67, Value -∞ 19 54 67 24 39 58
Index 0 1 2 3 4 5 6
Value -∞ 54 67 19 24 39 58
K 3
Index 0 1 2 3 4 5 6
K 1
Now, A[3] > TEMP , hence set A[4] = A[3]
Value -∞ 19 54 67 67 39 58

211 212
 Value -∞ 19 24 39 54 67 58
Index 0 1 2 3 4 5 6
Index 0 1 2 3 4 5 6
K 2
K 2

Now, A[2] > TEMP , hence set A[3] = A[2]

Value -∞ 19 54 54 67 39 58 Pass 5 j=6,
TEMP=58,
Index 0 1 2 3 4 5 6
Value -∞ 19 24 39 54 67 58
K 1

Index 0 1 2 3 4 5 6
Now, A[1] is not greater than TEMP , hence set A[2] = TEMP
Value -∞ 19 24 54 67 39 58 K 2

Index 0 1 2 3 4 5 6 Now, A[5] > TEMP , hence set A[6] = A[5]

Value -∞ 19 24 39 54 67 67
K 1

Index 0 1 2 3 4 5 6
Pass 4 j=5,
K 5
TEMP=39,

Value -∞ 19 24 54 67 39 58 Now, A[4] is not greater than TEMP , hence set A[5] = TEMP
Value -∞ 19 24 39 54 58 67
Index 0 1 2 3 4 5 6
K 4
Index 0 1 2 3 4 5 6

K 4
Now, A[4] > TEMP , hence set A[5] = A[4]
Value -∞ 19 24 54 67 67 58
After 5 passes, you got the sorted list.
Value 19 24 39 54 58 67
Index 0 1 2 3 4 5 6
Index 1 2 3 4 5 6
K 3

12.6.3 Complexity Insertion Sort

Now, A[3] > TEMP , hence set A[4] = A[3]
Complexity of insertion sort in worst case is same as that of Bubble sort and selection sort.
Value -∞ 19 24 54 54 67 58
Following is the detail of number of comparisons that will be made to find the correct position of

Index 0 1 2 3 4 5 6 each element in the list during each step.

K 2
No. of comparisons made in step 1 = 1
No. of comparisons made in step 2 = 2
Now, A[2] is not greater than TEMP , hence set A[3] = TEMP

213 214

No. of comparisons made in step 3 = 3 Categorizing- Arrangement of similar elements in a group or cluster.
..... Ascending order- Arrangement of elements of the list in non-decreasing order.
....... Descending order- Arrangement of elements of the list in non-increasing order.
No. of comparisons made in step N-2 = N-2 Stable-Sorting Algorithm- Algorithm in which two objects in the input list that have equal keys appear
No. of comparisons made in step N-1 = N-1 in the same order in sorted output list as they appear in the input unsorted list.

Hence, f(n) = 1 + 2 + 3 +...... + (n-2) + (n-1) = (N(N-1))/2 = (N2 - N)/2 12.9 Answers to check your progress/self assessment questions
Big Oh Notation = O(n2) 1. Sorting refers to systematic ordering (rules for sequencing) of element in a list. Sorting is of two
types:
12.7 Summary a. Ordering: Arrangement of elements in some sequence.
Sorting is a vital operation of data structure. Sorting operations help to simplify other data structure b. Categorizing: Arrangement of similar elements in a group or cluster.
operations like, insert, delete and search. Sorting is of two types:
1. Ordering: Arrangement of elements in some sequence. 2. Ascending order is the arrangement of elements of the list in non-decreasing order.
2. Categorizing: Arrangement of similar elements in a group or cluster. Such as, A1 <= A2 <= A3 ...... <= An-1 <= An
Ascending order is the arrangement of elements of the list in non-decreasing order. For example,
Such as, A1 <= A2 <= A3 ...... <= An-1 <= An 1. 52, 52, 67, 68, 68, 90
Descending order is the arrangement of elements of the list in non-increasing order.
Such as, A1 >= A2 >= A3 ...... >= An-1 >= An 3. A sorting algorithm is understood to be stable if two objects in the input list that have equal keys
A sorting algorithm is understood to be stable if two objects in the input list that have equal keys appear appear in the same order in sorted output list as they appear in the input unsorted list.
in the same order in sorted output list as they appear in the input unsorted list. Some of the examples
stable sorting algorithms are Insertion sort, Merge Sort, Bubble Sort and some examples of sorting 4. Bubble sort places the largest element at last position in pass1 and selection sort places the smallest
algorithms are Heap Sort, Quick Sort, etc. element at first position in pass 1
Process of bubble sorting involves N-1 steps where N stands for number of elements in the list. With
N-1 comparisons in step 1, number of comparisons keep decreasing by 1 with every step. With each 5. Total number of comparisons made in bubble sort are as follows:
step the largest element is placed at the end of the list. Complexity of Bubble Sort is O(n2). No. of comparisons made in step 1 = N-1
Selection sort works on the principle of finding the smallest element in the list and interchanging the No. of comparisons made in step 2 = N-2
same with the first element in the list. Hence the first element is placed at its correct position and then No. of comparisons made in step 3 = N-3
the same process is applied to the remaining N-1 elements starting from index position two and so on .....
till N-1. It places the smallest element at first position of the un-sorted list with each step. Complexity .......
of selection Sort is O(n2). No. of comparisons made in step N-2 = 2
Insertion Sort, starting from 2nd element in the list, Considering that element 1 is logically already No. of comparisons made in step N-1 = 1
sorted, places each element K (2 to N) to its correct position in the sorted list. Total No. of comparisons = (n-1) + (n-2) + ..... + 2 + 1 = (N(N-1))/2 =
Complexity of selection Sort is also O(n2).
6. Complexity of both selection and insertion sort in term of Big Oh notation is O(n2).
12.8 Glossary
Sorting- Sorting refers to systematic ordering (rules for sequencing) of element in a list. 12.10 References/ Suggested Readings
Ordering- Rules for arrangement of elements in some sequence. 1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill

215 216
2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage 13.1 Introduction
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education. 13.2 Quick Sort
13.2.1 Example
12.11 Model questions 13.2.2 Algorithm
1. Show step by step sorting of following elements using bubble sort 13.2.3 Complexity
12 54 67 43 23 54 13.3 Heap Sort
2. Write insertion sort algorithm. 13.3.1 Example
3. Discuss complexity of selection sort algorithm 13.3.2 Algorithm
4. Define sorting order and stability. 13.3.3 Complexity
5. Write Selection sort algorithm. 13.4 Merge Sort
13.4.1 Example
13.4.2 Algorithm
13.4.3 Complexity
13.5 Radix Sort
13.5.1 Example
13.5.2 Algorithm
13.5.3 Complexity
13.6 Summary
13.7 Glossary
13.8 Answers to check your progress/self assessment questions
13.9 References/ Suggested Readings
13.10 Model questions

13.0 Objective
After studying this lesson, students will be able to:
1. Explain Quick Sort Algorithm.
2. Describe Merge Sort Algorithm.
3. Define Heap Sort Algorithm
4. Discuss Radix Sort Algorithm.
5. Write sorting algorithms for all four techniques.

13.1 Introduction
In the last lesson you learned three basic sorting algorithms. In this chapter you will learn four advanced
sorting algorithms with better and reduced time complexity. Quick sort algorithm makes use of stack
Lesson 13 Sorting 2 data structure and has much better time complexity. Heap sort algorithm makes use of heap tree or tree
Structure of the lesson data structure. Merge sort makes use of stack data structure and has very good performance. Radix sort
13.0 Objective

217 218

algorithm makes use of 2-D array or buckets to sort the elements. It also has a very time complexity.
You will again enjoy doing this lesson. In this case scanning from second number 45 to right, 45 itself is greater than 35 and hence the two
numbers are interchanged.
13.2 Quick Sort
Quick sort algorithm uses the concept of divide and conquer methodology. Given a list of N elements, 32 35 61 6 89 45 67 90

It divides the un-sorted list into two un-sorted sub-lists. It further using the recursive approach, divides LOWER UPPER
the sub-lists into sub-lists. It continues till the sub-lists are reduced to one element only. You know that
a sub-list of one element is sorted. The quick sort uses stack data structure to keep the track of all sub- In again scans from number 89 to left, 6 is smaller than 35 and hence the two numbers are interchanged
lists.
32 6 61 35 89 45 67 90

13.2.1 Example LOWER UPPER

The quick sort algorithm works as follows:

Given a list of n elements, it places the first element to its correct position on the list. In again scans from number 61 to right, 61 is greater than 35 and hence the two numbers are interchanged

32 6 35 61 89 45 67 90
Consider the following list of N = 8 elements
35 45 61 6 89 32 67 90 LOWER UPPER

Initially, the smallest index in the list is called LOWER and largest index in the list UPPER. 35 has reached its correct position. You can observe that all elements to the left of 35 are smaller than
35 and all elements to the right of 35 are greater than 35.
35 45 61 6 89 32 67 90
LOWER UPPER Now there exists two sub-lists, one on the left of 35 and one on the right of 35. Next the two sublists
will be go through the same process. The process stops when all sub[-lists are reduced to one element
It does so comparing the first element with the element stored at index UPPER in the list and scans from each. When it happens, the list is sorted.
right to left until it finds an element smaller than first element. If it finds one, it interchanges the two
numbers. If it does not find, it means the element has been paced at its correct position in the list. 13.2.2 Algorithm
ALGORITHM_QUICK (It places the first element in the sub-list in the ARRAY to its correct position
In this case scanning from last number 90 to left, 32 is smaller than 35 and hence the two numbers are on the sub-list).

interchanged and UPPER is updated. 1. Set LEFT = BEG

2. Set LOC = LEFT
32 45 61 6 89 35 67 90 3. RIGHT = END
LOWER UPPER
4. Repeat following steps while ARRAY[LOC] <= ARRAY[RIGHT] AND LOC ≠ RIGHT 5. Set
RIGHT = RIGHT - 1
[End of step 4 while loop]

6. if (ARRAY[LOC] > ARRAY[RIGHT])

It than scans the list left to right starting from the element stored next to LOWER to find a number
7. interchange ARRAY[LOC] AND ARRAY[RIGHT] 8. Set LOC = RIGHT
greater than the first number at its new position. If it finds one, it interchanges the two numbers. If it else
does not find, it means the element has been paced at its correct position in the list. [Link] LOC
[End of step 6 if statement]

219 220
10. Repeat following steps while ARRAY[LOC] >= ARRAY[LEFT] AND LOC ≠ LEFT 13.3 Heap Sort
11. Set LEFT = LEFT + 1
[End of step 10 while loop] Heap sort is yet another very popular sorting algorithm. It uses the heap structure or tree. You have
already learned about the heap structure in lesson 6 of this SLM. Recall, a heap or a MAXHEAP is one
12. if (ARRAY[LOC] < ARRAY[LEFT]) in which each node N has a value greater than or equal to the value of all nodes in the left sub-tree and
13. interchange ARRAY[LOC] AND ARRAY[LEFT]
right sub-tree.
14. Set LOC = LEFT
15. goto Step 6 Given a list of N element, the heap sort algorithm in phase 1 creates a heap by inserting all elements in
else the list one by one using the ALGORITHM_INSERTHEAP (explained in lesson 9). Then in the
[Link] LOC
second phase, the heap sort algorithm deletes all elements in the
[End of step 12 if statement]
17. Exit. heap using ALGORITHM_DELETEHEAP (also explain in lesson 1) and add these elements to the
list in the reverse order.
ALGORITHM_QUICKSORT (It sorts a list ARRAY with N elements).
13.3.1 Example
1. Set TOP = NULL
Consider the following list of unsorted elements:
2. if ( N > 1) 50, 44, 40, 48, 60
3. Set TOP = TOP + 1
Phase 1 [ADDING ELEMENTS TO HEAP]
4. Set LOWER[TOP] = 1
5. Set UPPER[TOP] = N 1st element is taken as ROOT.
[End of step 2 if statement]

6. Repeat following steps while TOP ≠ NULL

7. Set BEG = LOWER[TOP]
Step 1 ELEMENT 44
8. Set END = UPPER[TOP]
9. Set TOP = TOP + 1
10. Call ALGORITHM_QUICK (ARRAY, BEG, END, LOC)

11. if LOC + 1 < END

12. Set TOP =TOP + 1
13. Set LOWER[TOP] = LOC + 1
14. Set UPPER[TOP] = END
[End of step 11 if statement] Step 2 ELEMENT 40

15. if LOC - 1 > BEG

16. Set TOP =TOP + 1
17. Set LOWER[TOP] = BEG
18. Set UPPER[TOP] = LOC - 1
[End of step 15 if
statement] [End of step 6 while
loop] 19. Exit.
13.2.3 Complexity Step 3 ELEMENT 48
Worst case scenario for quick sort is when the list is already sorted. In pass 1, number of
comparisons required are n, followed by n-1 comparisons in pass 2 and so on.
f(n) = n + (n+1) + .... + 2 + 1 = n (n + 1) / 2 = O(n2)

221 222

Step 2
TEMP = 50

50 60
Step 4 ELEMENT 60

Step 3 TEMP = 50

48 50 60

TEMP = 50
Step 1 TEMP = 60
Step 4

40 44 48 50 60

Only one element is left, so it is automatically placed at the first position and the list is sorted.

60 13.3.2 Algorithm
ALGORITHM_HEAPSORT (It is used to sort an ARRAY with N elements)

// Create heap structure by inserting elements in list ARRAY one by one

// You start from second element, consider the first element to be the root of the heap structure

1. Repeat following steps for COUNT = 1 TO N - 1

// Algorithm given in lesson 9 of this SLM

223 224
2. Call ALGORITHM_INSERTHEAP (ARRAY, COUNT, ARRAY[COUNT + 1] 13.4 Merge Sort
Merge sorting also follows the principle of divide and conquer. Given an un-sorted list of N elements,
[End of step 1 for loop]
it breaks the entire list into N sub-lists of 1 element each. What is the idea behind it?

For a list with N = 1 elements, the list is always sorted. Hence breaking the list into N sub-lists of 1
// Delete all elements of heap one by one
element each, what we get is N sorted list. Then step by step these sorted lists are combined to form a
// Because the ROOT is largest element, you will add it to the end of list. sorted list using merge algorithm.

3. Repeat following steps while N > 1

13.4.1 Example
// Algorithm given in lesson 9 of this SLM Following image illustrates the concept of merge sort to the best:
4. Call ALGORITHM_DELETEHEAP (ARRAY, COUNT, TEMP)
5. ARRAY[N+1] = TEMP

[End of step 3 while loop]

6. Exit

13.3.3 Complexity
Time complexity of phase 1 to create heap is O(n) = n log2 n.
Time complexity of phase 2 to delete all elements from heap is also O(n) = n log2 n.
Hence the time complexity for the worst case scenario of heap sort is proportional to O(n) = n log2 n.

Check your progress/ Self assessment questions

Q1. Explain the approach of quick sorting.

____________________________________________________________________________
Figure 13.1 Merge sort
___________________________________________________________________________

____________________________________________________________________________ 13.4.2 Algorithm

ALGORITHM_MERGE (It is used to merge 2 sorted sub-lists in ARRAY. TEMP is auxiliary or
Q2. What is the worst case time complexity of quick sort? temporary array).
____________________________________________________________________________
1. Set LE = MID - 1
___________________________________________________________________________
2. Set TEMP_POS = LEFT
____________________________________________________________________________ 3. COUNT = RIGHT - LEFT + 1

Q3. Explain the approach of heap sorting. 4. Repeat following steps while LEFT <= LE AND MID <= RIGHT
____________________________________________________________________________
5. if ARRAY[LEFT] <= ARRAY [MID]
___________________________________________________________________________ 6. TEMP[TEMP_POS] = ARRAY[LEFT]
7.TEMP_POS = TEMP_POS + 1
____________________________________________________________________________
8. LEFT = LEFT +1

else

225 226

9. TEMP[TEMP_POS] = ARRAY[MID] Hence it can be concluded that time complexity of merge sort is O(n) = n log n
10. TEMP_POS = TEMP_POS + 1
11. MID = MID + 1
13.5 Radix Sort
[End of step 5 if statement]
[End of step 4 while loop] Radix sort is a very popular sorting technique that has a very good time complexity. It is basically used
to sort names or words. Like in dictionary all words are sorted on the basis of alphabets from left to
12. Repeat following steps while LEFT <= LE
right. Radix sort can also be used to sort numbers.
13. TEMP[TEMP_POS] = ARRAY[LEFT]
14. TEMP_POS = TEMP_POS + 1 The radix sort approach starts by sorting the numbers based on the unit place number. For example, 654
15. LEFT = LEFT +1 has unit place number = 4 and 432 has unit place number = 2. The numbers are sorted based on the
[End of step 12 while loop]
value of right most digit first.
16. Repeat following steps while MID <= RIGHT But there can be 10 different possible values of unit place number, how to keep track of numbers if N
17. TEMP[TEMP_POS] = ARRAY[MID] is very high. Radix sort uses the concept of pockets to overcome this problem. A total of 10 pockets are
18. TEMP_POS = TEMP_POS + 1
used to save all the numbers with 10 different values for unit place number from 0 to 9. The numbers
19. MID = MID + 1
[End of step 16 while loop] are sorted based on unit place number and PUSHED into the respective pockets.
Once the numbers are placed in respective pockets after pass 1, the elements are rearranged starting
20. Repeat following step for I = to COUNT
from all numbers in pocket 0, followed by numbers in pocket 1 and so on till pocket 9.
21. ARRAY[RIGHT] = TEMP[RIGHT]
RIGHT = RIGHT - 1 Next the newly arranged numbers are sorted based on ten place number and PUSHED into the respective
[End of step 20 for loop] pockets. Once the numbers are placed in respective pockets after pass 2, the elements are rearranged
21. End starting from all numbers in pocket 0, followed by numbers in pocket 1 and so on till pocket 9.
The process is repeated for the length of largest number in the list. For example, consider that 54325 is

ALGORITHM_MERGESORT (It is an recursive algorithm used to sort list of N elements called ARRAY. the largest number in the list. It has a length of 5 and hence total of 5 passes will be performed.
Initially LEFT = 1 and RIGHT = N).
13.5.1 Example
1. if RIGHT > LEFT
2. Set MID = (RIGHT + LEFT) / 2 Consider the following list for example,

3. Call ALGORITHM_MERGESORT ( ARRAY, LEFT, MID)

034 543 251 545 678 440 332 967 843 249
4. Call ALGORITHM_MERGESORT ( ARRAY, MID + 1, RIGHT)
5. Call ALGORITHM_MERGE(ARRAY, LEFT, MID + 1, RIGHT)
[End of step 1 if statement] Pass 1

2. End The elements shown in the figure above will be inserted into respective pockets based on the digit at
unit place. 034 % 10 = 4

13.4.3 Complexity 543 % 10 = 3

It takes linear time to merge two lists with total of N elements, which means to merge 2 lists of N 251 % 10 = 1

elements in total, O(n) = n 545 % 10 = 5

Let us consider a list of N = 8 elements, 678 % 10 = 8

Time complexity to merge 2 lists with N = 2 elements = 2 440 % 10 = 0

Time complexity to merge 2 lists with N = 4 elements = 4 332 % 10 = 2

Time complexity to merge 2 lists with N = 8 elements = 8 967 % 10 = 7

227 228
843 % 10 = 3 The elements shown in the figure above will be inserted into respective pockets based on the digit at
249 % 10 = 9 hundred place. 332 % 1000 = 3
POCKET POCK POCK POCK POCK POCK POCK POCK POCK POCK 034 % 1000 = 0
[0] ET [1] ET [2] ET [3] ET [4] ET [5] ET [6] ET [7] ET [8] ET [9] 440 % 1000 = 4
440 251 332 543 034 545 967 678 249 543 % 1000 = 5
843 843 % 1000 = 8
545 % 1000 = 5
249 % 1000 = 2
Newly arranged list of elements
440 251 332 543 843 034 545 967 678 249 251 % 1000 = 2
967 % 1000 = 9
678 % 1000 = 6
Pass 2
POCKET POCK POCK POCK POCK POCK POCK POCK POCK POCK
The elements shown in the figure above will be inserted into respective pockets based on the digit at ten
[0] ET [1] ET [2] ET [3] ET [4] ET [5] ET [6] ET [7] ET [8] ET [9]
place.
034 249 332 440 543 678 843 967
440 % 100 = 4
251 % 100 = 5 251 545

332 % 100 = 3
543% 100 = 4 Final Sorted List
843 % 100 = 4 034 249 251 332 440 543 545 678 843 967

034 % 100 = 3
545 % 100 = 4 13.5.2 Algorithm
967 % 100 = 6 ALGORITHM_ RADIXSORT (It is used to sort list ARRAYA. ARRAYB is used as auxiliary list and
678 % 100 = 7 POCKET as 2-D list with 10 columns).

249 % 100 = 4 1. Set SIZE = length of largest element in the ARRAYA.

POCKET POCK POCK POCK POCK POCK POCK POCK POCK POCK
[0] ET [1] ET [2] ET [3] ET [4] ET [5] ET [6] ET [7] ET [8] ET [9] 2. Repeat following steps for COUNT = 1 to SIZE
332 440 251 967 678
3. Repeat following steps for I = 1 to N
034 543 4. DIGIT = ARRAYA[I] % 10COUNT
5. Insert ARRAYA[I] into POCKET[DIGIT], where DIGIT represents POCKET number.
843 [End of step 3 for loop]
545
6. Repeat following steps for J = 9 to 0
249
7. Repeat while POCKET[J] ≠ NULL
8. Remove from POCKET [J] AND Insert the element in ARRAYB.
Newly arranged list of elements [End of step 7 for loop]
332 034 440 543 843 545 249 251 967 678 [End of step 6 for loop]

9. Set ARRAYA = ARRAYB AND Delete all elements from ARRAYB.

Pass 3 [End of step 2 for loop]

229 230

10. Exit. ALGORITHM_DELETEHEAP and add these elements to the list in reverse order. Time complexity of
phase 1 to create heap is O(n) = n log2 n. Time complexity of phase 2 to delete all elements from heap
13.5.3 Complexity is also O(n) = n log2 n. Hence the time complexity for the worst case scenario of heap sort is proportional
Let for a list of n elements, d represents the radix or number of pockets. In case of words d = 26 to O(n) = n log2 n.
(number of distinct alphabets) and in case of numbers d= 10 (number of distinct digits). Let the length Merge for a given un-sorted list of N elements, breaks the entire list into N sub-lists of 1 element each.
of the largest number in the list is s. Hence a total of s passes will be made. For a list with N = 1 elements, the list is always sorted. Hence breaking the list into N sub-lists of 1
Number of comparisons is bound to be c(n) <= d*s*n, where both d and s are independent of n. The element each, what we get is N sorted list. Then step by step these sorted lists are combined to form a
performance of radix sort is best when s, i.e. length of largest element s is small. sorted list using merge algorithm. Time complexity of merge sort is O(n) = n log n.
The radix sort approach starts by sorting the numbers based on the unit place number. It then sorting the
Check your progress/ Self assessment questions
numbers based on tens place number, and so on. The number of passes are equal to the length of the
Q1. What is the time complexity of merge sort? largest number in the list. The performance of radix sort is best when s, i.e. length of largest element s
____________________________________________________________________________
is small.
___________________________________________________________________________
13.7 Glossary
____________________________________________________________________________
Sorting- Arranging of elements sequentially based on some ordering rule.
Q2. Which is the best application of radix sort? Time Complexity- Number of computational steps or comparisons needed to successfully finish thr
____________________________________________________________________________
algorithm steps.
___________________________________________________________________________ Quick Sort- Sorting algorithm.

____________________________________________________________________________ Merge Sort- Sorting algorithm.

Radix Sort- Sorting algorithm.
Q3. In which case does the radix sort performs the best in terms of time complexity.
____________________________________________________________________________ Heap Sort- Sorting algorithm.
Heap- Tree structure in which each node n is greater than all nodes in the left and right sub-trees.
___________________________________________________________________________

____________________________________________________________________________ 13.8 Answers to check your progress/self assessment questions

1. Quick sort algorithm uses the concept of divide and conquer methodology. Given a list of N elements,
13.6 Summary It divides the un-sorted list into two un-sorted sub-lists. It further using the recursive approach,
Quick sort algorithm uses the concept of divide and conquer methodology. Given a list of N elements, divides the sub-lists into sub-lists. It continues till the sub-lists are reduced to one element only.
It divides the un-sorted list into two un-sorted sub-lists. It further using the recursive approach, divides
the sub-lists into sub-lists. It continues till the sub-lists are reduced to one element only. You know that 2. Worst case scenario for quick sort is when the list is already sorted. In pass 1, number of comparisons
a sub-list of one element is sorted. The quick sort uses stack data structure to keep the track of all sub- required are n, followed by n-1 comparisons in pass 2 and so on.
lists. f(n) = n + (n+1) + .... + 2 + 1 = n (n + 1) / 2 = O(n2)
Worst case scenario for quick sort is when the list is already sorted. In pass 1, number of comparisons
required are n, followed by n-1 comparisons in pass 2 and so on. 3. Given a list of N element, the heap sort algorithm in phase 1 creates a heap by inserting all elements
f(n) = n + (n+1) + .... + 2 + 1 = n (n + 1) / 2 = O(n2) in the list one by one using the ALGORITHM_INSERTHEAP. Then in the second phase, the heap
Heap sort uses the heap structure or tree. Given a list of N element, the heap sort algorithm in phase 1 sort algorithm deletes all elements in the heap using ALGORITHM_DELETEHEAP and adding
creates a heap by inserting all elements in the list one by one using the ALGORITHM_INSERTHEAP. these elements to the list in the reverse order.
Then in the second phase, the heap sort algorithm deletes all elements in the heap using

231 232
4. Time complexity of merge sort is O(n) = n log n 14.1 Introduction
14.2 Linear Search
5. The best application of radix sort is to sort names or words. Like in dictionary all words are sorted 14.2.1 Algorithm [LINEAR SEARCH]
on the bases of alphabets from left to right. 14.2.2 Example of successful search [LINEAR SEARCH]
14.2.3 Example of un-successful search [LINEAR SEARCH]
6. The performance of radix sort is best when s, i.e. length of largest element s is small. 14.2.4 Time Complexity [LINEAR SEARCH]
14.3 Binary Search
13.9 References/ Suggested Readings 14.3.1 Algorithm [BINARY SEARCH]
1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill. 14.3.2 Example of successful search [BINARY SEARCH]
2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage 14.3.3 Example of un-successful search [BINARY SEARCH]
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education. 14.3.4 Time Complexity [BINARY SEARCH]
14.4 Hashing
13.10 Model questions 14.5 Summary
1. Show step by step sorting of following elements using heap sort 14.6 Glossary
18 45 76 12 43 14.7 Answers to check your progress/self assessment questions
2. Write radix sort algorithm. 14.8 References/ Suggested Readings
3. Explain the concept of quick sort with the help of an example. 14.9 Model questions
4. Explain the concept of merge sort with the help of an example.
5. Write quick sort algorithm. 14.0 Objective
After studying this lesson, students will be able to:
1. Define linear and binary search algorithms.
2. Explain the efficiency of both linear and binary search algorithms.
3. Compare and contrast both linear and binary search algorithms
4. Implement both linear and binary search algorithms.

14.1 Introduction
Searching is one of the most important and critical operation of data structures. It is most common term
used in day to day life of every human being. Be at hospital searching for the room number of patient,
be at railway station, searching for trains leaving from one station, be at library searching for availability
of a book in the library, etc.

Search refers to the process of looking for a record or item in the list based on some key. Only the value
of that key is known and not the actual location in the list. For example, take a key to be roll number,
accountant wants to know the phone number of the students father whose roll number is 18.
Lesson 14 Searching
The primary usage of computers in commercial scenario was to store data and later search for that data
Structure of the lesson
entries in efficient manner. There is no point in storing data in computers if it would take enormous
14.0 Objective
time to search for that record or data. The most basic search algorithm is linear search.

233 234

Advanced search algorithm is binary search, but it has a major pre-requisite. 5. Exit.

In this lesson you will learn algorithms for both linear and binary search algorithms with the help of 14.2.2 Example of successful search [LINEAR SEARCH]
detailed examples. Also in the end, you will also come across the efficiency of both the search For Example [successful search], Consider the following array:
algorithms.
Value 23 45 12 89 112 4
14.2 Linear Search Index 1 2 3 4 5 6
Linear search is the most basic and easy to implement search algorithm of all. Starting from the very
first element or record in the list, it continues to search for the given ITEM in the linear fashion. Easy Let us suppose, the users wants to search the location of ITEM 89 in the array.
to implement it may be, but it is not the most effective algorithm of all. The complexity depends upon Step 1 of the algorithm adds ITEM at the end of the array. Number of elements in the array do not
the number of elements "N" in the list. change, as the ITEM added at the end of the array is not part of the array.

It is certainly useful when there are only a few entries in the list, but can give very poor performance Value 23 45 12 89 112 4 89
when the size of list grows exponentially. Where the data grows daily, i.e. new entries are made on the
regular basis and historical data keeps on pilling, it is not useful. Let us have a look at the algorithm for Index 1 2 3 4 5 6 7
linear search in the next section.
Step 2 of the algorithm assigns the index 1 to the counter I.
14.2.1 Algorithm [LINEAR SEARCH]
Step 3 is a control statement. The loop will iterate till the ITEM is found in the array
ALGORITHM LINEAR_SEARCH (SEARCHING FROM AN ARRAY) searches for an
element ITEM in the array(ARR) with lower bound LB and upper bound UB. LOC is
where the location is stored if search is successful. Value 23 45 12 89 112 4 89
Index 1 2 3 4 5 6 7
1. Set ARR[UB+1] = ITEM I 1

2. Set I = LB
The first element of array does not match with the ITEM, Hence the counter I is incremented by
3. Repeat while ARR[I] != ITEM
1.
4. Set I = I + 1 [Increments the value of counter by 1]

[End of Loop] Value 23 45 12 89 112 4 89

4. if I = UB + 1
Index 1 2 3 4 5 6 7
Print “ITEM COULD NOT BE FOUND”
I 2
else

LOC = I The second element of array does not match with the ITEM, Hence the counter I is incremented
by 1.
Print “ITEM FOUNF AT LOCATION “ + LOC
return LOC

[End of if]

235 236
Value 23 45 12 89 112 4 89
Index 1 2 3 4 5 6 7 14.2.3 Example of un-successful search [LINEAR SEARCH]
I 3
For Example [un-successful search], Consider the following array:

The third element of array does not match with the ITEM, Hence the counter I is again
Value 23 45 12 89 112
incremented by 1.
Index 1 2 3 4 5
Value 23 45 12 89 112 4 89
Index 1 2 3 4 5 6 7 Let us suppose, the users wants to search the location of ITEM 68 in the array.
I 4
Step 1 of the algorithm adds ITEM at the end of the array. Number of elements in the array do not

Now the fourth element of the array, i.e. ARR[4] = 89 matches with the ITEM = 89 and hence the change, as the ITEM added at the end of the array is not part of the array.

loop at step 3 terminates.

Value 23 45 12 89 112 68
Index 1 2 3 4 5 6
Step 4 is an if control statement that checks if the ITEM was found within the array or at position
next to the UB of the array.
Step 2 of the algorithm assigns the index 1 to the counter I.

In this case the item was found within the boundaries of the array, hence the else part is executed.
Step 3 is a control statement. The loop will iterate till the ITEM is found in the array
The LOC is set to 4 and the same is displayed to the user. Also the LOC is returned to the calling
algorithm.
Value 23 45 12 89 112 68
Index 1 2 3 4 5 6
Check your progress/ Self assessment questions
I 1
Q1. Define search.
____________________________________________________________________________
The first element of array does not match with the ITEM, Hence the counter I is incremented by
___________________________________________________________________________
1.
____________________________________________________________________________
Value 23 45 12 89 112 68
Q2. List at least 3 real life applications where you use search operation.
____________________________________________________________________________
Index 1 2 3 4 5 6
___________________________________________________________________________
I 2
____________________________________________________________________________

Q3. What is the disadvantage of linear search? The second element of array does not match with the ITEM, Hence the counter I is incremented
____________________________________________________________________________ by 1.

___________________________________________________________________________
Value 23 45 12 89 112 68
____________________________________________________________________________ Index 1 2 3 4 5 6

237 238

I 3
Worst time complexity: which is the maximum time taken to search for an ITEM in the list. For linear
The third element of array does not match with the ITEM, Hence the counter I is incremented by search algorithm, the worst time complexity is n, i.e. if the ITEM to be searched is stored at index n of
1. the array.

Value 23 45 12 89 112 68 Average time complexity: It is the average of both the best and worst time complexities. For linear
Index 1 2 3 4 5 6 search it is (n + 1)/ 2
I 4
The Big Oh notation for linear search is O(n) taken from the worst time complexity.
The fourth element of array does not match with the ITEM, Hence the counter I is incremented
by 1. Check your progress/ Self assessment questions

Q4. Give the worst case complexity of linear search .

Value 23 45 12 89 112 68 ____________________________________________________________________________

___________________________________________________________________________
Index 1 2 3 4 5 6
____________________________________________________________________________
I 5
Q5. What is the time taken to search for an item that does not exist in array using the linear search
given earlier in this lesson.
The fifth element of array does not match with the ITEM, Hence the counter I is incremented by
____________________________________________________________________________
1.
___________________________________________________________________________

Value 23 45 12 89 112 68 ____________________________________________________________________________

Index 1 2 3 4 5 6
Q6. Can we perform linear search from last position in the list?
I 6 ____________________________________________________________________________

___________________________________________________________________________
Now the 6th element matches with the ITEM.
____________________________________________________________________________

Step 4 checks if the ITEM was found within the array or at position next to the UB of the array.
In this case the item was found outside the boundaries of the array, hence the if part is executed.
14.3 Binary search
The message “ITEM COULD NOT BE FOUND” is displayed to the user”. It is yet another search technique popularly used in the field of computer science for its better efficiency
than the linear search. It takes much lesser time to search for an item in the list than the linear search
14.2.4 Time Complexity [LINEAR SEARCH] algorithm.
There are two notions to keep in mind while computing the time complexity of the linear serach
algorithm. With its better performance comes an disadvantage too. Binary search algorithm can be implemented
only on the lists that are sorted, i.e. in order to implement binary search, you need to sort the list first.
Best time complexity: which is the minimum time taken to search for an ITEM in the list. For linear Sorting can either be in ascending or descending order. Binary search follows the principle of divide
search algorithm, the best time complexity is 1, i.e. if the ITEM to be searched is stored at index 1 of and conquer. Depending upon the value of the ITEM to be searched with the value of middle element
the array. in the list, the search area is halved after every iteration.

239 240
 Value 23 29 32 39 42 44 54 90 91 97 99 128 135
For example,
Index 1 2 3 4 5 6 7 8 9 10 11 12 13
Let us consider that you are searching for an ITEM 55246 in a sorted list of 1000 elements. If the middle
element of the list is 50000, it means that the ITEM cannot be on the left side of the middle element as
Let us suppose, the users wants to search the location of ITEM 39 in the array.
all elements on the left side of 50000 are less than it and ITEM is greater than it. So with this one step,
Step 1 of the algorithm assigns BEG = 1 & END = 13, covering the entire range of array.
the algorithm manages to reduce the search area to half.
Step 2 Assigns the mid of the two , i.e. (13 + 1)/2 = 7 to MID.

14.3.1 Algorithm [BINARY SEARCH] Value 23 29 32 39 42 44 54 90 91 97 99 128 135

Index 1 2 3 4 5 6 7 8 9 10 11 12 13
ALGORITHM BINARY_SEARCH (SEARCHING FROM AN ARRAY) searches for an
element ITEM in the sorted array(ARR) with N elements. LOC is where the location is POINTERS BEG MID END
stored if search is successful.
1. Set BEG = 1 and END = N
Step 3 is a control statement. The loop will iterate till the ITEM is found at ARR[MID] or BEG
2. Set MID = (BEG + END) / 2
becomes greater than END.
3. Repeat While (BEG <= END) and (ARR[MID] != ITEM)
Step 4 checks if the value of ITEM is less than ARR[MID], which in this case is true and hence
4. If (ITEM < ARR[MID]) Then
changes the value of END = MID - 1, i.e. END = 6
5. Set END = MID – 1

6. Else Also Step 8 changes the value of MID = (1+6)/2 = 3

7. Set BEG = MID + 1 Value 23 29 32 39 42 44 54 90 91 97 99 128 135

[End of If] Index 1 2 3 4 5 6 7 8 9 10 11 12 13
POINTERS BEG MID END
8. Set MID = (BEG + END) / 2

[End of While Loop]

Step 4 again checks if the value of ITEM is less than ARR[MID], which in this case is false and
9. If (ARR[MID] == ITEM) Then hence the else part changes the value of BEG = MID + 1, i.e. BEG = 4

10. Print "ITEM is stored at location" + MID

Also Step 8 changes the value of MID = (4+6)/2 = 5
11. Else
Value 23 29 32 39 42 44 54 90 91 97 99 128 135
12. Print "ITEM doesn’t exist in the array"
Index 1 2 3 4 5 6 7 8 9 10 11 12 13
[End of If]
POINTERS BEG MID END
13. Exit Step 4 again checks if the value of ITEM is less than ARR[MID], which in this case is true and
hence changes the value of END = MID - 1, i.e. END = 4
14.3.2 Example of successful search [BINARY SEARCH]
For Example [successful search], Consider the following array: Also Step 8 changes the value of MID = (4+4)/2 = 4

Value 23 29 32 39 42 44 54 90 91 97 99 128 135

241 242

Index 1 2 3 4 5 6 7 8 9 10 11 12 13 POINTERS BEG MID END

POINTERS BEG,
MID, Step 4 checks if the value of ITEM is less than ARR[MID], which in this case is true and hence
END changes the value of END = MID - 1, i.e. END = 5

Now that the ITEM is equal to the ARR[MID], the loop terminates. Also Step 8 changes the value of MID = (5+5)/2 = 5

Value 23 29 32 39 42 44 54
Step 9 checks, if the ITEM is equal to ARR[MID], which is true in this case, it displays:
ITEM is stored at location 4 and terminates. Index 1 2 3 4 5 6 7
POINTERS BEG,
14.3.3 Example of un-successful search [BINARY SEARCH] Example MID,
[Un-Successful search], Consider the following array: END

Value 23 29 32 39 42 44 54 Step 4 checks if the value of ITEM is less than ARR[MID], which in this case is true and hence
Index 1 2 3 4 5 6 7 changes the value of END = MID - 1, i.e. END = 4

Let us suppose, the users wants to search the location of ITEM 41 in the array. Now that the BEG is greater than END, the loop terminates.

Step 1 of the algorithm assigns BEG = 1 & END = 7, covering the entire range of array. Step 9 checks, if the ITEM is equal to ARR[MID], which is false in this case, it displays:
ITEM doesn’t exist in the array
Step 2 Assigns the mid of the two , i.e. (7 + 1)/2 = 4 to MID.
14.3.4 Time Complexity [BINARY SEARCH]
Value 23 29 32 39 42 44 54
There are two notions to keep in mind while computing the time complexity of the binary search
Index 1 2 3 4 5 6 7 algorithm.
POINTERS BEG MID END Best time complexity: which is the minimum time taken to search for an ITEM in the list. For binary
search algorithm, the best time complexity is 1, i.e. if the ITEM to be searched is stored at middle index
Step 3 is a control statement. The loop will iterate till the ITEM is found at ARR[MID] or BEG of the array. For example, in the list of 1000 elements, if the ITEM to be searched is stored at 500th
becomes greater than END. index.

Step 4 checks if the value of ITEM is less than ARR[MID], which in this case is false and hence Worst time complexity: which is the maximum time taken to search for an ITEM in the list. For binary
else part changes the value of BEG = MID + 1, i.e. BEG = 5 search algorithm, the worst time complexity is log2n, i.e. if the maximum number of iterations possible
to search an element in the list. It is log2n, because with every iteration, the search area is halved.
Also Step 8 changes the value of MID = (5+7)/2 = 6
Average time complexity: It is the average of both the best and worst time complexities. For binary
Value 23 29 32 39 42 44 54
search it is (log2n + 1)/ 2
Index 1 2 3 4 5 6 7

243 244
The Big Oh notation for binary search is O(log2n) taken from the worst time complexity. H refers to hash function. The main objective of using hash function is to reduce the time complexity
of the search operation. If the hash function takes too much of time to compute, the whole idea of using
Check your progress/ Self assessment questions the hash function fails. Also you need to maintain the uniformity in address calculation L. It means for

Q7. What is the pre-requisite of Binary search?

computing location for most of the keys, the hash function must yield uniform memory locations, i.e.
____________________________________________________________________________ different memory location for different key values. It helps in reducing the problem of collision.

___________________________________________________________________________
Some of the examples of hash function.
1. Division Method: based on the modulus function, the division method computes the memory
____________________________________________________________________________
location by applying modulus operator on the key K. The value M, used as divisor in modulus operation
Q8. What is the advantage of binary search over linear search . is usually a prime number or a number that does not have small divisors.
____________________________________________________________________________
2. Midsquare Method: It is yet another very simple hash function used to compute the memory
___________________________________________________________________________ location L for different keys. The idea is very simple, i.e. to compute the square of the key and then to
select the memory location L from the middle of the resultant figure. The middle value can be obtained
____________________________________________________________________________
by removing equal number of digits from the left and right side of the figure obtained by squaring the
9. Which of the following is not the required condition for binary search algorithm? a. key.
The list must be sorted 3. Folding Method: Last of the three hash function simply chops the key into multiple sub-keys
b. there should be the direct access to the middle element in any sublist and then simply add those keys to compute the memory location L. It is quite simple to compute:
c. There must be mechanism to delete and/or insert elements in list
d. none of above 14.5 Summary
Search refers to the process of looking for a record or item in the list based on some key. Only the value
10. Time complexity of linear search: of that key is known and not the actual location in the list. Linear search is the most basic and easy to
a. O(n) implement search algorithm of all. Starting from the very first element or record in the list, it continues
b. O(n2) to search for the given ITEM in the linear fashion. The complexity depends upon the number of elements
c. O(1) "N" in the list. The Big Oh notation for linear search is O(n) taken from the worst time complexity.
d. O(log2 n) Binary search follows the principle of divide and conquer. Depending upon the value of the ITEM to be
searched with the value of middle element in the list, the search area is halved after every iteration.
14.4 Hashing Binary search algorithm can be implemented only on the lists that are sorted. It takes much lesser time
Hashing is a technique that provides a way to reduce the expected time of operations such as INSERT, to search for an item in the list than the linear search algorithm. The Big Oh notation for linear search
DELETE, SEARCH to O( 1) per operation. The idea behind hashing is quite natural and straight is O(log2n) taken from the worst time complexity
forward. Yes, there are certain problems regarding the memory collision. But if we approach the
problem in the straightforward fashion and it is possible to work around the memory problem 14.6 Glossary
encountered later on. Search- Data structure operation to search for an ITEM in any data structure.
Let n be the number of data items to be stored and m the number of possible data items. Ideally, you Linear Search- Technique to search for an ITEM in the list in linear fashion.
would like to employ an array as follows: Array- Collection of similar type of elements stored contiguously in memory.
1. Initialize all locations of a (large) array A[O ... m-l] to contain a nil value. Time Complexity- Number of computational steps it takes to execute or run the algorithm successfully.
2. Associate a unique integer 0 ~ h(d)<m with each possible input item d. Sort- Arrangement of elements in either ascending or descending order in a list.
3. Place d in position A[h(d)]. Big Oh Notation- It is the notation used to suggest the worst time that will taken by an algorithm and it
suggests the upper bound to any f(n).

245 246

1. Compare and contrast linear and binary search algorithms.

14.7 Answers to check your progress/self assessment questions 2. Write the linear search algorithm.
1. Search refers to the process of looking for a record or item in the list based on some key. Only the 3. Give the step by step searching of ITEM 67 using binary search in the following list:
value of that key is known and not the actual location in the list. 11 22 34 36 45 55 56 58 67 101 111
4. Write the binary search algorithm.
2. 5. Explain the time complexity of both linear and binary search algorithms.'
a. At hospital, searching for the room number of patient.
b. At railway station, searching for trains leaving from one station
c. At library, searching for availability of a book in the library, etc.

3.
Linear search is not the most effective algorithm of all. The complexity of the linear search algorithm
is very high and it is depended upon the number of elements "N" in the list. As the value of N increases,
also increases the complexity of the algorithm.

4. Worst time complexity is the maximum time taken to search for an ITEM in the list. For linear
search algorithm, the worst time complexity is n, i.e. if the ITEM to be searched is stored at index
n of the array.

5. Time taken to search for an item that does not exist in array using the linear search is n + 1.

6. Yes, we can start linear search from last position in the list. The order of search is from N to 1.

7. It is only possible to implement binary search on any given list if the given list is already sorted.

8. The efficiency of binary search is much better than that of linear search. The time complexity of
binary search is O(log2n) as compared to O(n) of linear search.
9. c.
10. a.

14.8 References/ Suggested Readings

1. Schaum’s Outline of Data Structures – Seymour Lipschutz by Tata McGraw-hill
2. Data Structures – A Pseudo code Approach with C++ - Gilberg and Forouzan by Cengage
3. Data Structures Using C and C++ - Langsam, Augenstein, Tanenbaum by Pearson Education.
4. Data Structures in C++, "Kutti and Padhye", PHI, 1999.

14.9 Model questions

247 248