UNIT-1

Introduction-definition, need of Data Structures

Definition

Definition:

Data structure is a particular way of organizing or structuring data while storing in a

computer so that it can be used effectively. (it is not a programming language)

For example, we can store a list of items having the same data-type using the array data
structure:

We can also define data structure as a mathematical or logical model (we will construct
these models in C language)of a particular organization of data items.

Data Structure mainly specifies the following four things:

· Organization of Data (+amount of memory required to store)

· Accessing methods (+amount of time required to process)

· Degree of associativity (how the data items are related to each other)

· Processing alternatives for information (only then can we know the best)

Basic Terminology

 Data: Data can be defined as an elementary value or the collection of values, for
example, student's name and its id are the data about the student.
 Group Items: Data items which have subordinate data items are called Group
item, for example, name of a student can have first name and the last name.
  Record: Record can be defined as the collection of various data items, for
example, if we talk about the student entity, then its name, address, course and
marks can be grouped together to form the record for the student.
 File: A File is a collection of various records of one type of entity, for example, if
there are 60 employees in the class, then there will be 20 records in the related
file where each record contains the data about each employee.
 Attribute and Entity: An entity represents the class of certain objects. it contains
various attributes. Each attribute represents the particular property of that entity.
 Field: Field is a single elementary unit of information representing the attribute of
an entity.

Introduction-definition, need of Data Structures

Need of Data Structure

Need of Data Structures

As applications are getting complexed and amount of data is increasing day by day,
there may arrise the following problems:

Processor speed: To handle very large amout of data, high speed processing is required,
but as the data is growing day by day to the billions of files per entity, processor may fail
to deal with that much amount of data.

Data Search: Consider an inventory size of 106 items in a store, If our application needs
to search for a particular item, it needs to traverse 106 items every time, results in
slowing down the search process.

Multiple requests: If thousands of users are searching the data simultaneously on a web
server, then there are the chances that a very large server can be failed during that
process

In order to solve the above problems, data structures are used. Data is organized to form
a data structure in such a way that all items are not required to be searched and required
data can be searched instantly.
Advantages of Data Structures

Efficiency: Efficiency of a program depends upon the choice of data structures. For
example: suppose, we have some data and we need to perform the search for a
perticular record. In that case, if we organize our data in an array, we will have to search
sequentially element by element. hence, using array may not be very efficient here. There
are better data structures which can make the search process efficient like ordered
array, binary search tree or hash tables.

Reusability: Data structures are reusable, i.e. once we have implemented a particular
data structure, we can use it at any other place. Implementation of data structures can be
compiled into libraries which can be used by different clients.

Abstraction: Data structure is specified by the ADT which provides a level of abstraction.
The client program uses the data structure through interface only, without getting into
the implementation details.

Introduction-definition, need of Data Structures

Classification of data structures

Classification of Data Structure

· Primitive data structures

· Non-primitive data structures (linear and non-linear)

· Homogeneous and non-homogeneous data structures

· Static and dynamic data structures

1. Primitive data structures :

These are the basic data structures and are directly operated upon by the machine
instructions.

They are integers, floating point numbers, characters, string constants, pointers etc.

Like: int a =10;

The corresponding machine level code will be like:

store the int value in so and so location.

But if I write: int arr[10]=20;

The machine instruction doesn’t know array index 10! So, intermediate steps will be there
to convert this particular instruction to machine level.

2. Non-primitive data structures:

It is advanced data structure emphasizing on structuring of a group of data items.

They cannot be directly operated upon by the machine instructions.

Example: Array, list, files, linked list, trees and graphs fall in this category.

Linear and non-linear data structures :

In a linear data structure, the data items are arranged in a linear sequence.

For example: array.

In a non-linear data structure, the data items are not in sequence.

For Example: trees and graphs.

3. Homogeneous and non-homogeneous data structures:

In homogeneous data structure, all the elements are of same type.

For Example: arrays.

In non-homogeneous data structure, the elements may or may not be of the same type.

For Example: Records.

4. Static and dynamic data structures:

In Static data structure the size of the structure is fixed. The content of the data structure
can be modified but without changing the memory space allocated to it.

Example: Array

In Dynamic data structure the size of the structure is not fixed and can be modified
during the operations performed on it. Dynamic data structures are designed to facilitate
change of data structures in the run time.

Example: Linked List

Classification of data structures, Operations on Data

Structures

Operations on Data Structures

The most commonly used operations on data structure are broadly categorized into
following types:

1) Create:- The create operation results in reserving memory for program elements. This
can be done by declaration statement.

Creation of data structure may take place either during compile-time or run-time.

Dynamic Memory Allocation in C can be done using malloc(), calloc(), free() and realloc()

2) Destroy:- Destroy operation destroys memory space allocated for specified data
structure. free() function of C language is used to destroy data structure.

3) Selection:- Selection operation deals with accessing a particular data within a data
structure.

4) Updation:- It updates or modifies the data in the data structure.

5) Searching:- It finds the presence of desired data item in the list of data items, it may
also find the locations of all elements that satisfy certain conditions.

6) Sorting:- Sorting is a process of arranging all data items in a data structure in a

particular order, say for example, either in ascending order or in descending order.
7) Merging:- Merging is a process of combining the data items of two different non-
primitive data structure into a single one.

8) Splitting:- Splitting is a process of partitioning single non-primitive data structure to

multiple ones.

9) Traversal:- Traversal is a process of visiting each and every node of a non-primitive

data structure in systematic manner.
Pointers – definition, accessing the address of a variable

Definition

Definition:

A pointer is a variable whose value is the address of another variable, i.e., direct address
of the memory location.

Like any variable or constant, you must declare a pointer before using it to store any
variable address.

The general form of a pointer variable declaration is −

type *var-name;

Here, type is the pointer's base type (i.e.data type of the variable whose address the
pointer is storing) and var-name is the name of the pointer variable.

Accessing the Address of a Variable

#include <stdio.h>

int main () {

int var = 10; /* actual variable declaration */

int *ptr; /* pointer variable declaration */

ptr = &var; /* store address of var in pointer variable*/

printf("Address of var variable: %x\n", &var );

/* address stored in pointer variable */

printf("Address stored in ip variable: %x\n", ptr );

/* access the value using the pointer */

printf("Value of *ip variable: %d\n", *ptr);

return 0;

}
Steps of pointer usage:

· Define a pointer variable

· Assigning the address of a variable to a pointer using unary operator (&) which
returns the address of that variable.

· Accessing the value stored in the address using unary operator (*) which returns the
value of the variable located at the address specified by its operand.
Declaring and initialising pointers, Accessing a variable
through its pointer

Declaring and initialising pointers

Declaration of C Pointer variable

General syntax of pointer declaration is,

datatype *pointer_name;

Data type of a pointer must be same as the data type of the variable to which the
pointer variable is pointing. void type pointer works with all data types, but is not often
used.

Here are a few examples:

int *ip // pointer to integer variable

float *fp; // pointer to float variable

double *dp; // pointer to double variable

char *cp; // pointer to char variable

Initialization of C Pointer variable

Pointer Initialization is the process of assigning address of a variable to

a pointer variable. Pointer variable can only contain address of a variable of the same
data type. In C language address operator & is used to determine the address of a
variable. The & (immediately preceding a variable name) returns the address of the
variable associated with it.

#include<stdio.h>
void main()
{
int a = 10;
int *ptr; //pointer declaration
ptr = &a; //pointer initialization
}
Pointer variable always point to variables of same datatype. Let's have an example to
showcase this:

#include<stdio.h>
void main()
{
float a;
int *ptr;
ptr = &a; // ERROR, type mismatch
}
If you are not sure about which variable's address to assign to a pointer variable while
declaration, it is recommended to assign a NULL value to your pointer variable. A pointer
which is assigned a NULL value is called a NULL pointer.

#include <stdio.h>
int main()
{
int *ptr = NULL;
return 0;
}

Accessing a variable through its pointer

Steps:

1. Declare a normal variable, assign the value

2. Declare a pointer variable with the same type as the normal variable
3. Initialize the pointer variable with the address of normal variable
4. Access the value of the variable by using asterisk (*) - it is known as dereference
operator

#include <stdio.h>

int main(void)

//normal variable

int num = 100;

//pointer variable

int *ptr;
 //pointer initialization

ptr = &num;

//pritning the value

printf("value of num = %d\n", *ptr);

return 0;

Output

value of num = 100

Points to remember while using pointers

1. While declaring/initializing the pointer variable, * indicates that the variable is a

pointer.
2. The address of any variable is given by preceding the variable name with
Ampersand &.
3. The pointer variable stores the address of a variable. The declaration int
*a doesn't mean that a is going to contain an integer value. It means that a is
going to contain the address of a variable storing integer value.
4. To access the value of a certain address stored by a pointer variable, * is used.
Here, the * can be read as 'value at'
Dynamic memory allocation – define static and dynamic
memory allocation
Static memory allocation

In Static Memory Allocation the memory for your data is allocated when the program
starts.

The size is fixed when the program is created.

This memory allocation is fixed and cannot be changed, i.e. increased or decreased after
allocation. So, exact memory requirements must be known in advance.

Key features:

· Variables get allocated permanently

· Allocation is done before program execution

· It uses the data structure called stack for implementing static allocation

· There is no memory reusability

Example:

All the variables in the program below are statically allocated.

void play

int a;

int main()

int b;

int c[10];

return 1;

}
Dynamic memory allocation

Since C is a structured language, it has some fixed rules for programming. One of it
includes changing the size of an array. An array is collection of items stored at
continuous memory locations.

As it can be seen that the length (size) of the array above made is 9. But what if there is a
requirement to change this length (size). For Example,

· If there is a situation where only 5 elements are needed to be entered in this array.
In this case, the remaining 4 indices are just wasting memory in this array. So there is a
requirement to lessen the length (size) of the array from 9 to 5.

· Take another situation. In this, there is an array of 9 elements with all 9 indices filled.
But there is a need to enter 3 more elements in this array. In this case 3 indices more are
required. So the length (size) of the array needs to be changed from 9 to 12.

This procedure is referred to as Dynamic Memory Allocation in C.

Therefore, C Dynamic Memory Allocation can be defined as a procedure in which:

· Dynamic Memory Allocation can be defined as a procedure in which the size of a

data structure is changed during the runtime.

· Dynamic allocation is useful when data structures need to be created whose size is
not known until run time

C provides some functions to achieve these tasks. There are 4 library functions provided
by C defined under <stdlib.h> header file to facilitate dynamic memory allocation in C
programming. They are:

1. malloc()

2. calloc()

3. free()

4. realloc()
memory allocation functions – malloc, calloc

Malloc

Memory allocation functions

There are 4 library functions provided by C defined under <stdlib.h> header file to
facilitate dynamic memory allocation in C programming. They are:

· malloc()

· calloc()

· free()

· realloc()

malloc():

“malloc” or “memory allocation” method in C is used to dynamically allocate a single

large block of memory with the specified size. It returns a pointer of type void which can
be cast into a pointer of any form.

Syntax:

ptr = (cast-type*) malloc(byte-size)

For Example:

ptr = (int*) malloc(100 * sizeof(int));

Since the size of int is 4 bytes, this statement will allocate 400 bytes of memory. And, the
pointer ptr holds the address of the first byte in the allocated memory.
malloc(): example

#include <stdio.h>

#include <stdlib.h>

int main()

int* ptr;

int n=5, i, sum = 0;

ptr = (int*)malloc(n * sizeof(int));

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

ptr[i] = i + 1;

printf("The elements of the array are: ");

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

printf("%d, ", ptr[i]);

return 0;

}
Calloc

calloc()

“calloc” or “contiguous allocation” method in C is used to dynamically allocate the

specified number of blocks of memory of the specified type. It also returns a pointer of
type void which can be cast into a pointer of any form. It initializes each block with a
default value ‘0’.

Syntax:

ptr = (cast-type*)calloc(n, element-size);

For Example:

ptr = (float*) calloc(25, sizeof(float));

This statement allocates contiguous space in memory for 25 elements each with the size
of the float.

#include <stdio.h>

#include <stdlib.h>

int main()

// This pointer will hold the

// base address of the block created

int* ptr;
int n, i;

// Get the number of elements for the array

n = 5;

printf("Enter number of elements: %d\n", n);

// Dynamically allocate memory using calloc()

ptr = (int*)calloc(n, sizeof(int));

// Check if the memory has been successfully

// allocated by calloc or not

if (ptr == NULL) {

printf("Memory not allocated.\n");

exit(0);

else {

// Memory has been successfully allocated

printf("Memory successfully allocated using calloc.\n");

// Get the elements of the array

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

ptr[i] = i + 1;

// Print the elements of the array

printf("The elements of the array are: ");

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

 printf("%d, ", ptr[i]);

return 0;

Output:

Enter number of elements: 5

Memory successfully allocated using calloc.
The elements of the array are: 1, 2, 3, 4, 5,
memory allocation functions – free, realloc

Realloc

realloc()

“realloc” or “re-allocation” method in C is used to dynamically change the memory

allocation of a previously allocated memory.

In other words, if the memory previously allocated with the help of malloc or calloc is
insufficient, realloc can be used to dynamically re-allocate memory.

Syntax:

ptr = realloc(ptr, newSize);

where ptr is reallocated with new size 'newSize'

Free

“free” method in C is used to dynamically de-allocate the memory.

The memory allocated using functions malloc() and calloc() is not de-allocated on their
own.
Hence the free() method is used, whenever the dynamic memory allocation takes place.
It helps to reduce wastage of memory by freeing it.

Syntax:

free(ptr);

memory allocation functions – free, realloc

Example

#include <stdio.h>

#include <stdlib.h>

int main()

// This pointer will hold the

// base address of the block created

int *ptr, *ptr1;

int n, i;

// Get the number of elements for the array

n = 5;

printf("Enter number of elements: %d\n", n);

// Dynamically allocate memory using malloc()

ptr = (int*)malloc(n * sizeof(int));

// Dynamically allocate memory using calloc()

ptr1 = (int*)calloc(n, sizeof(int));

// Check if the memory has been successfully

// allocated by malloc or not

if (ptr == NULL || ptr1 == NULL) {

printf("Memory not allocated.\n");

exit(0);

else {

// Memory has been successfully allocated

printf("Memory successfully allocated using malloc.\n");

 // Free the memory

free(ptr);

printf("Malloc Memory successfully freed.\n");

// Memory has been successfully allocated

printf("\nMemory successfully allocated using calloc.\n");

// Free the memory

free(ptr1);

printf("Calloc Memory successfully freed.\n");

return 0;

Output:

Enter number of elements: 5

Memory successfully allocated using malloc.

Malloc Memory successfully freed.

Memory successfully allocated using calloc.

Calloc Memory successfully freed.
Recursion - definition, types

Definition

Recursion is the process of repeating items in a self-similar way. In programming

languages, if a program allows you to call a function inside the same function, then it is
called a recursive call of the function.

void recursion() {
recursion(); /* function calls itself */
}

int main() {
recursion();
}
The C programming language supports recursion, i.e., a function to call itself. But while
using recursion, programmers need to be careful to define an exit condition from the
function, otherwise it will go into an infinite loop.

Recursive functions are very useful to solve many mathematical problems, such as
calculating the factorial of a number, generating Fibonacci series, etc.

A Mathematical Interpretation

Let us consider a problem that a programmer have to determine the sum of first n
natural numbers.

Recursive adding
f(n) = 1 n=1
f(n) = n + f(n-1) n>1
The function “ f( ) ” itself is being called inside the function, so this phenomenon is
named as recursion and the function containing recursion is called recursive function, at
the end this is a great tool in the hand of the programmers to code some problems in a
lot easier and efficient way.

What is base condition in recursion?

In the recursive program, the solution to the base case is provided and the solution of
the bigger problem is expressed in terms of smaller problems.

int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}

In the above example, base case for n < = 1 is defined and larger value of number can
be solved by converting to smaller one till base case is reached.

How a particular problem is solved using recursion?

The idea is to represent a problem in terms of one or more smaller problems, and add
one or more base conditions that stop the recursion. For example, we compute factorial
n if we know factorial of (n-1). The base case for factorial would be n = 0. We return 1
when n = 0.

Types
Recursion are mainly of two types depending on whether a function calls itself from
within itself or more than one function call one another mutually.

The first one is called direct recursion and another one is called indirect recursion.

Thus, the two types of recursion are:

1. Direct Recursion: These can be further categorized into four types:

· Tail Recursion: If a recursive function calling itself and that recursive call is the last
statement in the function then it’s known as Tail Recursion. After that call the recursive
function performs nothing. The function has to process or perform any operation at the
time of calling and it does nothing at returning time.

· Head Recursion: If a recursive function calling itself and that recursive call is the first
statement in the function then it’s known as Head Recursion. There’s no statement, no
operation before the call. The function doesn’t have to process or perform any operation
at the time of calling and all operations are done at returning time.

· Tree Recursion: To understand Tree Recursion let’s first understand Linear

Recursion. If a recursive function calling itself for one time then it’s known as Linear
Recursion. Otherwise if a recursive function calling itself for more than one time then it’s
known as Tree Recursion.

· Nested Recursion: In this recursion, a recursive function will pass the parameter as a
recursive call. That means “recursion inside recursion”. Let see the example to
understand this recursion.
2. Indirect Recursion: In this recursion, there may be more than one function and they
are calling one another in a circular manner.

From the above diagram fun(A) is calling for fun(B), fun(B) is calling for fun(C) and fun(C)
is calling for fun(A) and thus it makes a cycle.
Recursion - Writing recursive programs in C
Example: Sum of Natural Numbers Using Recursion

#include <stdio.h>
int sum(int n);

int main() {
int number, result;

printf("Enter a positive integer: ");

scanf("%d", &number);

result = sum(number);

printf("sum = %d", result);

return 0;
}

int sum(int n) {
if (n != 0)
// sum() function calls itself
return n + sum(n-1);
else
return n;
}

Output

Enter a positive integer:3

sum = 6

Explanation
Initially, the sum() is called from the main() function with number passed as an argument.
Suppose, the value of n inside sum() is 3 initially. During the next function call, 2 is
passed to the sum() function. This process continues until n is equal to 0.When n is equal
to 0, the if condition fails and the else part is executed returning the sum of integers
ultimately to the main() function.
Recursion - Binomial Coefficient, Fibonacci Series

Binomial Coefficient

A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion of
(1 + X)^n.

Where Binomial coefficient is

The Problem

Write a function that takes two parameters n and k and returns the value of Binomial
Coefficient C(n, k). For example, your function should return 6 for n = 4 and k = 2, and it
should return 10 for n = 5 and k = 2.

The Solution

The value of C(n, k) can be recursively calculated using following standard formula for
Binomial Coefficients.

C(n, k) = C(n-1, k-1) + C(n-1, k)

C(n, 0) = C(n, n) = 1
#include<stdio.h>

void main()

int n,r;

int fact(int);

clrscr();

printf("\nEnter the value for n:");

scanf("%d",&n);

printf("\nEnter the value for r:");

scanf("%d",&r);

if(n<r)

printf("Invalid Input\n");

else

printf("\nBinomial Coefficient nCr is %d",fact(n)/(fact(n-r)*fact(r)));

getch();

int fact(int x)

if(x==0||x==1)

return 1;

else

return(x*(fact(x-1)));

}
Recursion - Binomial Coefficient, Fibonacci Series

Fibonacci Series

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the

recurrence relation

Fn = Fn-1 + Fn-2

F0 = 0 and F1 = 1.

//Fibonacci Series using Recursion

#include<stdio.h>

int fib(int n)

if (n <= 1)

return n;

int num = fib(n-1) + fib(n-2);

return num;

int main ()

int n = 9;

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

printf("%d\n", fib(i));

return 0;

}
GCD, Tower of Hanoi

GCD

GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the
largest number that divides both of them.

// C program to find GCD of two numbers

#include<stdio.h>

void main()

int a,b,res;

clrscr();

printf("\nGreatest Common Divisor\n");

printf("Enter the value for a : ");

scanf("%d",&a);

printf("Enter the value for b : ");

scanf("%d",&b);

res=gcd(a,b);

printf("The Greatest Common Divisor of %d and %d is %d",a,b,res);

getch();

int gcd(int a,int b)

{
 if(a==b)

return(a);

else

if(a>b)

return(gcd(a-b,b));

else

return(gcd(a,b-a));

Tower of Hanoi

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks.

The objective of the puzzle is to move the entire stack to another rod, obeying the
following simple rules:
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on
top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.
Algorithm:

Step 1 − Move n-1 disks from source to aux

Step 2 − Move nth disk from source to dest

Step 3 − Move n-1 disks from aux to dest

Code:

#include<stdio.h>

#include<math.h>

void main()

int n;

char A,B,C;

void towers(int,char,char,char);

clrscr();
 printf("\nTowers of Hanoi\n");

printf("\nEnter the number of disks : ");

scanf("%d",&n);

printf("The number of moves=%0.f\n",(pow(2,n)-1));

printf("\nTowers of Hanoi simulation for %d disks\n",n);

towers(n,'A','C','B');

getch();

void towers(int n,char source,char dest,char aux)

if(n==1)

printf("\nMove disk %d from %c to %c",n,source,dest);

return;

towers(n-1,source,aux,dest);

printf("\nMove disk %d from %c to %c",n,source,dest);

towers(n-1,aux,dest,source);

}
Output

(A-SOURCE, B-AUX, C-DEST)

Towers of Hanoi

Enter the number of disks : 3

The number of moves=7

Towers of Hanoi simulation for 3 disks

Move disk 1 from A to C

Move disk 2 from A to B

Move disk 1 from C to B

Move disk 3 from A to C

Move disk 1 from B to A

Move disk 2 from B to C

Move disk 1 from A to C

 UNIT-2

SEARCHING && SORTING

INTRODUCTION
Searching: Introduction

Searching refers to finding for an item in any list. It is one of the common operations in
data processing. Searching should be efficient and quick as the list may be large and
large amount of data has to be processed. The programmer has to select the best
technique to the given problem. Searching is made easy when the list is sorted.

Basic Search Techniques

The searching technique that is being followed in the data structure is listed below:

1. Linear Search or Sequential Search

2. Binary Search

Linear Search or Sequential Search: In this technique of searching, the element to be

found in searching the elements to be found is searched sequentially in the list. This
method can be performed on a sorted or an unsorted list (usually arrays). In case of a
sorted list searching starts from 0th element and continues until the element is found
from the list or the element whose value is greater than (assuming the list is sorted in
ascending order), the value being searched is reached.

Binary Search: It is a very fast and efficient searching technique. It requires the list to be
in sorted order. In this method, to search an element you can compare it with the
present element at the centre of the list. If it matches, then the search is successful
otherwise the list is divided into two halves: one from the 0th element to the middle
element which is the centre element (first half) another from the centre element to the
last element (which is the 2nd half) where all values are greater than the centre element.

The searching mechanism proceeds from either of the two halves depending upon
whether the target element is greater or smaller than the central element. If the element
is smaller than the central element, then searching is done in the first half, otherwise
searching is done in the second half.
LINEAR / SEQUENTIAL SEARCH
Define Linear Search

Linear / Sequential Search

It is the simplest of all the searching techniques which does not expect the specific
ordering of data. Sequential search is nothing but searching an element / record in a
linear way. This can be in arrays or in linked lists.

Linear search algorithm finds a given element on a list of elements with O(n) time
complexity where n is the total number of elements in the lists. Start the search from the
beginning by comparing the ‘key’ in each case and by scanning all the elements one by
one until the end of the array or the linked list. If search is successful, the entire record
of that particular ‘key’ or the index of the record or the pointer to the record is returned.
If the search is unsuccessful, it gives a failure notification ‘-1’ is returned.

LINEAR / SEQUENTIAL SEARCH

Steps to be followed to implement the linear / Sequential search

Linear search is implemented using the following steps

Step 1: Read the search element (key).

Step 2: Compare the search element with the first element in the list.

Step 3: If both are matched, then display search element is found and terminate
the function.

Step 4: If both are not matched, then compare search element with the next element in
the list

Step 5: Repeat the Steps 3 & 4 until the search element is compared with the last
element in the list.

Step 6: If the last element in the list does not match, then display element not
found and terminate the function.
Algorithm

Algorithm: Linear Search

Algorithm: Linear Search (list [ ], n, key)

Let list [ ] be a linear array with n elements and key is an element to be searched in the
list

Step 1: Set i = 0

Step 2: while (i < n) do

If list [i] == key then

return i; //Key found at ith location

end while

Step 3: return -1; //key not found

Example

Example - Linear Search

Consider the following list of elements and element to be searched:

Search element (Key): 12

Step 1: Search element 12 is compared with the first element 65

Both are not matching, so move to the next element.

Step 2: Search element 12 is compared with the next element 20

Both are not matching, so move to the next element.

Step 3: Search element 12 is compared with the next element 10

Both are not matching, so move to the next element.

Step 4: Search element 12 is compared with the next element 55

Both are not matching, so move to the next element.

Step 5: Search element 12 is compared with the next element 32

Both are not matching, so move to the next element.

Step 6: Search element 12 is compared with the next element 12

Both are matching, so move to the next element. Terminate the function and display the
element found at index ‘5’.
BINARY SEARCH
Binary Search: Definition

Binary Search

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This
search algorithm works on the principle of divide and conquers. For this algorithm to
work properly, the data collection should be in the sorted form.

Binary search looks for a particular item by comparing the middle most item of the
collection. If a match occurs, then the index of item is returned. If the middle item is
greater than the item, then the item is searched in the sub-array to the left of the middle
item. Otherwise, the item is searched for in the sub-array to the right of the middle item.
This process continues on the sub-array as well until the size of the subarray reduces to
zero.

How the binary search works ?

Consider an array ‘A’ sorted in ascending order has the elements
between A[first] and A[last]. It should always be noted that the item to be searched
should lie between these elements A[first] and A[last]. So consider the ‘key item’ to be
searched, then key item should lie between A[first] and A[last]. Initially first is set
to ‘0’ the last is set to ‘(n-1)’ where ‘n’ is the size of the array.

Algorithm: Binary Search

Algorithm: Binary Search (A [0, 1, 2, ................ n-1], item)

Input: Given an array A of n elements in sorted order and item is an element to be

searched.

Output: Returns the position of item element if successful and returns -1 otherwise,
Step 1: set first = 0, last = n – 1

Step 2: while (first <= last)

mid = (first + last) / 2

if (item == A[mid])

return (mid + 1);

else if (item < A[mid])

last = mid – 1

else

first = mid + 1

end while

Step 3: return -1

Example

Step 1: Determine half of the array by using this formula,

Here it is, 0 + (9 - 0) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.
Step 2: Compare the value stored at location 4, with the value being searched, i.e. 31.
We find that the value at location 4 is 27, which is not a match. As the value is greater
than 27 and we have a sorted array, so we also know that the target value must be in the
upper portion of the array.

Step 3: Change the low to mid + 1 and find the new mid value again.

The new mid is 7 now. We compare the value stored at location 7 with our target value
31. That is (5 + 9) / 2 = 7.

Step 4: The value stored at location 7 is not a match. So, the value must be in the lower
part from this location.

That is, (6 + 5) / 2 = 5

Compare the value stored at location 5 with our target value. The match is found.

Binary search halves the searchable items and thus reduces the count of
comparisons to be made to very less numbers.
 COMPARISON BETWEEN SEQUENTIAL AND BINARY
SEARCH
Comparison: Sequential / Linear Search & Binary Search

Basis of
Linear / Sequential Search Binary Search
comparison
Linear search is an algorithm to find an
Binary search is an algorithm that finds the
element in a list by sequentially
Description position of a target value within a sorted
checking the elements of the list until
array.
finding the matching element.
A binary search cuts down the search to half
A linear search scans one item at a time
How It Works as soon as the middle of a sorted list is
without skipping to any item.
found.
Linear searches may be implemented on Binary searches can only be implemented on
Implementation any linear container (vector, Single data structures where two-way traversal is
Linked list, double linked list). possible.
Dimensional It can be implemented on both a single It can be implemented only on a
array and multidimensional array. multidimensional array.
Algorithm type Iterative in nature Divide and conquer in nature
Usefulness Easy to use and no need for any ordered Anyhow tricky algorithm and elements
elements. should be organized in order.
Lines of Code Less More
Linear search is easy to use because The binary search is a bit complicated with
Complexity there is no need for any ordered elements being necessarily arranged in a
elements. given order.
Size It is preferable for the small-sized data It is preferable for the large-size data sets.
sets.
Linear search does not require the A binary search requires sorted arrays for
sorted elements hence the elements are effective performance. This facilitates
Sorted Elements
conveniently inserted at the bottom of insertion of elements at their required place
the list. and in essence maintaining sorted lists.
Linear search is repetitive or iterative as
Binary search employs divide and conquer
Approach well as uses the sequential approach in
approach in its functionality.
its functionality.
In linear search, performance is done by In binary search, performance is done by
Performance
equality comparisons. ordering comparisons.
In the linear search, worst case scenario
Worse-Case In the binary search, the worst case scenario
for searching an element is equivalent
Scenario is O(Log2n) number of similarities.
to O(n) number of comparison.
The best case scenario in a linear search
Best-Case The best case scenario is to find the element
is to find the element in the first
Scenario in the middle position O(1).
position O(1).
Time The time complexity of linear search The time complexity of binary
Complexity happens to be O(n). search is O(log2n).
ITERATIVE AND RECURSIVE METHODS
Definition: Iterative & Recursion

ITERATIVE AND RECURSIVE METHODS

The recursion and iteration both repeatedly execute the set of

instructions. Recursion is when a statement in a function calls itself repeatedly.
The iteration is when a loop repeatedly executes until the controlling condition
becomes false. The primary difference between recursion and iteration is
that recursion is a process, always applied to a function and iteration is applied to
the set of instructions which we want to get repeatedly executed.

Differences: Iterative and Recursion

Property Recursion Iteration
A set of instructions repeatedly
Definition Function calls itself.
executed.
Application For functions. For loops.
Through base case, where there will When the termination condition for the
Termination
be no function call. iterator ceases to be satisfied.
Used when code size needs to be Used when time complexity needs to
Usage small, and time complexity is not an be balanced against an expanded code
issue. size.
Code Size Smaller code size Larger Code Size.
Time Complexity Very high time complexity. Relatively lower time complexity

Properties
A recursive function can go infinite like a loop. To avoid infinite running of recursive
function, there are two properties that a recursive function must have:

 Base criteria − There must be at least one base criteria or condition, such that,
when this condition is met the function stops calling itself recursively.
 Progressive approach − The recursive calls should progress in such a way that
each time a recursive call is made it comes closer to the base criteria.
Implementation
Many programming languages implement recursion by means of stacks. Generally,
whenever a function (caller) calls another function (callee) or itself as callee, the caller
function transfers execution control to the callee. This transfer process may also involve
some data to be passed from the caller to the callee.

This implies, the caller function has to suspend its execution temporarily and resume
later when the execution control returns from the callee function. Here, the caller
function needs to start exactly from the point of execution where it puts itself on hold. It
also needs the exact same data values it was working on. For this purpose, an activation
record (or stack frame) is created for the caller function.

This activation record keeps the information about local variables, formal parameters,
return address and all information passed to the caller function.

Analysis of Recursion
One may argue why to use recursion, as the same task can be done with iteration. The first
reason is, recursion makes a program more readable and because of latest enhanced CPU
systems, recursion is more efficient than iterations.

Time Complexity
In case of iterations, we take number of iterations to count the time complexity. Likewise, in
case of recursion, assuming everything is constant, we try to figure out the number of times a
recursive call is being made. A call made to a function is Ο(1), hence the (n) number of times
a recursive call is made makes the recursive function Ο(n).

Space Complexity
Space complexity is counted as what amount of extra space is required for a module to
execute. In case of iterations, the compiler hardly requires any extra space. The compiler
keeps updating the values of variables used in the iterations. But in case of recursion, the
system needs to store activation record each time a recursive call is made. Hence, it is
considered that space complexity of recursive function may go higher than that of a function
with iteration.
TOWER OF HANOI
Objective: Tower of Hanoi

It is a mathematical game or puzzle. It consists of three rods and a number of disks of

different sizes, which can slide onto any rod. The puzzle starts with the disks in a
neat stack in ascending order of size on one rod, the smallest at the top, thus making
a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the
following simple rules:

1. Only one disk can be moved at a time.

2. Each move consists of taking the upper disk from one of the stacks and placing it
on top of another stack or on an empty rod.
3. No larger disk may be placed on top of a smaller disk.

Solving a Tower of Hanoi puzzle with three disks

Step 0:
Step 1:

Step 2:

Step 3:

Step 4:

Step 5:
Step 6:

Step 7:

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves
required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.

Algorithm
To write an algorithm for Tower of Hanoi, first we need to learn how to solve this
problem with lesser amount of disks, say → 1 or 2. Mark three towers with
name, source, destination and aux (only to help moving the disks). If we have only one
disk, then it can easily be moved from source to destination peg.
If we have 2 disks:

 First, we move the smaller (top) disk to aux peg.

 Then, we move the larger (bottom) disk to destination peg.
 And finally, we move the smaller disk from aux to destination peg.

In a position to design an algorithm for Tower of Hanoi with more than two disks. We
divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other
(n-1) disks are in the second part.

Our ultimate aim is to move disk n from source to destination and then put all other (n1)
disks onto it. We can imagine to apply the same in a recursive way for all given set of
disks.

The steps to follow are:

Step 1 − Move n-1 disks from source to aux

Step 2 − Move nth disk from source to dest

Step 3 − Move n-1 disks from aux to dest

A recursive algorithm for Tower of Hanoi can be driven as follows:

START

Procedure Hanoi (disk, source, dest, aux)

IF disk == 1, THEN

move disk from source to dest

ELSE

Hanoi(disk - 1, source, aux, dest) // Step 1

move disk from source to dest // Step 2

Hanoi(disk - 1, aux, dest, source) // Step 3

END IF

END Procedure

STOP
FIBONACCI SERIES: Definition
Fibonacci series generates the subsequent number by adding two previous numbers.
Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be
taken 0, 1 or 1, 1 respectively.

Fibonacci series satisfies the following conditions:

Example & Algorithm

Example: F = 0 1 1 2 3 5 8 13 21

The solution as,

0 + 1 = 1 + 2 = 3 + 5 = 8 + 13 = 21

Fibonacci Iterative Algorithm

Procedure Fibonacci(n)

declare f0, f1, fib, loop

set f0 to 0

set f1 to 1

display f0, f1

for loop ← 1 to n

fib ← f0 + f1

f0 ← f1

f1 ← fib

display fib
 end for

end procedure

Fibonacci Recursive Algorithm

START

Procedure Fibonacci(n)

declare f0, f1, fib, loop

set f0 to 0

set f1 to 1

display f0, f1

for loop ← 1 to n

fib ← f0 + f1

f0 ← f1

f1 ← fib

display fib

end for

END
SORTING
Definition & Importance : Sorting

Sorting refers to arranging data in a particular format. Sorting algorithm specifies the
way to arrange data in a particular order. Most common orders are in numerical or
lexicographical order.

The importance of sorting lies in the fact that data searching can be optimized to a
very high level, if data is stored in a sorted manner. Sorting is also used to represent data
in more readable formats.

Adaptive and Non-Adaptive Sorting Algorithm

A sorting algorithm is said to be adaptive, if it takes advantage of already 'sorted'

elements in the list that is to be sorted.

A non-adaptive algorithm is one which does not take into account the elements which
are already sorted.

Types of Sorting:

Adaptive sorting algorithms:

1. Bubble Sort
2. Insertion Sort
3. Quick Sort

Non-adaptive sorting algorithms:

1. Selection Sort
2. Merge Sort
3. Heap Sort
Important Terms: Sorting
Some terms are generally coined while discussing sorting techniques:

 Increasing Order: A sequence of values is said to be in increasing order, if the

successive element is greater than the previous one. For example, 1, 3, 4, 6, 8, 9
are in increasing order, as every next element is greater than the previous
element.
 Decreasing Order: A sequence of values is said to be in decreasing order, if the
successive element is less than the current one. For example, 9, 8, 6, 4, 3, 1 are in
decreasing order, as every next element is less than the previous element.
 Non-Increasing Order: A sequence of values is said to be in non-increasing
order, if the successive element is less than or equal to its previous element in the
sequence. This order occurs when the sequence contains duplicate values. For
example, 9, 8, 6, 3, 3, 1 are in non-increasing order, as every next element is less
than or equal to (in case of 3) but not greater than any previous element.
 Non-Decreasing Order: A sequence of values is said to be in non-decreasing
order, if the successive element is greater than or equal to its previous element in
the sequence. This order occurs when the sequence contains duplicate values. For
example, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next element is
greater than or equal to (in case of 3) but not less than the previous one.
BUBBLE SORT
Definition: Bubble Sort

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based

algorithm in which each pair of adjacent elements is compared and the elements are
swapped if they are not in order. This algorithm is not suitable for large data sets as its
average and worst case complexity are of Ο(n2) where n is the number of items.

Example : Bubble Sort

Step 1: Bubble sort starts with very first two elements, comparing them to check which
one is greater.

Step 2: In this case, value 33 is greater than 14, so it is already in sorted locations. Next,
we compare 33 with 27.

27 is smaller than 33 and these two values must be swapped.

Step 3: Next compare 33 and 35. We find that both are in already sorted positions.
Step 4: Move to the next two values, 35 and 10.

Swap these values. Find that reached the end of the array. After one iteration, the array
should look like this,

To be precise, showing how an array should look like after each iteration. After the
second iteration, it should look like this,

After each iteration, at least one value moves at the end.

There is no swap required, bubble sorts, an array is completely sorted.

Algorithm

Assume list is an array of n elements. The swap function swaps the values of the given
array elements.

begin BubbleSort(list)

for all elements of list

if list[i] > list[i+1]

swap(list[i], list[i+1])

end if

end for

return list

end BubbleSort
INSERTION SORT
Definition : Insertion Sort

It is an in-place comparison-based sorting algorithm. A sub-list is maintained which is

always sorted. For example, the lower part of an array is maintained to be sorted. An
element which is to be inserted in this sorted sub-list, has to find its appropriate place
and then it has to be inserted there. Hence the name, insertion sort.

The array is searched sequentially and unsorted items are moved and inserted into the
sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its
average and worst case complexity are of Ο(n2), where n is the number of items.

Example

Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-
list.

Insertion sort moves ahead and compares 33 with 27.

Found that 33 is not in the correct position.

It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here that the
sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted
sub-list remains sorted after swapping.

But now 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.

These values are not in a sorted order.

So swapping take place,

Swapping makes 27 and 10 unsorted and swap it

Swapping makes 14 and 10 unsorted and swap it

Finally, the sorted element in the insertion sort will be as,

Algorithm
Step 1: If it is the first element, it is already sorted. return 1;

Step 2: Pick next element

Step 3: Compare with all elements in the sorted sub-list

Step 4: Shift all the elements in the sorted sub-list that is greater than the value to be
sorted

Step 5: Insert the value

Step 6: Repeat until list is sorted

procedure insertionSort( A : array of items )

int holePosition

int valueToInsert

for i = 1 to length(A) inclusive do: /* select value to be inserted */

valueToInsert = A[i]

holePosition = i /*locate hole position for the element to be inserted */

while holePosition > 0 and A[holePosition-1] > valueToInsert do:

A[holePosition] = A[holePosition-1]

holePosition = holePosition -1

end while

/* insert the number at hole position */

A[holePosition] = valueToInsert

end for

end procedure
QUICK SORT
Definition: Quick Sort

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array
of data into smaller arrays. A large array is partitioned into two arrays one of which holds
values smaller than the specified value, say pivot, based on which the partition is made
and another array holds values greater than the pivot value.

Quicksort partitions an array and then calls itself recursively twice to sort the two
resulting subarrays. This algorithm is quite efficient for large-sized data sets as its
average and worst-case complexity are O(n2), respectively.

 Quick sort is also known as Partition-exchange sort based on the rule of Divide
and Conquer.
 It is a highly efficient sorting algorithm.
 Quick sort is the quickest comparison-based sorting algorithm.
 Quick sort picks an element as pivot and partitions the array around the picked
pivot.

Steps to be followed for Quick Sort

Step 1: Choose the highest index value as pivot.

Step 2: Take two variables to point left and right of the list excluding pivot.
Step 3: Left points to the low index.
Step 4: Right points to the high index.
Step 5: While value at left < (Less than) pivot move right.
Step 6: While value at right > (Greater than) pivot move left.
Step 7: If both Step 5 and Step 6 does not match, swap left and right.
Step 8: If left = (Less than or Equal to) right, the point where they met is new pivot.
Example

Let select the highest index as ‘pivot’

Compare the low and upper end values with the pivot, 36 > 32 & 27 < 32. Since 27 is
less than 36, swapping takes place.

Compare, 34 > 32 & 45 > 32. Since both the values at the low and upper end are greater
than pivot value 32, so swapping.

Compare, 34 > 32 & 27 < 32. Swapping takes place.

Compare, 43 > 32 & 20 < 32. Swapping takes place.

Swapping takes place,

The pivot value divides the list into two parts. And recursively, find the pivot for each
sub-lists until all lists contains only one element.

Algorithm
Procedure: Quick Sort

procedure quickSort(left, right)

if right-left <= 0

return

else

pivot = A[right]

partition = partitionFunc(left, right, pivot)

quickSort(left, partition-1)

quickSort(partition+1, right)

end if

end procedure
SELECTION SORT
Definition : Selection Sort

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-

place comparison-based algorithm in which the list is divided into two parts, the sorted
part at the left end and the unsorted part at the right end. Initially, the sorted part is
empty and the unsorted part is the entire list.

The smallest element is selected from the unsorted array and swapped with the leftmost
element, and that element becomes a part of the sorted array. This process continues
moving unsorted array boundary by one element to the right.

This algorithm is not suitable for large data sets as its average and worst case
complexities are of Ο(n2), where n is the number of items.

Example : Selection Sort

Step 1: Find the smallest element. Compare the smallest element 11 with the first
element in the array 64.

Since 11 is less than 64, so swap it

Step 2: Start scanning the entire list, and find the next least element i.e 12. It is
compared the element in the second position 25. Compare and swap it

Step 3: Start scanning the entire list, and find the next least element i.e 22. It is
compared the element in the third position 25. Compare and swap it
The list is completely sorted.

Algorithm

Steps to be followed for Selection Sort:

Step 1 − Set MIN to location 0

Step 2 − Search the minimum element in the list

Step 3 − Swap with value at location MIN

Step 4 − Increment MIN to point to next element

Step 5 − Repeat until list is sorted

Algorithm: Selection Sort

procedure selection sort

list : array of items

n : size of list

for i = 1 to n - 1

/* set current element as minimum*/

min = i

/* check the element to be minimum */

for j = i+1 to n

if list[j] < list[min] then

 min = j;

end if

end for

/* swap the minimum element with the current element*/

if indexMin != i then

swap list[min] and list[i]

end if

end for

end procedure
MERGE SORT
Definition: Merge Sort

Merge sort is one of the most efficient sorting algorithms. It works on the principle of
Divide and Conquer. Merge sort repeatedly breaks down a list into several sublists until
each sublist consists of a single element and merging those sublists in a manner that
results into a sorted list.

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into ‘n’ sublists, each containing one element (a list of one
element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only one
sublist remaining. This will be the sorted list.

Example: Merge Sort

Step 1: Merge sort first divides the whole array iteratively into equal halves unless the
atomic values are achieved.

Step 2: This does not change the sequence of appearance of items in the original. Now
divide these two arrays into halves.

Step 3: Further divide these arrays and we achieve atomic value which can no more be
divided.
Step 4: First compare the element for each list and then combine them into another list
in a sorted manner. We see that 14 and 33 are in sorted positions. We compare 27 and
10 and in the target list of 2 values we put 10 first, followed by 27. We change the order
of 19 and 35 whereas 42 and 44 are placed sequentially.

Step 5: In the next iteration of the combining phase, compare lists of two data values,
and merge them into a list of found data values placing all in a sorted order.

Step 6: After the final merging.

Merge sort keeps on dividing the list into equal halves until it can no more be divided. By
definition, if it is only one element in the list, it is sorted. Then, merge sort combines the
smaller sorted lists keeping the new list sorted too.

Algorithm: Merge Sort

Step 1 − if it is only one element in the list it is already sorted, return.

Step 2 − divide the list recursively into two halves until it can no more be divided.

Step 3 − merge the smaller lists into new list in sorted order.
Algorithm:
procedure mergesort( var a as array )

if ( n == 1 ) return a

var l1 as array = a[0] ... a[n/2]

var l2 as array = a[n/2+1] ... a[n]

l1 = mergesort( l1 )

l2 = mergesort( l2 )

return merge( l1, l2 )

end procedure

procedure merge( var a as array, var b as array )

var c as array

while ( a and b have elements )

if ( a[0] > b[0] )

add b[0] to the end of c

remove b[0] from b

else

add a[0] to the end of c

remove a[0] from a

end if

end while

while ( a has elements )

add a[0] to the end of c

remove a[0] from a

end while

while ( b has elements )

add b[0] to the end of c

remove b[0] from b

end while

return c

end procedure
HEAP SORT
Definition

Example

Algorithm - maxHeap

Definition: Heap Sort

Heap is a special case of balanced binary tree data structure where the root-node key is
compared with its children and arranged accordingly. If α has child node β then,

As the value of parent is greater than that of child, this property generates Max Heap.
Based on this criteria, a heap can be of two types:

Min-Heap, where the value of the root node is less than or equal to either of its children.

Max-Heap, where the value of the root node is greater than or equal to either of its
children.

Both trees are constructed using the same input and order of arrival.

Steps to be followed for heap sort

Step 1 − Create a new node at the end of heap.

Step 2 − Assign new value to the node.

Step 3 − Compare the value of this child node with its parent.

Step 4 − If value of parent is less than child, then swap them.

Step 5 − Repeat step 3 & 4 until Heap property holds.

HEAP SORT
Definition: Heap Sort

Heap is a special case of balanced binary tree data structure where the root-node key is
compared with its children and arranged accordingly. If α has child node β then,

As the value of parent is greater than that of child, this property generates Max Heap.
Based on this criteria, a heap can be of two types:

Min-Heap, where the value of the root node is less than or equal to either of its children.

Max-Heap, where the value of the root node is greater than or equal to either of its
children.

Both trees are constructed using the same input and order of arrival.
Steps to be followed for heap sort

Step 1 − Create a new node at the end of heap.

Step 2 − Assign new value to the node.

Step 3 − Compare the value of this child node with its parent.

Step 4 − If value of parent is less than child, then swap them.

Step 5 − Repeat step 3 & 4 until Heap property holds.

Example

Input → 35 33 42 10 14 19 27 44 26 31

Step 1:

Step 2:
Step 3:

Step 4:

Step 5:
Algorithm: maxHeap
procedure heapsort(a, count) is

input: an unordered array a of length count

(Build the heap in array a so that largest value is at the root)

heapify(a, count)

(The following loop maintains the invariants that a[0:end] is a heap and every element

beyond end is greater than everything before it (so a[end:count] is in sorted order))

end ← count - 1

while end > 0 do

(a[0] is the root and largest value. The swap moves it in front of the sorted elements.)

swap(a[end], a[0])

(the heap size is reduced by one)

end ← end - 1

(the swap ruined the heap property, so restore it)

siftDown(a, 0, end)
 UNIT-3

STACK
What is a Stack?

A Stack is an Abstract Data Type (ADT), commonly used in most programming

languages.

It is named stack as it behaves like a real-world stack, for example – a deck of cards or a
pile of plates, etc.

A real-world stack allows operations at one end only.

For example, we can place or remove a card or plate from the top of the stack only.
Likewise, Stack ADT allows all data operations at one end only. At any given time, we can
only access the top element of a stack.

It is a simple data structure that allows adding and removing elements in a particular
order. Every time an element is added, it goes on the top of the stack and the only
element that can be removed is the element that is at the top of the stack, just like a pile
of objects.

This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the
element which is placed (inserted or added) last, is accessed first. In stack terminology,
insertion operation is called PUSH operation and removal operation is
called POP operation.

Operations on Stack

Stack Operations
The following diagram depicts a stack and its operations −

RULE :: LIFO(Last In First Out) or FILO(First In Last Out).

Mainly the following basic operations are performed in the stack:

 Push: Adds an item in the stack. If the stack is full, then it is said to be an
Overflow condition.
 Pop: Removes an item from the stack. The items are popped in the reversed
order in which they are pushed. If the stack is empty, then it is said to be an
Underflow condition.
 Peek or Top: Returns top element of stack.
 isEmpty: Returns true if stack is Empty, else false.
 isFull : Returns true if stack is Full, else false
Push Operation
The process of putting a new data element onto stack is known as a Push Operation.
Push operation involves a series of steps −

 Step 1 − Checks if the stack is full.

 Step 2 − If the stack is full, produces an error and exit.
 Step 3 − If the stack is not full, increments top to point next empty space.
 Step 4 − Adds data element to the stack location, where top is pointing.
 Step 5 − Returns success.

If the linked list is used to implement the stack, then in step 3, we need to allocate space
dynamically.

Pop Operation
Accessing the content while removing it from the stack, is known as a Pop Operation. In
an array implementation of pop() operation, the data element is not actually removed,
instead top is decremented to a lower position in the stack to point to the next value.
But in linked-list implementation, pop() actually removes data element and deallocates
memory space.

A Pop operation may involve the following steps −

 Step 1 − Checks if the stack is empty.

 Step 2 − If the stack is empty, produces an error and exit.
 Step 3 − If the stack is not empty, accesses the data element at which top is
pointing.
 Step 4 − Decreases the value of top by 1.
 Step 5 − Returns success.
Implementation of Stack - Using Arrays

Stack Operations using Array

A stack data structure can be implemented using a one-dimensional array.
But stack implemented using array stores only a fixed number of data values. This
implementation is very simple. Just define a one dimensional array of specific size and
insert or delete the values into that array by using LIFO principle with the help of a
variable called 'top'. Initially, the top is set to -1. Whenever we want to insert a value into
the stack, increment the top value by one and then insert. Whenever we want to delete a
value from the stack, then delete the top value and decrement the top value by one.

A stack can be implemented using array as follows...

Before implementing actual operations, first follow the below steps to create an
empty stack.

 Step 1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.
 Step 2 - Declare all the functions used in stack implementation.
 Step 3 - Create a one dimensional array with fixed size (int stack[SIZE])
 Step 4 - Define a integer variable 'top' and initialize with '-1'. (int top = -1)
 Step 5 - In main method, display menu with list of operations and make suitable
function calls to perform operation selected by the user on the stack.

push(value) - Inserting value into the stack

In a stack, push() is a function used to insert an element into the stack. In a stack, the
new element is always inserted at top position. Push function takes one integer value as
parameter and inserts that value into the stack. We can use the following steps to push
an element on to the stack...

 Step 1 - Check whether stack is FULL. (top == SIZE-1)

 Step 2 - If it is FULL, then display "Stack is FULL!!! Insertion is not
possible!!!" and terminate the function.
 Step 3 - If it is NOT FULL, then increment top value by one (top++) and
set stack[top] to value (stack[top] = value).

pop() - Delete a value from the Stack

In a stack, pop() is a function used to delete an element from the stack. In a stack, the
element is always deleted from top position. Pop function does not take any value as
parameter. We can use the following steps to pop an element from the stack...
  Step 1 - Check whether stack is EMPTY. (top == -1)
 Step 2 - If it is EMPTY, then display "Stack is EMPTY!!! Deletion is not
possible!!!" and terminate the function.
 Step 3 - If it is NOT EMPTY, then delete stack[top] and decrement top value by
one (top--).

display() - Displays the elements of a Stack

We can use the following steps to display the elements of a stack...

 Step 1 - Check whether stack is EMPTY. (top == -1)

 Step 2 - If it is EMPTY, then display "Stack is EMPTY!!!" and terminate the
function.
 Step 3 - If it is NOT EMPTY, then define a variable 'i' and initialize with top.
Display stack[i] value and decrement i value by one (i--).
 Step 3 - Repeat above step until i value becomes '0'.

Limitations:

Once a size of the array is declared, it cannot be modified during program execution.

If the reserved memory is more, then the memory will be wasted.

Therefore this method is suitable only when we know exactly the number of elements to
be stored..

An array can be declared large enough for the maximum size of the stack. A variable
TOP, which specifies the position of the top item of the stack, is maintained. Insertions
and deletions are done with the help of this variable

Stack Using Linked List

The major problem with the stack implemented using an array is, it works only for a fixed
number of data values. That means the amount of data must be specified at the
beginning of the implementation itself. Stack implemented using an array is not suitable,
when we don't know the size of data which we are going to use. A stack data structure
can be implemented by using a linked list data structure. The stack implemented using
linked list can work for an unlimited number of values. That means, stack implemented
using linked list works for the variable size of data. So, there is no need to fix the size at
the beginning of the implementation. The Stack implemented using linked list can
organize as many data values as we want.
In linked list implementation of a stack, every new element is inserted as 'top' element.
That means every newly inserted element is pointed by 'top'. Whenever we want to
remove an element from the stack, simply remove the node which is pointed by 'top' by
moving 'top' to its previous node in the list. The next field of the first element must be
always NULL.

Example

In the above example, the last inserted node is 99 and the first inserted node is 25. The
order of elements inserted is 25, 32,50 and 99.

Stack Operations using Linked List

To implement a stack using a linked list, we need to set the following things before
implementing actual operations.

 Step 1 - Include all the header files which are used in the program. And declare
all the user defined functions.
 Step 2 - Define a 'Node' structure with two members data and next.
 Step 3 - Define a Node pointer 'top' and set it to NULL.
 Step 4 - Implement the main method by displaying Menu with list of operations
and make suitable function calls in the main method.
Polish and Reverse Polish Notation

The way to write arithmetic expression is known as a notation. An arithmetic expression

can be written in three different but equivalent notations, i.e., without changing the
essence or output of an expression. These notations are −

 Infix Notation
 Prefix (Polish) Notation
 Postfix (Reverse-Polish) Notation

These notations are named as how they use operator in expression. We shall learn the
same here in this chapter.

Infix Notation
We write expression in infix notation, e.g. a - b + c, where operators are used in-
between operands. It is easy for us humans to read, write, and speak in infix notation but
the same does not go well with computing devices. An algorithm to process infix
notation could be difficult and costly in terms of time and space consumption.

Prefix Notation
In this notation, operator is prefixed to operands, i.e. operator is written ahead of
operands. For example, +ab. This is equivalent to its infix notation a + b. Prefix notation
is also known as Polish Notation.

Postfix Notation
This notation style is known as Reversed Polish Notation. In this notation style, the
operator is postfixed to the operands i.e., the operator is written after the operands. For
example, ab+. This is equivalent to its infix notation a + b.

The following table briefly tries to show the difference in all three notations −

Postfix
Sl.No. Infix Notation Prefix Notation
Notation
1 a+b +ab ab+
2 (a + b) ∗ c ∗+abc ab+c∗
3 a ∗ (b + c) ∗a+bc abc+∗
ab/cd/
4 a/b+c/d +/ab/cd
+
ab+cd+
5 (a + b) ∗ (c + d) ∗+ab+cd
∗
ab+c∗d
6 ((a + b) ∗ c) - d -∗+abcd
-
Operations on Stack

Stack operations:

1) Creating a stack

2) Checking the status of a stack whether it is empty of full

3) Initializing a stack

4) Inserting or pushing an element into a stack

5) Deleting or popping an element from a stack

6) Accessing the top element

7) Displaying the elements of stack

8) Identify the current position of top of stack

1) Creating a stack:

à Creating a stack with n elements

void createstack( )

printf(“\n Enter the number of elements in the stack:”);

scanf(“%d”,&n);

for(top=0;top<n;top++)

scanf(“%d”,&st[top]);

}
2) Checking the status of a stack whether empty or full

The isempty() operation is used to find whether stack contains any element or
not. If stack is empty, which is denoted by top=-1, it returns true. Otherwise if stack is
not empty, it returns false. This function is mainly used to test stack underflow
condition.

int isempty( )

if(top = = -1)

return 1;

else

return 0;

The isfull( ) operation is used to find whether stack contains all elements ie
whether the stack of size MAXSTK is completely filled with elements. If stack is full, it is
indicated by top=MAXSTK-1, and it returns true. Otherwise, it returns false. This
function is mainly used to test stack overflow condition.

int isfull( )

if(top = = MAXSTK-1)

return 1;

else

return 0;

}
3) Initializing a stack

int stack[MAXSTK] = { 0 };

4) Push operation:

Insertion is placing an item in the stack and is referred as PUSH operation.

The most important property of a stack is that the last element inserted into the stack is
the first element to be deleted.

For this reason, a stack is sometimes called as last-in, first-out (LIFO) list.

Algorithm for pushing (inserting) an element in stack:

PUSH (S, TOP, X) – This algorithm inserts an element x to the top of the stack which is
represented by a vector S containing N elements with a pointer Top denoting the Top
element in the stack.

1. [Check for stack overflow]

if Top = MAXSTK-1

then write (‘STACK OVERFLOW’)

2. [Increment Top]

Top ← Top +1
3. [Insert element]

S[TOP] ← x

4. [Finished ]

Return

When the array is full, i.e. when the stack contains as many elements as the array and if
an attempt is made to push yet another element onto the stack. The result of such an
attempt is called Overflow.

void push()

int item;

if (top == max - 1)

printf("\n Stack is full");

else

top++;

printf("\n Enter the item to be inserted: ");

scanf("%d", &item);

stk[top]=item;

printf("\n %d is inserted", item);

}
Algorithm for poping (deleting) an element from a stack.

Deletion is removing an existing element from the stack and is referred

as pop operation.

ALGORITHM POP (S, TOP) – This algorithm removes the top element from
the stack which is represented by a vector S and return this element. Top is a pointer to
the top element of the stack.

1. [Check for underflow on stack]

if Top = -1

then write (‘STACK UNDER FLOW’)

Exit

2. [Assign top element of stack]

item = S[Top])

3. [Decrement pointer]

Top ← Top - 1

If an attempt is made to pop an item from an empty stack, such an attempt is

called Underflow

void pop()

int item;

if (top == -1)
 printf("\n Stack underflow");

else

item = stk[top];

top--;

printf("\n %d is poped", item);

6) Display operation:

Display the contents of the stack from the top till the bottom of the stack.

ALGORITHM FOR DISPLAY( )

1. [Check if stack is empty]

if Top = -1

then write (‘STACK EMPTY”)

Exit

2. [Output the top element of stack]

While (Top ! = -1)

Output S[Top])

3. [Decrement pointer]

Top ← Top - 1

End of while.
7) Accessing the top element:

It is to print the top most element.

void stacktop( )

if(top = = -1)

printf(“\n stack underflow”);

else

printf(“%d”, st[top]);

8) Identifying current position of top of stack:

void top( )

printf(“Top position = %d”, top);

}
Applications of Stacks

The different applications of stacks are,

1. Conversion of expressions

2. Evaluation of expressions

3. Reversal of string

4. Recursion

Arithmetic Expression: It is combination of operands and operators placed in its proper

place. An arithmetic expression can be represented in three ways.

1. Infix

2. Prefix (Reverse polish notation)

3. Postfix (Suffix polish notation/polish notation)

(The name polish notation is named after polish logician Jan Lukasiewicz )

Consider the sum of A and B.

The arithmetic expression is written as A+B where A and B are operands, + is the
operator.

1. This particular representation, if the operator is between A and B (operands)

is infix notation.
2. If the operator precedes the two operands, then the notation is prefix
notation i.e. +AB
3. If the operator follows the two operands then the notation is post fix notation.
i.e. AB+

Conversion of infix expression to postfix expression:

Two important things is to be consider before conversion.

1. Hierarchy of the operators (Precedence)

Hierarchy of the operators are as follows,

 Hierarchy

Parenthesis 1

Exponentiation 2

*, / 3

+, - 4

Algorithm to convert infix to post fix expression:

Q is the input infix expression and P is the output Postfix expression.

1. Push ‘(‘onto stack.

2. Scan Q from left to right and repeat steps 3 to 6 for each element of Q until
the stack is empty.
3. If an operand is encountered add it to P (Postfix Expression).
4. If a left parenthesis is encountered then push it to the stack.
5. If an operator is encountered then,

i. Repeatedly pop from stack and add to the postfix expression P each
operator on top of the stack which has the same or higher precedence than the operator
scanned from the infix expression.

ii. Add the operator to the stack.

6. If a right parenthesis is encountered then,

i. Repeatedly pop from the stack and add to P each operator on top of
the stack until a left parenthesis is encountered.

ii. Remove the left parenthesis

7. Exit.
Evaluation of postfix expression

Algorithm:

1. Scan the postfix expression from left to right.

2. If we encounter an operand, push it on to stack.

3. If we encounter an operator, pop two operands from the stack. The first operand
popped is an operand 2 and second popped is operand 1.

4. Perform the desired operation on the operands. i.e. operand 1 operator operand 2

5. Push the result on to the stack.

6. Repeat the above procedure till the end of input is encountered.

Trace of algorithm to evaluate the postfix expression 6 3 2 – 5 * + 1 ^ 7 +

Symbol Operand2 N2 Operand1 N1 Result (N1 Stack

operator N2)
6 6
3 6,3
2 632
- 2 3 1 61
5 2 3 1 615
* 5 1 5 65
+ 5 6 11 11
1 5 6 11 11 1
^ 1 11 11 11
7 1 11 11 11 7
+ 7 11 18 18
String Reversal and Recursion

String Reversal

Each character of the string is pushed on to the stack. Since stack works on Last in first
out principle, when the whole string is pushed on to the stack, popping of the characters
from that stack is done so as to obtain the reverse string.

Solution Steps

 Create a recursive function recur to reverse the stack containing string

 Pop the top element in each stack of recursion and hold the element in
function call Stack until we reach the end of the stack
 While moving back in the recursion tree, push the held element of each
recursion call stack at the bottom of the stack.

Recursion

Recursion is a process of calling the function repeatedly in terms of itself until a

specified condition is reached so that it reduces the complexity of the program.

a) Factorial of a Number

The product of the positive integers from 1 to n, is called “n factorial” and is

usually denoted by n!.

n! = 1 * 2 * 3 * . . . . (n-2) * (n-1) * n

E.g. 5! = 1* 2 * 3 * 4 * 5=120
Introduction to Queue

Definition

Queue is an ordered collection of items. These items may be deleted at one end (called
the FRONT / HEAD of the queue) and inserted at other end (called the REAR / TAIL of the
queue). Also known as FIFO – First In First Out.

A Queue is a linear structure which follows a particular order in which the operations are
performed. The order is First In First Out (FIFO). A good example of a queue is any queue
of consumers for a resource where the consumer that came first is served first. The
difference between stacks and queues is in removing. In a stack we remove the item the
most recently added; in a queue, we remove the item the least recently added.

The following diagram given below tries to explain queue representation as data
structure
−

As in stacks, a queue can also be implemented using Arrays, Linked-lists,

Basic Operations
Queue operations may involve initializing or defining the queue, utilizing it, and then
completely erasing it from the memory. Here we shall try to understand the basic
operations associated with queues −

 enqueue() − add (store) an item to the queue.

 dequeue() − remove (access) an item from the queue.

Few more functions are required to make the above-mentioned queue operation
efficient. These are −

 peek() − Gets the element at the front of the queue without removing it.
 isfull() − Checks if the queue is full.
 isempty() − Checks if the queue is empty.

In queue, we always dequeue (or access) data, pointed by front pointer and while
enqueing (or storing) data in the queue we take help of rear pointer.
Operations in a Queue
a. Inserting an element into queue

b. Deleting an element from queue

c. Checking the status whether queue is empty

d. Checking the status whether queue is full

e. Displaying the elements of queue

The first element inserted into a queue is the first element to be removed. For this
reason queue is referred as first-in-first-out (FIFO) list.

a) Insertion:

Points to remember when we add an element in the queue:

 Check whether the queue has any space to add an element into it.
 If the queue has spaces then add the element into the queue by incrementing the
REAR pointer.

Example:

· Increment the REAR as REAR+1 or REAR++

· Queue [Rear] = Item which is used to add an element into the queue.

Note: Rear is the position where the item is to be inserted.

Now add element 8 to the queue

Before insertion

Front rear

0 1 2

23
Queue 34 ....

Front=0, Rear =1
To insert 1) increment rear --à Rear+1= 2

2) queue[2]=8

After insertion

Front rear

0 1 2

23
A 34 8 ....

Front=0, Rear =2

void qinsert()

int item;

if(rear==max-1)

printf("queue is full");

else

scanf("%d",&item);

rear++;

queue[rear]=item;

getch();

}
Queue Overflow:

Insertion of an element in a queue is possible only if there is room in the array to

fit in elements. If the maximum size of the array is reached and if an attempt to insert an
element into the queue that is full, is tried, the condition that occurs is called ‘queue
overflow’.

Deleting an element from the queue:

Points to remember when we remove an element from the queue:

· Check whether the queue has any element to be deleted.

· If so, delete the element from the queue by incrementing the FRONT pointer.

Example:

· Item= queue[rear]

· Increment the front using front++

Note: Rear is the position where the item is to be inserted.

Before deletion

Front rear

0 1 2

23
A 34 8 ....

Front=0, Rear =2

To insert 1) item = queue[2]à item = 8

2) fornt++ à front=1

After deletion

Front rear

0 1 2

23
A 34 8 ....
Front=1, Rear =2

Note: Front is the position where the item is to be deleted

void qdelete()

int item;

if(front==rear+1)

printf("deleted item is %d",queue[front]);

front++;

getch();

Queue Underflow:

Deletion or removal of an element from the queue can be done only if at least
one item is there in the queue. It means that the queue must be non-empty. An
attempt to remove an element from an empty queue is called ‘queue underflow’.

Queue empty operation:

A function to check whether queue is empty or not return 1 when the queue is
empty and returns 0 when the queue is ot empty. This function is used to check for
queue underflow.

int qempty()

if(front == rear+1)

return 1;

else

return 0;
}

Queue Full operation:

A function to check whether queue is full or not returns 1 when the queue is full
and returns 0 when the queue is not full. This function is used to check for queue
overflow.

A queue is full when REAR reaches the maximum size of the array used for the
queue i.e.e REAR=max-1. FRONT = 0 and REAR = n-1 indicates this condition.

int qfull( )

if(rear = = max-1)

return 1;

else

return 0;

Queue display operation:

This operation is used to display all the elements present in a queue. Whenever
REAR value becomes equal to the FRONT-1 i.e.REAR = -1 and FRONT = 0 then the queue
is empty.

void qdisplay()

int item;

int p=front;

if(p==rear+1)

printf("queue is empty");

else
{

printf("\n queue elements");

while(p<=rear)

printf("%d\t",queue[p]);

p++;

getch();

}
Types of Queue - Circular Queue

Linear queue have a drawback that once a queue is full, i.e. it has reached the maximum
size of the array, even through elements may be deleted from the front/ head , and
certain locations are free, we cannot add any more elements as rear/tail would have
already reached the last position in the queue. So insertion is not possible and it will
indicate the queue overflow condition.

Problem solution

 Create a circular queue.

 Circular queue wraps around to the beginning whenever the Head(Front) or the
Tail(Rear) reaches the end of the queue.

Circular Queue – The method of arranging the queue elements Q[1], Q[2], …….. Q[n] in a
circular fashion with Q[1] following Q[n] is called circular Queue
 In a circular queue, every time we add an element to the queue, the REAR value
increments by 1 till the time it reaches the upper limit of queue; after which it starts all
over again from 1. Similarly, every time we delete an element from queue, FRONT
increments by 1 till the time it reaches the upper limit of queue, after which it starts all
over again from 1.

Insertion of element into circular queue:

Figure shows an empty circular queue with maximum size of 7 elements.

Initially Front=1;Rear=0;

1) To insert element into the circular queue, increment REAR

Rear = (Rear+1)%n where n is size of circular queue ie 7

Once REAR reaches maximum size, it should start all over again from 0 which can be
achieved by ‘%’ operator.

2) Queue[Rear]=item use this statement to insert value.

It is important to check for queue overflow condition before inserting an

element.

Deletion of element from circular queue:

To delete an element from the queue, front is to be incremented by 1,

1) item = queue [front]

2) front=front+1

3) then print item value

Types of Queue - Priority Queue and Double ended
Queue
Priority Queues

A Queue in which it is able to insert elements or remove elements from any position on
some property (such as priority of the task to be processed) is referred as priority Queue.

 An element of higher priority is processed before any element of lower priority.

 Two elements with the same priority are processed according to the order in
which they were added to the queue.

In priorty queue, every element has been assigned with a priority value called priority.
The elements can be inserted or deleted randomly any where in the queue.

Priority queue is a data structure in which prioritized insertion and deletion operations
on elements can be performed according to their priority values.

Double Ended Queue

A deque, also known as a double-ended queue, is an ordered collection of items similar

to the queue. It has two ends, a front and a rear, and the items remain positioned in the
collection. What makes a deque different is the unrestrictive nature of adding and
removing items. New items can be added at either the front or the rear. Likewise,
existing items can be removed from either end. In a sense, this hybrid linear structure
provides all the capabilities of stacks and queues in a single data structure.
The deque abstract data type is defined by the following structure and operations. A
deque is structured, as described above, as an ordered collection of items where items
are added and removed from either end, either front or rear. The deque operations are
given below.

 Deque() creates a new deque that is empty. It needs no parameters and returns an
empty deque.
 add_front(item) adds a new item to the front of the deque. It needs the item and
returns nothing.
 add_rear(item) adds a new item to the rear of the deque. It needs the item and
returns nothing.
 remove_front() removes the front item from the deque. It needs no parameters
and returns the item. The deque is modified.
 remove_rear() removes the rear item from the deque. It needs no parameters and
returns the item. The deque is modified.
 is_empty() tests to see whether the deque is empty. It needs no parameters and
returns a boolean value.
 size() returns the number of items in the deque. It needs no parameters and
returns an integer.
Applications of Queue
A queue is a data structure that follows First In First Out — which means the first item to
enter the queue is the first to leave the queue.

In computer science this pattern is useful when processes need to be executed in the
order that they are created. It is also used to send messages to a receiver in the order
that they were generated.

Queues are useful in the scenario where there is only a single resource, but multiple
objects that want to use or access this resource. So a queue can be thought of like a
waiting list, for a resource. This resource can be a processor, or maybe a service that
executes a function, or it could even be a receiver for a message. Introducing this
concept of a waiting list for a resource helps us create asynchronous systems, increasing
processing speed and also ensures the resource is utilized efficiently.

Here are some of the common places where queues are used:

 Message Queues – A message queue is a general concept used for

communication between processes. Basically a sender sends a message, and if the
receiver cannot receive it immediately maybe because it is busy with something
or offline, the message instead of dropping off, waits in some kind of a queue,
and when the receiver is ready to receive it, the message is consumed or removed
from the queue and sent to the receiver.
For example, when you send an email, it waits in a queue called the SMTP queue,
until the receiver logs into their inbox. Same concept is applied when you send a
message to someone who is not online on a social network. Your message waits
in some kind of a queue on a server, and when the recipient comes online, it is
sent to them.
 Process Scheduling – All the processes running on your computer now, first wait
in a queue called ready queue, waiting to be executed by your processor. There
are various scheduling algorithms that decide which process should be executed
next based on certain criteria like priority.
 Data Buffers – A buffer implements a queue and is typically used in
communication when there is difference between the rate at which data is
received and the rate at which it can be processed.
For example in video streaming applications, the video is streamed in bursts and
stored in a buffer so that even if the network becomes slow for a while, the
playback is not interrupted. Say for example the video is playing at 24fps, then
the streaming app may store 240 frames in its buffer, so that it can continue
playing for the next 10 seconds even if the network is interrupted. The buffer is
also used for sequencing frames, i.e, if frames come out of order, they are sorted
in the buffer before being played. Buffers also used in disk drives, input/output
devices and communication over networks.
  It is also used in several algorithms like the Breadth First Search or BFS algorithm,
and round robin algorithm.

Examples and discussion on Expression conversion using

stack
Example

Convert ((A+(B-C)*D)^E+F) to postfix

1st Hierarchy parenthesis (inner most) which is (B-C) its postfix is BC-

((A+[BC-]*D)^E+F)

next Hierarchy is * within the parenthesis

((A+[BC-D*]) ^ E + F)

next Hierarchy + within the parenthesis

(( ABC-D*+) ^ E + F)

Now exponentiation is given preference over +

( ABC – D * + E ^) +F

So the final postfix expression is

ABC – D * + E^F+
Trace of the algorithm to convert the infix expression (A*(B-C)) to postfix
expression

Sl.no Symbol (Q) Postfix (P) Stack

1 ( (
2 A A (
3 * A (*
4 ( A (*(
5 B AB (*(
6 - AB (*(-
7 C ABC (*(-
8 ) ABC- (*
9 ) ABC-*
 UNIT-4

LINKED LIST

INTRODUCTION & COMPONENTS

INTRODUCTION

The term list refers to a linear collection of the data item. The size of the list is not
fixed. It is dynamic in nature i.e., varying in size.

In stack and queues, the allocation of items is done by means of sequential allocation
technique using arrays whereas as in linked list it is dynamic memory allocation
technique.

COMPONENTS

A singly linked list or one-way list is a linear collection of data elements

called nodes, where each node is divided into two parts:

1. Information Field, holds the actual value to be stored and accessed in a list.
Information part may consist of one or more than one field. In other words, a linked list
consists of a series of structures which are not necessarily contiguous in memory.

2. Pointer to the next node / link filed, contains the address of the next node. So
the link field in the first node refers to the second node and the link field in the second
node refers to the third node and so on. It establishes a link to the next data item / node
in the linked list from the current node. It is called link field. The last node of the list
contains NULL (‘\0’) in the link field indicating that it is the end of the list.

Node
Information Link or Pointer to the next node.

Example: The following figure illustrates a linked list structure with 4 nodes. Each node
containing one information field and one pointer field. A linked list also contains
an external pointer variable called start, which contains the address of the first node in
the list. There is an arrow drawn from the start to the first node in the linked list. If there
is no node in the list, the list is called NULL list or EMPTY list.
The two pointers called Null pointer and External pointer and one special case of
linked list called Empty List.

Null pointer, the link field / pointer filed of the last node contains zero rather than valid
address. There is nothing but a Null pointer and it indicates the end of the list.

External Pointer, is a pointer to the very first node in the linked list. It enables to access
the entire list.

Empty List, if the nodes are not present in a linked list, then it is named as empty list or
empty linked list or NULL list.

The value of an external pointer for an empty list = zero. So a linked list can be made
an empty list by assigning a NULL value to the external pointer start i.e., start = NULL.
Representation of linked list
There are two ways to represent a linked list in memory:

1. Static Representation using array

2. Dynamic representation using free pool of storage.

Static Representation using Array

It maintains two arrays: Information and link or pointers as INFO [ ] and LINK [ ]. These
two arrays should be of equal size and parallel to each other. The memory size of these
two arrays should be sufficient to store the entire linked list.

INFO [1] = ALINK [1] = 3

INFO [3] = BLINK [3] = 6

INFO [6] = CLINK [6] = NULL

A, B, C represent the information i.e the actual data and 1, 2, 3, …. 6 represent the
addresses of the nodes that points to the next nodes.

Dynamic representation using free pool of storage

The process of allocating memory at run time is known as dynamic memory

allocation. The function malloc ( ) and calloc ( ) are used to allocate memory
and free() is used to deallocate the memory.

In the dynamic representation of linked list, a node is created dynamically whenever it is

required. Any number of nodes can be created depending upon the requirement. There
is no need to setup any actual storage space at this stage as space will be allocated for
each node as needed when the program is running.

In order to create a linked list a structure is to declared that defines all the list entries.
The following structure is capable of holding the data plus the address of the memory
space holding the next structure in the list.

The link is the pointer that points to the next node of the same structure type.

The link member field contained in the structure node, which is used to point to the
same structure type is called self – referential structure. A node may contain any
number of information fields.

Advantages – Linked list:

1. Efficient Memory Utilization, the memory of a linked list is not preallocated.

Memory can be allocated whenever required. It is deallocated (removed) when it is no
longer needed.

2. Insertion and deletion operation are easier and efficient: Linked lists provide
flexibility in inserting a data item at a specified position and deletion of a data item from
the given position.

3. As dynamic data structures, can grow or shrink during the execution of the
program.

4. Extensive Manipulation, perform any number of complex manipulations without

any prior idea of memory space available.

5. Arbitrary Memory Locations, in the linked lists, memory locations need not be
consecutive. It may be arbitrary values. Even then the accessing of these items is easier
as each data item contained within itself will address to the next data item. The
elements in the linked list are ordered not by the physical placement in memory in
memory but by the logical links stored as part of the data with the node itself.

Linked list is effective way of sorting the data in memory where each element in the list
contain a field, called a link or pointer, which contains the address of the next element
in the list.
Disadvantages – Linked list:

1. Array implementation of stacks and queues, allocates a fixed memory size for that
particular stack or queue. If more memory is allocated and if using a very small memory,
the remaining is unnecessarily wasted. If the memory allocated is very small and need
more memory than available, then cannot allocate the extra memory during the
execution of the program.

2. Insertion and deletion makes so many complications in the array implementation

because of the data movement from one position to other. Example: if the array is of
larger size, insertion operation on the array has to first slide of all the elements one
stroke right side and deletion operation on the array has to slide all the elements one
stroke left side.
Types of Linked List
Depending on the requirements, the linked lists are classified basically into four types:

1. Singly Linked list

2. Doubly Linked list

3. Circular Linked list

4. Circular Doubly Linked list.

1. Singly Linked list

It is a linear collection of data elements called nodes, where each node is divided into
two parts: INFO and LINK field. The link field of each node will point to the next node
and the link field of last node always point to NULL.

2. Doubly Linked list

In a single linked list one can move starting from the start to any node in one direction
only (from left to right). A singly linked list is also termed as a one-way list.

Sometimes it is required to transverse the list in either forward direction or backward

direction. This increase the performance and efficiency of algorithms. So a two-way list
called doubly linked list.

Forward direction means traversing from left to right and backward direction means
traversing from right to left.
In doubly linked list, two link fields called BACK and FORW. Defining the doubly linked
list as collection of nodes, where each node is divided into three fields.

 Pointer to previous / BACK field

 Information field
 Pointer to next node / FORW field

BACK, is a pointer which points to the previous node in the list or BACK contain the
address of the previous node.

FORW, is a pointer which points to the next node in the list or FORW contains the
address of the next node in the list.

INFO, field contains the data or information.

In doubly linked list, the BACK field of the first node always contains NULL indication
that it is the first node in the linked list. The FORW field of the last node also contains
NULL indicating that it is the last node in the linked lists.

Advantages of doubly linked list:

 It can be traversed in forward or backward direction

 If any particular node address is known, one can have both successor node
address and predecessor node address that makes inserting and deleting much
easier.
 It is used to represent the trees effectively.
 It simplifies the list management.

Disadvantages of doubly linked list:

 Extra memory is required to store the back pointer

3. Circular Linked list
In singly linked list, link part of the last node has NULL value, it represents the last node
of linked list, but in circular linked list, link part of the last node points to the first node of
the linked list and represents the linked list in circular way. Some operations like deletion,
merging can be implemented very easily with circular linked lists.

Accessing any node of the linked list without going back and start traversal again from
the first node because it’s direction is just like a circle and can traverse from last node to
first node.

In circular linked list, there is no first and the last nodes, maintain the pointer at the last
node as ‘last’. It will be very useful for stack and queue implementation because, a ‘top’
in stack and ‘rear’ in a queue. The pointer ‘last’ is pointing to the last node, say that the
node that follow last, will be the first node, i.e., last à LINK always have the address of
first node.

Advantages – Circular linked list: Used frequently instead of single linked list because
many operations can be easily be performed in circular list.

 It can be traversed to any node from any node.

 All the node link address will have valid address, instead of NULL pointer
 A node can be inserted at or deleted from any position of the linked list
 One can start at any node in the list and traverse the whole list.

4. Circular Doubly Linked list

It is a more complexed type of data structure in which a node contains pointers to its
previous node as well as the next node. It does not contain NULL in any of the node. The
last node of the list contains the address of the first node of the list. The first node of the
list also contains address of the last node in its previous pointer.
Advantages - Circular Doubly Linked list:

 Any node can be accessible from any given node

 It can be traversed in forward and backward direction
 Used to represent trees
 It simplifies list management effectively

Disadvantages - Circular Doubly Linked list:

 Extra memory is required to store BACK pointer

Linked List - Creation
In this algorithm a Linked List of nodes is created. The list is pointed by pointer first, the
last node of the list points to NULL., indicating the end of the list.

Each node is having two parts DATA and NEXT. Let us assume that a linked list of N
number of nodes is to be created. The operator new will be used for the dynamic
allocation of node. A variable I is being used as a counter to count the number of nodes
in the created list.

Algorithm

1.first=new node; //create the 1st node of the list pointed by first

2.Read(Data(first));

3.NEXT(First)=NULL;

4.Far a First; //point Far to the First

5. For I=1 to N-1 repeat steps 6 to 10

6.X=new node;

7.Read(Data(X))

8.NEXT(X)=NULL;

9.NEXT(Far)=X; //connect the nodes

10.Far=X; //shift the pointer to the last node of the list

// end of For Loop

11.END
Creation of Linked List - Code

void create( ){

char choice='y';

clrscr();

start=null;

q=null;

while(choice=='y')

p=((struct node*)malloc(sizeof(struct node)));

printf("\nEnter the rollno & name :");

scanf("%d %s",&p->rollno,p->name);

p->link=null;

if(start==null) {

start=p;

q=p;

} else

q->link=p;

q=p;

printf("\nDo you want to create another node y/n :");

choice=getch();

}
Linked List - Insertion

Insertion: At the beginning

Algorithm

1.X=new node;

2.Read(DATA(X);

3. NEXT(X)=First;

First=X;

4.END

Program

void ins_beg()

p=((struct node*)malloc(sizeof(struct node)));

printf("\nEnter register number:");

scanf("%d",&p->rollno);

printf("\nEnter name of student:");

scanf("%s",&p->name);

p->link=start;

start=p;

}
Insertion: At the End

Algorithm

1. X=new node

2. READ(DATA(X))

3. ptr = List

4. While(NEXT(ptr) <> NULL) repeat step 3

5. ptr = NEXT(ptr)

6. NEXT(ptr) = X

7. Next(X) = NULL

8. END

Program

void ins_end()

p=(struct node *)malloc(sizeof(struct node));

printf("\nEnter register number:");

scanf("%d",&p->rollno);

printf("\nEnter name of student:");

scanf("%s",&p->name);

p->link=null;

if(start==null)

start=p;

else
 {

q=start;

while(q->link!=null)

q=q->link;

q->link=p;

Insertion: At A Position

Algorithm

1. Pos = position to insert

2. Read(pos)

3. Q = list

4. Listpos = 1

5. While(Listpos < pos -1) repeat step 6

6. Q = Next(Q)

7. X = new node

8. Read(Data(X))

9. Next(X) = Next(Q)

10. Next(Q) = X

11. End
Program

void ins_pos()

int i,pos;

printf("\nEnter the position at which you want to insert the new node:");

scanf("%d",&pos);

if(pos==1)

ins_beg();

else {

q=start;

for(i=1;i<pos-1;i++)

q=q->link;

p=(struct node *)malloc(sizeof(struct node));

printf("\nEnter register number:");

scanf("%d",&p->rollno);

printf("\nEnter name of student:");

scanf("%s",&p->name);

p->link=q->link;

q->link=p;

}
Linked List - Deletion, Display, Searching
Deletion

Algorithm

1. If (DATA(list)=’VAL’)then

Ptr=LIST;

LIST=NEXT(list);

Delete ptr;

Stop;

Back=list;

Ptr=list;

2. while(ptr<>NULL) repeat step 3 to 5

3. If(DATA(ptr)=’VAL’) then

NEXT(back)=NEXT(ptr);

Delete ptr;

Exit; }

4. back=ptr;

5. ptr=next(ptr);

[end of while loop]

6. END
Program

void del_item(int regno)

p=start;

prev=null;

if(start==null)

printf("\nLinked list is empty\n");

return;

if(start->rollno==regno)

start =start->link;

free(p);

return;

while((p->rollno!=regno)&&(p!=null))

prev=p;

p=p->link;

if(p==null)

printf("\nRegister number %d is not found in the linked list\n",regno);

else
 {

prev->link=p->link;

free(p);

Display
In this algorithm a linked list, pointed by first, is traversed. The number of nodes in the
list is also counted during the traverse. A pointer ptr is being used to visit the various
nodes in the list. A variable count is used to keep track of the number of nodes visited
during the traverse. The traverse stops when a NULL is encountered.

Algorithm

1. If First=NULL then {print “List empty” STOP}

2. count=0;

3. ptr=First; {point ptr to the 1st node}

4. While ptr<> NULL repeat Steps 5 to 6

5. Print(Data(ptr))

6. ptr=NEXT(ptr) [shift ptr to the next node]

7. END
Program

void display()

printf("\n\n The nodes in the list are\n\nSTART->");

p=start;

while(p!=null)

printf("%d %s ->",p->rollno,p->name);

p=p->link;

printf("NULL\n");

return;

Searching
In this algorithm a linked list, pointed by first, is traversed. While traversing the data part
of each visited node is compared with an item ‘x’. If the item is found then the search
stops otherwise the process continues till the end of the list(i.e NULL) is encountered. A
pointer ptr is being used to visit the various nodes in the list.

Algorithm

1. If first=NULL then{

Print “List empty”; STOP; }

2. ptr=First; [point ptr to the 1st node]

3. while (ptr<>NULL) repeat steps 4 to 5

4. If (DATA (ptr)= ‘X’)

Then {print “item found”;

STOP

5. ptr=NEXT (ptr); [shift ptr to the next node]

[end of while]

6. Print “item not found”;

7. END

Program

void search(int regno)

int i=0;

p=start;

while(p!=null)

if(regno==p->rollno)

i++;

printf("\nRoll no %d is found at %d",p->rollno,i);

printf("\n Name:%s",p->name);

return;

}
 else

p=p->link;

i++;

printf("\nNode with register number %d does not exist",regno);

}
 UNIT 5

TREE
Tree-Definition

Tree is a data structure used to represent hierarchical relationship existing among several
data items. Here, each data item is referred to as node. Each node may be empty or may
be connected to some other nodes.

Tree-Terminologies
Referring to the above diagram, let us define some of the terminologies used in trees. In
the diagram,

· A, B, C etc. are known as nodes of a tree.

· A is known as the root.

· B, C and D are called as children of A. Similarly, J and K are children of H and so on.

· A is referred as father of B, C and D.

· B, C and D are known as siblings of each other.

· The node, which is not a having any children is called

as leaf or terminal or external node.
· A tree structure, which is connected to root is known as a subtree.

· The number of subtrees connected to a node is known as a degree of that node. In

the figure, A is having degree 3, B is of degree 2, C is of degree 1 etc.

· The maximum number representing the degree of any node in a tree is called
as degree of a tree. Here, degree of tree is 3.

· The entire tree structure is leveled such that the root is at level 0 and any other
node is having the level one more than the level of its father.

· The depth or height of a tree is the maximum level of that tree.

Collection of disjoint trees is known as the forest.

Binary Tree, Complete Binary Tree
Binary Tree-Definition

Binary tree is a finite set of data items, which is either empty or partitioned into three
disjoint subsets. The first subset contains only one item known as root. The other two
subsets are themselves binary trees known as left subtree and right subtree

In the above figure, A is the root of a binary tree. A tree structure having B as a root is
known as left subtree of the tree with root A. Similarly, the tree structure having C as
root is the right subtree of the given tree.
Complete Binary Tree-Definition
There are certain variations in binary trees as listed below:

· A binary tree in which any node is either empty or consisting of both left subtree
and right subtree is known as strictly binary tree.

· A strictly binary tree is which the number of nodes at any level i is 2i then the tree is
said to be complete (or full) binary tree.

Level, i=0 Number of nodes=2i =1

Level, i=1 Number of nodes=2i =2

Level, i=2 Number of nodes=2i=4

· A strictly binary tree is which is not full only at the last level, that too at the right side
is called as almost complete binary tree.
Level, i=0 Number of nodes=2i =1

Level, i=1 Number of nodes=2i =2

Level, i=2 is not full

Binary Search Tree, Heap
Binary Search Tree-Definition

Binary search tree is a binary tree in which for each node, the elements in left subtree are
less than it and the elements in right subtree are greater than or equal to it. Every node
of binary search tree must satisfy this condition.

To insert a new node into BST, it is compared with root. If it is less than the root, traverse
towards left subtree. If it is greater than or equal to root, traverse towards right subtree
and insertion is made appropriately. Care to be taken such that after insertion also,
the tree remains BST. Similary, for deletion of a node also, such precaution is to be taken.

Note that in-order traversal of a BST will give the sorted list in ascending order.
So, binary tree sort is nothing but a creation of BST and then its in-order traversal.
Heap-Definition

• A heap is a specialized tree-based data structure with a key element in each node.

• It is a complete binary tree.

• There are two types of heaps:

(1) Max-Heap: In a Max-Heap the key present at the root node must be greatest among
the keys present at all of it’s children. The same property must be recursively true for all
sub-trees in that Binary Tree.

(2) Min-Heap: In a Min-Heap the key present at the root node must be minimum among
the keys present at all of its children. The same property must be recursively true for all
sub-trees in that Binary Tree.
Binary Tree
The simplest form of tree is a binary tree. A binary tree consists of a node (called the root
node) and left and right sub-trees.
Both the sub-trees are themselves binary trees.

Binary tree is a set of finite nodes which is either empty or consists of one or more nodes
in which each node has at most two disjoint binary sub trees called left sub tree or right
sub tree respectively. Thus we can say that there may be a zero degree node or a one
degree node or a two degree node.

Figure shows a typical binary tree.

In figure- A is the root node, B and C are the left sub tree and right sub tree of root node
A respectively. This binary tree is not a strictly binary tree. A binary tree is strictly
binary tree if every non-terminal node has two sub trees or you can say if every non-
terminal node consists of non-empty left sub tree as well as non-empty right sub tree.
 Figure-(b) shows a strictly binary tree.

The binary trees that we have discussed so far are not complete binary trees.

Complete binary tree is a strict binary tree with all leaf nodes at the same level. The
number of nodes at level ‘n’ is 2 n

Left Skewed Tree:

A binary tree with only left sub tree is called left skewed tree.

Right Skewed Tree:

A binary tree with only right sub tree is called right skewed tree.
Implementation of Binary Trees

Binary trees are implemented in two ways:

1. Array implementation of Binary Trees

2 . Linked List implementation of Binary Trees

Array implementation of Binary Trees

In an array implementation of binary trees we use one-dimensional array. The nodes

stored in an array are accessible sequentially. Consider the complete binary tree. The
nodes are numbered beginning with the root and then moving from left to right at each
level. The root node is numbered 0, then the left child as 1 and right child as 2 and so on.

Now if we place node number at index 0 then in successive positions the left child and
right child are stored.

Figure-(d) representation of this binary tree.

This table concludes that if father is at index ‘n’ then its left children will be at index 2n+1
and its right children will be at index 2n+2.Consider finding out the left and right child
position of node C. Since the node C is placed at index 2, therefore its left child would be
at index 5 (2*2+1) and its right child would be at index 6 (2*2+2).

The situation is pleasant so far because it is complete binary tree. But if the binary tree is
not complete then it definitely results in unnecessary wastage of memory space because
array is static in nature. For example let use have a binary tree as shown in figure-(e).
 Figure (e)

Array representation of the above binary tree is as shown in figure- (f)

From this table it is clear that if a tree is far from its complete behaviour then the array
implementation would waste a lot of memory space. This type of problem is overcome
by implementing the binary tree in linked list.

Linked List implementation of Binary Trees

In this linked list is used in which elements are treated as nodes. Each node of a
binary tree has three fields, as follows:

Ø Left link

Ø Data

Ø Right link

The data field contains the value of the node, the left link contains the address of the left
child and right link contains the address about the right child.

Figure-(h) shows the linked list representation of a binary tree shown in figure-(g)
From the figure (h) it is clear that the left link field and right link field of leaf nodes
contains a NULL value. However if a parent node has empty left child then its left link
field would be set to NULL and if it has empty right child then its right link field is set to
NULL.

Properties:

· The maximum number of nodes at a level I of binary tree is 2I where I>=0.

· If h = height of a binary tree,

max number of nodes possible in a binary tree of height h is 2h-1

min number of nodes possible in a binary tree of height h is h

· For any non empty tree, number of terminal or leaf nodes is equal to number of
non terminal nodes(internal nodes) +1.

· For any non empty binary tree, if ‘n’ is the number of nodes and ‘e’ is the number
of edges, then n=e+1;

A binary tree with height h and 2h + 1 - 1 nodes (or 2h leaves) is called a full binary tree
BINARY SEARCH TREES

A binary tree T is said to be a Binary Search Tree if each node N has the following
property:

Ø Value of N is greater than every value in the left sub tree of N and is less than every
value in the right sub tree of N.

Consider the elements 32 16 34 1 87 18

§ Since 32 is the First Number to be added, 32 becomes the root of the tree.

§ Next Number is 16 which is lesser than 32 Hence 16 becomes left node of 32.

§ Next consider 34. Since 34 > 32 , 34 becomes the right node of the ROOT.

§ Next 1 < 32 we jump to the left node of the ROOT. But since the left node
has already been taken we test 1 once again. Since 1 < 16, 1 becomes the left node of
16.
 § Since 87 > 32 we jump to the right node of the root. Once again this
space is occupied by 34. Now since 87 > 34, 87 becomes the right node of 34.

§ Since 18 < 32 we jump to left node of the root. There, 18 > 16 18 becomes the right
node of 16.The Binary Search tree is constructed as follows,

Traversals of a Binary Tree

There are three ways of traversing a Binary Tree. Displaying the tree
contents is known as transversal. The tree can be traversed in inorder, preorder and
postorder methods.

PREORDER TRAVERSAL:

§ Process the root R.

§ Traverse the left sub tree of R in preorder.

§ Traverse the right sub tree of R in preorder.

INORDER TRAVERSAL:

§ Traverse the left sub tree of R in inorder.

§ Process the root R.

§ Traverse the right sub tree of R in inorder.

POSTORDER TRAVERSAL :

§ Traverse the left sub tree of R in postorder.

§ Traverse the right sub tree of R in postorder.

§ Process the root R.

For Example , Consider the binary tree,

The order in which each node in the tree is traversed is as follows,

INORDER TRAVERSAL:10,15 ,16 ,32 ,33,34,87

PREORDER TRAVERSAL :32 ,16,10,15,34,33,87

POSTORDER TRAVERSAL :15, 10, 16, 33, 87, 34, 32

More about Tree Traversals
Construct Tree from given Inorder and Preorder traversals

Inorder traversal − In this type of tree traversal, a left subtree is visited first, followed by
the node and right subtree in the end.

Inorder (tree root)

 Traverse left subtree of node pointed by root, call inorder ( root→left )

 Visit the root
 Traverse right subtree of node pointed by root, call inorder ( root→right )

Preorder traversal − In this type of tree traversal, the node visited first, followed by the
left subtree and right subtree in the end.

Preorder (tree root)

 Visit the root

 Traverse left subtree of node pointed by root, call inorder ( root→left )
 Traverse right subtree of node pointed by root, call inorder ( root→right )

The inorder and preorder traversal of below tree are given −

Inorder
2-3-4-5-6-8-10

Preorder
4-3-2-5-8-6-10
Now we’ll construct the above tree again for given preorder and inorder traversals.

Inorder
2-3-4-5-6-8-10
Preorder
5-3-2-4-8-6-10
 As we know that preorder visits the root node first then the first value always
represents the root of the tree. From above sequence 5 is the root of the tree.

Preorder
5 -3-2-4-8-6-10
 From above inorder traversal, we know that a node’s left subtree is traversed
before it followed by its right subtree. Therefore, all values to the left of 5 in
inorder belong to its left subtree and all values to the right belong to its right
subtree.

Inorder
2-3-4 ← 5 → 6-8-10

 Now for the left subtree do the same as above.

Preorder traversal of left subtree is 3 -2-4. So 3 becomes the root.

Inorder traversal divided further into 2 ← 3 → 4

 Now for the right subtree do the same as above.

Preorder traversal of the right subtree is 8 -6-10. So 8 becomes the root.

Inorder traversal divided further into 6 ← 8 → 10

So, in this way we constructed the original tree from given preorder and inorder
traversals.
Concept of Heap
In this lecture , Students will learn about the concept of Heap and its creation

Creation of Heap

A Heap is a special Tree-based data structure in which the tree is a complete binary tree.
Generally, Heaps can be of two types:

1. Max-Heap: In a Max-Heap the key present at the root node must be greatest
among the keys present at all of it’s children. The same property must be
recursively true for all sub-trees in that Binary Tree.
2. Min-Heap: In a Min-Heap the key present at the root node must be minimum
among the keys present at all of it’s children. The same property must be
recursively true for all sub-trees in that Binary Tree.

Given an array of N elements. The task is to build a Binary Heap from the given array.
The heap can be either Max Heap or Min Heap.
Example:

Input: arr[] = {4, 10, 3, 5, 1}

Output: Corresponding Max-Heap:
10
/ \
5 3
/ \
4 1

Input: arr[] = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}

Output: Corresponding Max-Heap:
17
/ \
15 13
/ \ / \
9 6 5 10
/ \ / \
4 8 3 1
What is a Heap ?
Heap is a special tree-based data structure, that satisfies the following special heap
properties:

1. Shape Property: Heap data structure is always a Complete Binary Tree, which
means all levels of the tree are fully filled.

2. Heap Property: All nodes are either greater than or equal to or less than or
equal to each of its children. If the parent nodes are greater than their child
nodes, heap is called a Max-Heap, and if the parent nodes are smaller than their
child nodes, heap is called Min-Heap.
How Heap Sort Works?
Heap sort algorithm is divided into two basic parts:

 Creating a Heap of the unsorted list/array.

 Then a sorted array is created by repeatedly removing the largest/smallest
element from the heap, and inserting it into the array. The heap is reconstructed
after each removal.

Initially on receiving an unsorted list, the first step in heap sort is to create a Heap data
structure(Max-Heap or Min-Heap). Once heap is built, the first element of the Heap is
either largest or smallest(depending upon Max-Heap or Min-Heap), so we put the first
element of the heap in our array. Then we again make heap using the remaining
elements, to again pick the first element of the heap and put it into the array. We keep
on doing the same repeatedly untill we have the complete sorted list in our array.

Heap Sort
Heap sort processes the elements by creating the min heap or max heap using the
elements of the given array. Min heap or max heap represents the ordering of the array
in which root element represents the minimum or maximum element of the array. At
each step, the root element of the heap gets deleted and stored into the sorted array
and the heap will again be heapified.

The heap sort basically recursively performs two main operations.

 Build a heap H, using the elements of ARR.

 Repeatedly delete the root element of the heap formed in phase 1.

 Step 1: [Build Heap H]

Repeat for i=0 to N-1
CALL INSERT_HEAP(ARR, N, ARR[i])
[END OF LOOP]
 Step 2: Repeatedly Delete the root element
Repeat while N > 0
CALL Delete_Heap(ARR,N,VAL)
SET N = N+1
[END OF LOOP]
 Step 3: END
Discussion on FAQs

Questions:

1. Explain binary tree traversals with algorithms.

2. Explain the construction of Binary search tree with a suitable example.

3. List the properties of binary trees.

4. Write a C program to create and display a binary tree.

5. Write a C program to create, display and traverse a binary search tree.