Sweta Bohra

Data Structures
Sweta Bohra
Basic Terminologies
• Data :- Raw facts

• Data Item :- Raw facts which are part of our information

• Elementary items :- That are not divided into sub items.

Sweta Bohra
• Group items :- That are divided into sub items.

• Data Structure :- Techniques and methods are used to represent the data
in computer memory along with some operations to perform on it.

• Algorithm :- Step by step solution of a given problem.

• Flowchart :- Graphical representation of solution of given problem

Classification Of Data Structures
• Primary/Primitive/Fundamental
• Character, Integer, Float, Void
• Secondary/User defined/Derived/Non Primitive
• SIMPLE
• Arrays
• 1-d,2-d,…n-d
• Structure/Record

Sweta Bohra
• Pointer
• Union
• Enumeration
• Typedef
• COMPOUND
• Linear
• Linked List
• Stacks
• Queues
• Non Linear
• Graphs
• Trees
• Files
Classification Of Data Structures

Data Structure may be classified as

Sweta Bohra
LINEAR Data Structure
Elements forms a sequence

NONLINEAR Data Structure

Elements does not form a sequence
 Primitive And Non Primitive Data Type

Primitive Data Type

Which are not composed of other data type

Sweta Bohra
Non Primitive Data Type

Which are composed of primitive data type normally

these data type are defined by the some type refer
as user defined data type.
Classification Of Non Primitive Data Type

Non primitive data type can further divided in 2 categories.

Simple Data Structure

Sweta Bohra
Normally build from primitive data type

Compound Data Structure

Simple data structure can be combined in various ways to
form A complex structure are called compound data
structure
Simple Data Structure
Following data structure can be formed is simple data structure

Array

Sweta Bohra
Collection of homogeneous data items

Structures
Collection of heterogeneous data items
Compound Data Structure
Compound data structures are

Linear
Those data structure which are single level said to be

Sweta Bohra
linear or single level data structure

Examples stack, queue, linked list

Non-linear
Those data structure which are multilevel like tree,
graph and forests are termed is nonlinear
Operations on data structure

There are four major operations applied by all data structures

• Traversing
Accessing each record once so that all items in the record may

Sweta Bohra
be processed.
• Searching
Finding the location of the record with a given key value.
• Inserting
Adding new record to the structure .
• Deleting
Removable of a data element from a data structure
Other Operations

There are two other operations that are applied on data

structures.

Sweta Bohra
• Sorting
Means arranging of an data element of a data structure
in a specified order.

• Merging
Means combining the two similar data structure to form
a new data structure of same type
Primitive Data Type

• Which are NOT composed of other data type.

• Its like fundamental data types

Sweta Bohra
Example (in C) : int,
float,
char,
void
Non Primitive Data Type

• Which are composed of other data type.

• These are referred as User Defined Data Type

Sweta Bohra
Example (in C) : Stack
Queue
Linked List etc.

• NP Data Type can further categorized in 2 parts

• Simple
• Compound
Classification Of Data Structures
• Primary/Primitive/Fundamental
• Character, Integer, Float, Void
• Secondary/User defined/Derived/Non Primitive
• SIMPLE
• Arrays
• 1-d,2-d,…n-d
• Structure/Record

Sweta Bohra
• Pointer
• Union
• Enumeration
• Typedef
• COMPOUND
• Linear
• Linked List
• Stacks
• Queues
• Non Linear
• Graphs
• Trees
• Files
Array

• Single piece of data – Variable

• Whole bunch of data all at once – Array

• An Array is a “collection variable of same type” or data

Sweta Bohra
structure.

• It can store finite number of element.

• It is simplest data structure and easy to

• TRAVERSE
• SORT
• SEARCH
 Array
can store a
fixed-size contiguous (sequence)

Sweta Bohra
collection of
homogenous elements in
linear structure manner in
memory.
Array
A Finite number ‘N’ is called the length or size or range of an array.

Instead of declaring individual variables, such as number0, number1, ...,

and number99,

Sweta Bohra
You declare one array variable such as numbers and use numbers[0],
numbers[1], and ..., numbers[99] to represent individual variables.

A specific element in an array is accessed by an INDEX.

Types of Array
1. One dimensional array [1-d] and
2. Multidimensional array [n-d]

The lowest address corresponds to the first element and

the highest address to the last element.
Array

1 2 3 4 5 6 7 8
1 n

Here, n is length of array

Sweta Bohra
(total number of data can be stored in array)
and it can be found by index (Lower bound and Upper bound).

Lower bound (LB); smallest index i.e. 1

Upper bound (UB); largest index i.e. 8

Length = (UB – LB) +1

Length = (8 – 1) +1
Length = (7) +1
Length = 8
1-d array, 2-d array and n-d array

Sweta Bohra
Array
Question: If we take array variable 8 then what is the size
of an array.

LB = 1

Sweta Bohra
UB = 8

Length = (UB – LB) +1

Length = (8 – 1) +1
Length = (7) +1
Length = 8
 Way of representing linear structures in memory (1-d):

Relationship of elements represented by means of sequential memory locations.

(Array)

Sweta Bohra
Here ‘num’ is the name of the array, size is 5 and it is of int type. The array
subscript always starts from zero.
 Way of representing linear structures in memory (n-d):

Let take example of 2d array of m rows and n columns.

It will be represented in memory by a block of

m.n sequential memory locations.

Sweta Bohra
It can be store in memory by programming language in
two different ways

1. Column by Column (Column-major order)

2. Row by Row(Row major order)

 Way of representing linear structures in memory (1-d):
1. Column by Column (Column-major order)
Column-major order is a similar method of flattening arrays onto linear
memory, but the columns are listed in sequence.

Sweta Bohra
2. Row by Row(Row major order)
In row-major storage, a multidimensional array in linear memory is
organized such that rows are stored one after the other.
Computer does not keep track of address of each element
of array; rather it will store address of first element i.e.
Base Address

Sweta Bohra
 Example

Sweta Bohra
Operations on Linear Array
There are four major operations applied by all data structures
• Traversing
Accessing each record once so that all items in the record may be
processed.
• Searching

Sweta Bohra
Finding the location of the record with a given key value.
• Inserting
Adding new record to the structure .
• Deleting
Removable of a data element from a data structure
• Sorting
Means arranging of an data element of a data structure in a
specified order.
• Merging
Means combining the two similar data structure to form a
new data structure of same type
 Sweta Bohra
Traversal
Traverse elements in an Array
Traversal (Array) Process each element

• Let ‘A’ be a collection of data elements in the memory.

• Traverse; to go through all the elements of the collection
• Traverse may be from
• Beginning

Sweta Bohra
• End
• In-between
• At Specific location
• What we can do
• Print elements
• Count number of elements
• Sum of all the elements
• Search specific number etc.
Traversal (Array) - Process each element

Algorithm: Traversing a Liner Array

(Applying any process to each element of Linear Array)
LA: Linear Array
LB: Lower Bound
UB: Upper Bound

Sweta Bohra
N: Total Number present in array

TRAVERSE(LA,LB,UB,N)
Step 1. Set K = LB
Step 2. Repeat Step 3 to Step 4 while K < LB+N
Step 3. PROCESS LA[K]
Step 4. K=K+1
End while
Step 5. End
Traversal - Dry Run

Sweta Bohra
Traversal - C Program
void printArray(int* arr, int lb, int ub, int n)
4 8 1 9 6
{
int i;
0 1 2 3 4

printf("Array: ");
for (i = lb; i < n; i++) {
printf("%d ", arr[i]); lb n ub

Sweta Bohra
}
printf("\n");
}

int main()
{
int arr[] = { 2, -1, 5, 6, 0, -3 };
int n = sizeof(arr) / sizeof(arr[0]);
int lb = 0;
int ub = n;
printArray(arr, lb, ub, n);

return 0;
}
 Sweta Bohra
Analysis of Algorithm
Complexity of an Algorithm
Algorithm
Finite number of sets to solve a problem.
Charactersticsof algorithm
1. It should contain finite number of steps and for execution
contain finite time.
2. [Link] should contain unambiguous symbol.
Analysis
It is the process of comparing two Algorithms w.r.t, time, space, etc.

Sweta Bohra
Analysis

Priory Posterior
Calculate on the base of Iteration Dependent on a particular Hardware
• Gives Approx. Value • Gives Exact Value
• (Independent) • (Dependency)
• Uniformity • Value is not uniform
 Asymptotic Notation
It’s a mathematical way to represent time complexity. n = input value
t = time
1. Big - Oh (O) 2. Big - Omega [Link]

t t t
c.g(n) c2.g(n)
f(n) f(n) f(n)

Sweta Bohra
c1.g(n)
c.g(n)

k n k n k n

• Worst Case • Best Case • Average Case

• Upper Bound (At most) • Lower Bound (At least) • Exact time
 Asymptotic Notation
1. Big – oh (O) c = constant value
Graph Convention n = input value
f(n) = O g(n) t = time
t f(n) <= c.g(n)
c.g(n)
where c > 0
f(n)
n>k

Sweta Bohra
k >=0

k n
Let’s take an example
f(n) = 2n2+n
f(n) = 0 Closest value
• Worst Case 2n2+n <= c.g(n2)
• Upper Bound (At most)
 Asymptotic Notation
2. Big - Omega c = constant value
Graph Convention n = input value
t f(n) = g(n) t = time
f(n) >= c.g(n)
f(n) where c > 0
n>k

Sweta Bohra
k >=0

c.g(n)

k n Let’s take an example

f(n) = 2n2+n
f(n) = 0 Closest value {greatest lower
• Best Case 2n2+n >= c.g(n2) bound}
• Lower Bound (At least)
 Asymptotic Notation
3. Theta c = constant value
n = input value
t = time
t
c2.g(n)
f(n)
Graph Convention
c1.g(n) C1.g(n) <=f(n) <= c2.g(n)

Sweta Bohra
k n

• Average Case
• Exact time
 Sweta Bohra
Search
Search specific element in an Array
Search in (Array) Search specific element

• It refers to
• Operations to find location of item in array A
• Element exists or not
• If found it is SUCCESSFUL

Sweta Bohra
• If not found it is FAILED
• Complexity is measured in terms of
• Number of f(n) comparison required
• Two different types of searching
• Linear Search
• Binary Search
Linear Search in (Array)

• Suppose
• A ; is a Linear Array
• N ; is total number of elements
• Item ; is element to search

Sweta Bohra
• LOC ; Location of element
• Compare each element with element one by one
• From A[I] to a[N]
• To search and locate element sequentially is called
as Linear Search.
Linear Search (Algorithm)
LA: Linear Array
LB: Lower Bound
UB: Upper Bound
N: Total Number present in array
NUM: Number to search

SEARCH(LA,LB,UB,N,NUM)

Sweta Bohra
Step 1. Set K = LB
Step 2. Repeat Step 3 to Step 4 while K < LB+N {or K<=LB+N-1}
Step 3. if (LA[K] = NUM)
PRINT“Element found at”,K
End
End if
Step 4. K=K+1
Step 5. End while
Step 6. PRINT “Element not found!”
Step 7. End
Linear Search - Dry Run

Sweta Bohra
Complexity of Linear Search

1. Best Case : O(1) where the element is found at the first

index.

2. Worst Case : O(n) where the element is found at the

Sweta Bohra
last index or element is not present in the array.

• Average Case : O((n+1)/2) where the average number of

comparison required to find the location of item is
approximately equal to half the number of elements in
the array.
Binary Search in (Array)

Array on which binary search is to applied is must be SORTED. It can

be increasing or decreasing.

A binary search or half-interval search algorithm finds the position of

a specified input value (the search "key") within an array sorted by
key value

Sweta Bohra
In each step, the algorithm compares the search key value with the
key value of the middle element of the array.

If the keys match, then a matching element has been found and its
index, or position, is returned. Otherwise, if the search key is less
than the middle element's key, then the algorithm repeats its action
on the sub-array to the left of the middle element or, if the search
key is greater, on the sub-array to the right.

If the remaining array to be searched is empty, then the key cannot be

found in the array and a special "not found" indication is returned.
 Binary Search (Algorithm)
Algorithm: Binary Search in Linear Array (Find element from Linear Array)
LA: Linear Array LB: Lower Bound
UB: Upper Bound N: Total Number present in array
ITEM: Number to search

BINARYSRCH(LA,LB,UB,N,NUM,ITEM)
Step 1. Set BEG = LB
Step 2. Set END = LB+N-1
Step 3. MID = int(BEG+END)/2
Step 4. Repeat Step 4 to Step while BEG < END AND LA[MID]!= ITEM
Step 5. if (LA[MID] < ITEM)

Sweta Bohra
BEG = MID+1
End if
if (LA[MID] > ITEM)
END = MID-1
End if
MID = int(BEG+END)/2
Step 6. End while
Step 7. if (LA[MID] = ITEM)
LOC = MID
ELSE
LOC = NULL
End IF
Step [Link]
Binary Search (Array)

Sweta Bohra
Complexity of Binary Search

1. Best Case : O(1) where the element is found at the first

index.

2. Worst Case : Log2N where the element is found at the

Sweta Bohra
last index or element is not present in the array.

3. Average Case : Log2N where the average number of

comparison required to find the location of item is
approximately equal to half the number of elements in
the array.
 Comparisons of various time complexities

O(c) < O(log logn) < O(logn) < O(n1/2) <

O(n) < O(n logn) < O(n2) < O(n3) <

Sweta Bohra
n
O(nk) < O(2n) < O(nn) < 2
O(2 )
 Sweta Bohra
Sorting
Arrange the array in specific order
Sort an (Array) Arrange an array in
specific order
Sorting refers to arranging data in a particular format. Sorting algorithm
specifies the way to arrange data in a particular 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.

Types of Sorting algorithms:-

Sweta Bohra
Although there is no. of sorting algorithms best algorithm is which can solve a
problem in the minimum time and minimum space required to do so

1. Bubble Sort 8. Radix Sort

2. Insertion Sort 9. Shell Sort
3. Selection Sort 10. Comb Sort
4. Quick Sort 11. Cycle Sort
5. Heap Sort 12. Bitonic Sort
6. Counting Sort 13. Tree Sort
7. Bucket Sort 14. Stooge Sort
Sorting Categories
There are two different categories in sorting:

Internal sorting: If the input data is such that it can be adjusted in the main
memory at once, it is called internal sorting.

External sorting: If the input data is such that it cannot be adjusted in the memory
entirely at once, it needs to be stored in a hard disk, floppy disk, or any other
storage device. This is called external sorting.

Sweta Bohra
Bubble Sorting
Bubble Sort: It’s one of the simplest algorithms which repeatedly iterates
through the list, compares the elements next to each other, and swaps
according to the condition passed to them.

Suppose, an array, arr [5] = {14,33,27,35,10} and we have to sort it in

increasing order then Steps followed would be as:

Sweta Bohra
Here two loops would be required in sorting, the first loop for iterating and
the second loop for comparing.
As first you’ll check if the previous element is greater than the next element
then swap it otherwise increase the counter.
Bubble Sort (Array)

Sweta Bohra
Bubble Sort (Array) Contd…

Sweta Bohra
Bubble Sort (Algorithm)
LA: Linear Array
N: Total Number present in array

BUBBLE(LA, N,TEMP)
Step 1. i=0
Step 2. Repeat Step 3 to Step 4 while i<N-1

Sweta Bohra
Step 3. Repeat Step 4 for j=0 to [(N-1)-i]
Step 4. if(LA[j]>LA[j+1]
TEMP=LA[j]
LA[j]=LA[j+1]
LA[j+1]=TEMP
End if
Step 4. End for
i=i+1
Step 5. End while
Step 6. End
Complexity of Bubble Sort
1. Best Case : O(n) where the element is found at the first
index.

2. Worst Case : O(n2) where the element is found at the

last index or element is not present in the array.

Sweta Bohra
3. Average Case : O(n2) where the average number of
comparison required to find the location of item is
approximately equal to half the number of elements in
the array.
 Insertion Sorting
Insertion sort is the sorting mechanism where the sorted array is built having one
item at a time. The array elements are compared with each other sequentially and
then arranged simultaneously in some particular order. The analogy can be
understood from the style we arrange a deck of cards. This sort works on the
principle of inserting an element at a particular position, hence the name
Insertion Sort.

LA: Linear Array

N: Total Number present in array

Sweta Bohra
INSERTION-SORT(LA , n)
Step 1: for i = 1 to n
Step 2: key =LA [i]
Step 3: j=i – 1
Step 4: while j > 0 and LA[j] > key
Step 5: LA[j+1] = LA[j]
Step 6: j=j–1
Step 7: End while
Step 8: LA[j+1] = key
Step 9: End for
 Insertion Sorting
LA: Linear Array
N: Total Number present in array

INSERTION-SORT(LA , n)
Step 1: for i = 1 to n
Step 2: key =L A [i]
Step 3: j=i – 1
Step 4: while j > 0 and LA[j] > key
Step 5: LA[j+1] = LA[j]

Sweta Bohra
Step 6: j=j–1
Step 7: End while
Step 8: LA[j+1] = key
Step 9: End for

A B

1. Insertion Sort is Stable.

2. Insertion sort is in place. {No extra space is required}
3. It’s a online algorithm. {At the time of insertion, sort the array}
Consider the following array: 25, 17, 31, 13, 2

Sweta Bohra
Complexity of Insertion Sort
1. Best Case : O(n) where the element is found at the first
index.

2. Worst Case : O(n2) where the element is found at the

last index or element is not present in the array.

Sweta Bohra
3. Average Case : O(n2) where the average number of
comparison required to find the location of item is
approximately equal to half the number of elements in
the array.
 Selection Sorting
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.

Sweta Bohra
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.
 Selection Sorting
LA: Linear Array
N: Total Number present in array

SELECTION-SORT(LA , n)
Step 1: for i = 1 to n-1
Step 2: min=i *set current element as minimum
Step 3: for j=i+1 to n

Sweta Bohra
Step 4: If (LA[j]<LA[min]) then *check the element minimum
Step 5: min=j
Step 6: End if
Step 7: End for
Step 8: If indexmin != i *swap min element with current element
Step 9: Swap LA[min] and LA[i]
Step 10: End if
Step 11: End for
 Selection Sorting
Let the elements of array are -

Sweta Bohra
Selection Sorting

Sweta Bohra
Complexity of Selection Sort
1. Best Case : O(n2) where the element is found at the first
index.

2. Worst Case : O(n2) where the element is found at the

last index or element is not present in the array.

Sweta Bohra
3. Average Case : O(n2) where the average number of
comparison required to find the location of item is
approximately equal to half the number of elements in
the array.
 Sweta Bohra
Insertion
Insert specific element in an Array
Insertion (Array) Add element

• Let ‘A’ be a collection of data elements in the memory.

• Insertion; operation of adding element to collection
• Insertion may be at

Sweta Bohra
• CASE 1 : Beginning

• CASE 2 : End

• CASE 3 : At Specific location After

• CASE 4 : At Specific location Before

CASE 1 : INSERT in (Array) ; @ Beginning
Algorithm: Insertion in Linear Array
LA: Linear Array LB: Lower Bound UB: Upper Bound
N: Total Number present in array NUM: Element to search in array

INSERTFIRST(LA,LB,UB,N,NUM,ITEM)
Step 1. Set K = LB+N-1
Step 2. IF(K = UB) Array is Full
Step 3. PRINT “ARRAY IS FULL, CAN’T INSERT VALUE”
Step 4. EXIT

Sweta Bohra
Else
IF(N=0)
LA[0]=ITEM Array is Empty
Else
Step 5. Repeat Step 3 to Step 4 while K >= LB
Shift Element and
Step 6. LA[K+1]=LA[K]
create space at FIRST
K=K-1
Location
Step 7. End while
Step 8. LA[LB] = ITEM
End if
Step 9. N=N+1
End if
Step 10. End
CASE 1 : INSERT in (Array)
@ Beginning - Dry Run

Sweta Bohra
CASE 2 : INSERT in (Array) ; @ End
Algorithm: Insertion in Linear Array
LA: Linear Array • Check whether
LB: Lower Bound array is full or not.
UB: Upper Bound • Place required
N: Total Number present in array element at last in
NUM: Element to search in array list.

INSERTLAST(LA,LB,UB,N,NUM,ITEM)

Sweta Bohra
Step 1. Set K = UB
Step 3. IF(LB+N = UB)
Step 4. PRINT “ARRAY IS FULL, CAN’T INSERT VALUE”
Else
Step 5. LA[LB+N-1] = ITEM
Step 6. N=N+1
End if
Step 6. End
CASE 2 : INSERT in (Array)
@ End - Dry Run

Sweta Bohra
CASE 2 : INSERT in (Array) ;
@ After Specific Location
Algorithm: Insertion in Linear Array
LA: Linear Array
LB: Lower Bound
UB: Upper Bound
N: Total Number present in array
NUM: Element to search in array
INSERTAFTER(LA,LB,UB,N,VAL,ITEM)

Sweta Bohra
Step 1. Set K = LB
Set J = LB+N-1
Step 2. Repeat Step 3 to Step 4 while K < J
Search
Step 4. if (LA[K] = VAL)
BREAK
Element
End if
Step 5. K=K+1
Step 6. End while
Step 7. Repeat Step 3 and Step 4 while J >= K+1
Step 8. LA[J+1] = LA[J] Shifting
Step 9. J=J-1
End while
Step 10. LA[K+1] = ITEM Insert
Step 11. End
CASE 2 : INSERT in (Array) ;
@ After Specific Location - Dry Run

Sweta Bohra
CASE 2 : INSERT in (Array) ;
@ Before Specific Location
Algorithm: Insertion in Linear Array
LA: Linear Array
LB: Lower Bound
UB: Upper Bound
N: Total Number present in array
NUM: Element to search in array
INSERTBEFORE(LA,LB,UB,N,VAL,ITEM)

Sweta Bohra
Step 1. Set K = LB
Set J = LB+N-1
Step 2. Repeat Step 3 to Step 4 while K < J
Search
Step 4. if (LA[K] = VAL)
BREAK
Element
End if
Step 5. K=K+1
Step 6. End while
Step 7. Repeat Step 3 and Step 4 while J >= K
Step 8. LA[J+1] = LA[J] Shifting
Step 9. J=J-1
End while
Step 10. LA[K] = ITEM Insert
Step 11. End
CASE 2 : INSERT in (Array) ;
@ Before Specific Location - Dry Run

Sweta Bohra
 Sweta Bohra
Deletion
Delete specific element in an Array
DELETE element from (Array) ;

Algorithm: Deletion from Linear Array

LA: Linear Array LB: Lower Bound UB: Upper Bound
N: Total Number present in array ITEM: Number to delete

DELETE(LA,LB,UB,N,NUM,ITEM)
Step 1. Set K = LB
Step 2. Set J = LB + N

Sweta Bohra
Step 3. Repeat Step 3 to Step 4 while K <= J
Step 4. if (LA[K] = NUM)
BREAK
End if
Step 5. K=K+1
Step 6. End while
Step 7. Repeat Step 8 to Step 9 while K < J
Step 8. LA[K]=LA[K+1]
Step 9. K=K+1
End while
Step 10. N=N-1
Step 11. End
DELETE element from (Array) ;
@Delete from an array : Dry Run

Sweta Bohra
 POINTER ARRAY
{5,8,6,9,1,5,3} Integer Array : each elements are integer.
{0.2,2.3,5.6,9.2,8.2} Real Array : each elements are real.

Pointer Array : In array if each elements are pointer then it’s

called pointer array.
Pointer is the variable which contain the address of the

Sweta Bohra
elements.
POINTER ARRAY

Sweta Bohra
POINTER ARRAY
Let we have 4 groups.
Each group consist of list of members.
Membership list is stored in memory.
The most efficient method is to form two arrays. One is members consisting of all
members one after the other.
And another pointer array group containing the stating locations of different groups.
Observe that the elements of pointer array are starting addresses of each group.
1 BCA2-1
1 2 BCA2-2

Sweta Bohra
3 BCA2-3
5 4 BCA2-4

7 5 Bcom2-1
6 Bcom2-2
10 7 [Link].2-1
8 [Link].2-2
12
9 [Link].2-3
10 B.A.2-1

Fig: Pointer Array 11 B.A.2-2

12 END
 RECORDS ; Record Structures
A record is a data structure for storing a fixed number of elements. It is a collection of
related data items, each of which is called field or attribute.

In record the number to left of each variable is called level number.

Each group item is followed by its subitem.
The level of subitem is 1 more than the level of group item.

Sweta Bohra
Any particular field in record is accessed by using period.(dot)
{Student. Full Name. Last Name}

1. Student(15) It indicates 15 records in a file.

Collection of
Records
 Representation of Records in Memory
Records contain non homogeneous data.
To store record in memory we need parallel linear arrays.
i.e., one array for each elements of data item.

Sweta Bohra
 Array and Record
A record is a data structure for storing a fixed number of elements. It is a collection of
related data items, each of which is called field or attribute.

Array Records
1. Collection of homogeneous data 1. Collection of non-homogeneous
items. data.

Sweta Bohra
2. Elements are described by their 2. Elements in record are described by
subscript values level numbers.
3. Natural ordering of elements 3. As data items are indexed by
attribute names, so there may not be
natural ordering of its elements.
 Sweta Bohra
Arrays, Records and Pointers
Completed…
 Sweta Bohra
Linked List
Linear Structure
Linked List
A linked list or one way list is a linear collection of data element called ‘nodes’.

Each node is divided into 2 parts :

First part contains the information of the element are known as Info part.
Second part called the link field contains the address of the next node of the list.

Sweta Bohra
Garbage Collection
The Data Structure of computer may periodically collect all the deleted space on
to the full storage list. Any technique which does these collections is known as
garbage collection.

Garbage collection usually takes 2 steps:-

The computer runs through the entire list tagging those cells which are currently
in use.

Sweta Bohra
The computer runs throughout the memory collecting an untagged space onto
the free storage list.

Memory Allocation
Memory allocated from main memory & RAM memory can be allocated in two
forms.

1. Static
2. Dynamic
Memory representation of linear linked list
We require 2 linear arrays for memory representation. Let these two linear
arrays, first is INFO & second is LINK.

INFO [K] contains the information part

LINK [K] contains the next pointer field of node[K].

“START” is used to store the location of the beginning of the LIST and
“NULL” is used as next pointer field or link field which indicates the end of the
list.
The memory representation as follows:

Sweta Bohra
Types of Linked List
Following are the various types of linked list.

Simple Linked List − Item naviga on is forward only.

Doubly Linked List − Items can be navigated forward and backward.

Circular Linked List − Last item contains link of the first element as next and the

Sweta Bohra
first element has a link to the last element as previous.

Basic Operations
Following are the basic operations supported by a list.

1. Traversal − Read elements of the list.

2. Insertion − Adds an element at the beginning of the list.
3. Deletion − Deletes an element at the beginning of the list.
4. Display − Displays the complete list.
5. Search − Searches an element using the given key.
6. Delete − Deletes an element using the given key.
Creation of Linked List
Algorithm: Creation of Linked List

CREATE()
Step 1. Set START = NULL
Step 2. If Avail = NULL
return -1
Step 3. Repeat Step 4 to 11
Step 4. PRINT “Enter Value”

Sweta Bohra
Step 5. READ Value
Step 6. If Value = 0
Break
Step 7. NewNode = Request for Memory Allocation
Step 8. NewNode->Info = Value
Step 9. If START = NULL
START = NewNode
LAST = START
Else
LAST->Next = NewNode
Step 10. NewNode->Next = NULL
Step 11. End
Creation of Linked List

Sweta Bohra
Traversal
Algorithm: Traversal of Linked List

PRINT_LIST()
Step 1. If START = NULL
Step 2. return -1
Step 3. PTR = START
Step 4. Repeat Step 5 to 6 while PTR != NULL
Step 5. PRINT PTR->Info

Sweta Bohra
Step 6. PTR = PTR->Next
Step 7. End
Insert
1. At First
2. At Last
3. Before
4. After

Algorithm: Adding node in Linked List (FIRST)

INSERT_AT_FIRST(Value)
Step 1. NewNode = Request for Memory Allocation

Sweta Bohra
Step 2. NewNode->Info = Value
Step 3. If START = NULL
START = LAST = NewNode
Else
NewNode->Next = START
START=NewNode
Step 4. End
 Insert

Sweta Bohra
Insert
1. At First
2. At Last
3. Before
4. After

Algorithm: Adding node in Linked List (LAST)

INSERT_AT_LAST(Value)
Step 1. NewNode = Request for Memory Allocation

Sweta Bohra
Step 2. NewNode->Info = Value
Step 3. If START = NULL
START = LAST = NewNode
Else
LAST->Next = NewNode
LAST=NewNode
Step 4. End
Insert At Last

Sweta Bohra
Insert
1. At First
2. At Last
3. After
4. Before

Algorithm: Adding node in Linked List (AFTER)

INSERT_AFTER(START, Value, ItemtoInsert)

Step 1. If (START = NULL) // List Empty

Sweta Bohra
Return -1
Step 2. PTR = START
Step 3. Repeat Step 4 to 9 while(PTR->Info != ItemtoInsert)
Step 4. PTR = PTR->Next;
Step 5. If (PTR = NULL) // Item not found
Return -2
Step 6. NewNode = Request for Memory Allocation
Step 7. NewNode->Info = Value
Step 8. NewNode->Next = PTR->Next
Step 9. PTR->Next = NewNode
Step 10. End
Insert At After
PTR

START 51
501 51 101 211

501 Pen 51 Eraser 101 Pencil 211 Paper NULL

Sweta Bohra
Insert
1. At First
2. At Last
3. After
4. Before

Algorithm: Adding node in Linked List (BEFORE)

INSERT_AFTER(START, Value, ItemtoInsert)

Step 1. If (START = NULL) // List Empty

Sweta Bohra
Return -1
Step 2. PTR = START
Step 3. Repeat Step 4 to 10 while(PTR->Info != ItemtoInsert)
Step 4. PREV = PTR
Step 5. PTR = PTR->Next;
Step 6. If (PTR = NULL) // Item not found
Return -2
Step 7. NewNode = Request for Memory Allocation
Step 8. NewNode->Info = Value
Step 9. PREV->Next = NewNode
Step 10. NewNode->Next = PTR
Step 11. End
Insert At Before

Sweta Bohra
Delete
Algorithm: Deleting node in Linked List (FIRST)

DELETE_FIRST(START)
Step 1. If (START = NULL) // List Empty
Return -1
Step 2. START = START->Next

Sweta Bohra
 Delete At Last

Algorithm: Deleting node in Linked List (LAST)

DELETE_FIRST(START)

Step 1. If (START = NULL) // List Empty

Return -1
Step 2. START = START->Next

Sweta Bohra
Step 3. Repeat Step 4 to 5 while(PTR)
Step 4. PREV = PTR
Step 5. PTR = PTR->Next;
Step 6. Prev->Next = NULL
Step 7. End
Delete At Last

Sweta Bohra
 Delete Specific Node in Linked List

Algorithm: Deleting Specific node in Linked List

DELETE_FIRST(START, Val)
Step 1. If (START = NULL) // List Empty
Return -1
Step 2. PTR = START
Step 3. Repeat Step 4 to 5 while(PTR->Info != Val)

Sweta Bohra
Step 4. PREV = PTR
Step 5. PTR = PTR->Next;
Step 6. If (PTR = NULL) // Item not found
Return -2
Step 7. If (PTR = START)
START = START->Next
Else
PREV->Next = PTR->Next
Step 8. End
Delete Specific node from list

Sweta Bohra
 Sort Singly Linked List

Algorithm: Sorting of Singly Linked List (BUBBLE SORT)

SORT_LIST(START)
Step 1. CURRENT = START
Step 2. Repeat Step 3 to 6 while (CURRENT != NULL)
INDEX = CURRENT->Next
Step 3. Repeat Step 4 to 5 while (INDEX != NULL)

Sweta Bohra
Step 4. If(CURRENT->Info > INDEX->Info)
TMPInfo = CURRENT->Info
CURRENT->Info = INDEX->Info
INDEX->Info = TMPInfo
End IF
Step 5. INDEX=INDEX->Next
END Loop
Step 6. CURRENT=CURRENT->Next
End Loop
Step 7. END
 Creation of Ordered List
Algorithm: Creation of Ordered Linked List

CREATE()
Step 1. Repeat Step 4 to 11
Step 2. PRINT “Enter Value”
Step 3. READ Value
Step 4. If Value = 0
Break
Step 5. NewNode = Request for Memory Allocation
Step 6. NewNode->Info = Value

Sweta Bohra
Step 7. NewNode->Next=NULL
Step 8. If START = NULL
START = NewNode
LAST = START
Else
PTR = START
Step 9. Repeat Step while (PTR->Info <= InsertVal)
PREV = PTR
PTR=PTR->Next
End Loop
End If
Step 10. NewNode->Next = PREV->Next
Step 11. PREV->Next = NewNode
End Loop
Step 12. End
Creation of Ordered List

Sweta Bohra
Creation of Ordered List

Sweta Bohra
Insertion in Ordered List
Algorithm: Insert Element in Ordered Linked List

CREATE(START, InsertVal)
Step 1. NewNode = Request for Memory Allocation
Step 2. If Avail = NULL
Return -1
Step 3. NewNode->Info = Value
Step 4. NewNode->Next = NULL

Sweta Bohra
Step 5. If START = NULL
Step 6. START = NewNode
Step 7. LAST = START
Else
Step 8. PTR = START
End If
Step 9. Repeat Step 10 to 11 while (PTR->Info <= InsertVal)
Step 10. PREV = PTR
Step 11. PTR=PTR->Next
End Loop
Step 12. NewNode->Next = PREV->Next
Step 13. PREV->Next = NewNode
Step 14. End
Insertion in Ordered List

Sweta Bohra
Insertion in Ordered List

Sweta Bohra
 Traversal in Ordered List
Algorithm: Traversal of Ordered Linked List

PRINT_LIST()
Step 1. If START = NULL
Step 2. return -1
Step 3. PTR = START
Step 4. Repeat Step 5 to 6 while PTR != NULL
Step 5. PRINT PTR->Info
Step 6. PTR = PTR->Next
Step 7. End

Sweta Bohra
 Deletion in Ordered List
Algorithm: Delete Element from Ordered Linked List

DELETE_NODE(START, Val)
Step 1. If (START = NULL) // List Empty
Return -1
Step 2. PTR = START
Step 3. Repeat Step 4 to 5 while(PTR->Info != Val)
Step 4. PREV = PTR
Step 5. PTR = PTR->Next;

Sweta Bohra
Step 7. If (PTR = NULL) // Item not found
Step 8. Return -2
Step 9. If (PTR = START)
START = START->Next
Else
PREV->Next = PTR->Next
Step 10. End
Deletion in Ordered List

Sweta Bohra
Circular Linked List
Algorithm: Creation of Circular Linked List

CREATE()
Step 1. Repeat Step 2 to 4
Step 2. PRINT “Enter Value”
Step 3. READ Value
Step 4. If Value = 0
Break

Sweta Bohra
Step 5. NewNode = Request for Memory Allocation
Step 6. If Avail = NULL
Return -1
Step 7. NewNode->Info = Value
Step 8. NewNode-> Next = NULL
Step 9. If START = NULL
START = LAST = NewNode
NewNode->Next = START
Else
NewNode->Next = LAST->Next
LAST->Next = NewNode
LAST = NewNode
Step 10. End
Creation of Circular Linked List

Sweta Bohra
Creation of Circular Linked List

Sweta Bohra
 Traversal of Circular Linked List
Algorithm: Traversal of Circular Linked List

PRINT_LIST()
Step 1. If START = NULL
Step 2. return -1
Step 3. PTR = START
Step 4. Repeat Step 5 to 6 while PTR != START
Step 5. PRINT PTR->Info
Step 6. PTR = PTR->Next

Sweta Bohra
Step 7. End
 Insertion in Circular Linked List
1. At First
2. At Last
3. Before
4. After

Algorithm: Adding node in Circular Linked List (FIRST)

Sweta Bohra
INSERT_AT_FIRST(Value)
Step 1. NewNode = Request for Memory Allocation
Step 2. NewNode->Info = Value
Step 3. If START = NULL
START = LAST = NewNode
NewNode->Next = START
Else
NewNode->Next = START
START = NewNode
LAST->Next = NewNode
Step 4. End
Insertion in Circular Linked List

Sweta Bohra
Insertion in Circular Linked List

Sweta Bohra
 Insertion in Circular Linked List
Algorithm: Adding node in Linked List (LAST)

INSERT_AT_LAST(Value)
Step 1. NewNode = Request for Memory Allocation
Step 2. NewNode->Info = Value
Step 3. If START = NULL
START = LAST = NewNode

Sweta Bohra
NewNode->Next = START
Else
NewNode->Next = START
LAST->Next = NewNode
LAST=NewNode
Step 4. End
Insertion in Circular Linked List

Sweta Bohra
Insertion in Circular Linked List

Sweta Bohra
 Insertion in Circular Linked List
Algorithm: Adding node in Linked List (MID ; After Reference Value)

INSERT_AFTER(START, Value, ItemtoInsert)

Step 1. NewNode = Request for Memory Allocation

Step 2. NewNode->Info = Value

Sweta Bohra
Step 3. If (START = NULL) // List Empty
Return -1
Step 4. PTR = START
Step 5. Repeat Step 4 to 5 while(PTR->Info != ItemtoInsert)
Step 6. PTR = PTR->Next;
Step 7. If (PTR -> next = START) // Item not found
Return -2
Step 8. NewNode->Next = PTR->Next
Step 9. PTR->Next = NewNode
Step 10. End
 Insertion in Circular Linked List
Algorithm: Adding node in Linked List (MID ; Before Reference Value)

INSERT_BEFORE(START, Value, ItemtoInsert)

Step 1. NewNode = Request for Memory Allocation

Step 2. NewNode->Info = Value

Sweta Bohra
Step 3. If (START = NULL) // List Empty
Return -1
Step 4. PTR = START
Step 5. Repeat Step 4 to 5 while(PTR->Info != ItemtoInsert)
PREV=PTR
Step 6. PTR = PTR->Next;
Step 7. If (PTR -> next = START) // Item not found
Return -2
Step 8. PREV->Next = NewNode
Step 9. NewNode->Next = PTR
Step 10. End
 Deletion in Circular Linked List

Algorithm : Delete node in Linked List (At Begin)

DELETE_AT_BEGIN(START, PTR)

Step 1. If (START = NULL) // List Empty

Sweta Bohra
Return -1
else
Step 2. PTR = START
Step 3. START = PTR -> next
Step 4. LAST -> next = START
Step 5. End
 Deletion in Circular Linked List

Algorithm : Delete node in Linked List (At Last)

DELETE_AT_Last(START, PREV, PTR)

Step 1. If (START = NULL) // List Empty

Sweta Bohra
Return -1
else
Step 2. PREV = NULL
Step 3. PTR = START
Step 4. Repeat Step 5 to 6 while(PTR-> next != START)
Step 5. PREV = PTR
Step 6. PTR=PTR -> next
Step 7. PREV -> next = START
Step 8. LAST = PREV
Step 9. End
 Deletion in Circular Linked List
Algorithm: Deleting Specific node in Linked List

DELETE_FIRST(START, Val)
Step 1. If (START = NULL) // List Empty
Return -1
Step 2. PTR = START

Sweta Bohra
Step 3. Repeat Step 4 to 7 while(PTR->Info != Val)
Step 4. PREV = PTR
Step 5. PTR = PTR->Next;
Step 6. If (PTR -> next = START) // Item not found
PREV -> next = START
LAST = PREV
Step 7. If (PTR = START)
START = START->Next
LAST -> next = START
Else
PREV->Next = PTR->Next
Step 8. End
Doubly Linked List
Algorithm: Creation of Doubly Linked List

CREATE()
Step 1. Set START = NULL
Step 2. Repeat Step 3 to 11
Step 3. PRINT “Enter Value”
Step 4. READ Value
Step 5. If Value = 0
Break
Step 6. NewNode = Request for Memory Allocation
Step 7. NewNode->Info = Value

Sweta Bohra
Step 8. If START = NULL
START = NewNode
LAST = NewNode
START->Next = NULL
START->Prev =NULL
Else
PTR = START
Step 9. Repeat Step 11 to 11 while PTR != NULL
Step 10. PTR = PTR->Next
Step 11. End
Step 12. PRT->Next = NewNode
Step 13. NewNode->Prev = PTR
Step 14. NewNode->Next =NULL
Step 15. LAST = NewNode
Step 16. End
Doubly Linked List

Sweta Bohra
 Traversal in Doubly Linked List (Forward)

Algorithm: Traversal of Doubly Linked List (Forward)

PRINT_LIST()
Step 1. If START = NULL
Step 2. return -1

Sweta Bohra
Step 3. PTR = START
Step 4. Repeat Step 5 to 6 while PTR != NULL
Step 5. PRINT PTR->Info
Step 6. PTR = PTR->Next
Step 7. End
 Traversal in Doubly Linked List (Backward)

Algorithm: Traversal of Doubly Linked List (Backward)

PRINT_LIST()
Step 1. If LAST = NULL
Step 2. return -1

Sweta Bohra
Step 3. PTR = LAST
Step 4. Repeat Step 5 to 6 while PTR != NULL
Step 5. PRINT PTR->Info
Step 6. PTR = PTR->Prev
Step 7. End
 Insertion in Doubly Linked List
Algorithm: Adding node in Doubly Linked List (Begin)

INSERT_AT_FIRST(START, Value, SearchItem)

Step 1. NewNode = Request for Memory Allocation
Step 2. NewNode->Info = Value
Step 3. PTR = START
Step 4. If START = NULL

Sweta Bohra
START = LAST = NewNode
START->Next = NULL
START->Prev =NULL
Step 5. Repeat Step 5 to 6 while(PTR->Info != SearchItem)
Step 6. PTR=PTR->Next
End While
Step 5. If PTR = START
NewNode->Next = START
START->Prev = NewNode
START = NewNode
Step 6. End
 Insertion in Doubly Linked List
Algorithm: Adding node in Doubly Linked List (Last)

INSERT_AT_LAST(START, Value, SearchItem)

Step 1. NewNode = Request for Memory Allocation
Step 2. NewNode->Info = Value
Step 3. PTR = START
Step 4. If START = NULL

Sweta Bohra
return -1
Step 5. Repeat Step 5 to 6 while(PTR->Info != SearchItem)
Step 6. PTR=PTR->Next
End While
Step 7. If PTR = LAST
NewNode->Next = PTR->Next
NewNode->Prev = PTR
PTR->Next = NewNode
LAST = NewNode
Step 8. End
 Insertion in Doubly Linked List
Algorithm: Adding node in Doubly Linked List (AFTER)

INSERT_AFTER(START, Value, SearchItem)

Step 1. If (START = NULL) // List Empty
Return -1
Step 2. PTR = START
Step 3. Repeat Step 4 to 9 while(PTR->Info != SearchItem)

Sweta Bohra
Step 4. PTR = PTR->Next;
Step 5. If (PTR = NULL) // Item not found
Return -2
Step 6. NewNode = Request for Memory Allocation
Step 7. If PTR = LAST
LAST = NewNode
Step 7. NewNode->Info = Value
Step 8. NewNode->Next = PTR->Next
NewNode->Prev = PTR
PTR->Next = NewNode
PTR->Next->Prev = NewNode
Step 10. End
 Insertion in Doubly Linked List
Algorithm: Adding node in Doubly Linked List (BEOFRE)

INSERT_BEFORE(START, Value, SearchItem)

Step 1. If (START = NULL) // List Empty
Return -1
Step 2. PTR = START
Step 3. PREV = START
Step 4. Repeat Step 4 to 9 while(PTR->Info != SearchItem)
Step 5. PREV = PTR
Step 6. PTR = PTR->Next;

Sweta Bohra
Step 7. If (PTR = NULL) // Item not found
Return -2
Step 8. NewNode = Request for Memory Allocation
Step 9. If PTR = START
NewNode->Next = START
START->Prev = NewNode
START = NewNode
Else
NewNode->Info = Value
NewNode->Next = PTR
PREV->Next = NewNode
PTR-> Prev = NewNode
NewNode->PREV = PREV->NEXT
Step 10. End
 Deletion in Doubly Linked List

Algorithm : Delete node in Linked List (At Begin)

DELETE_AT_BEGIN(START, PTR)

Step 1. If (START = NULL) // List Empty

Sweta Bohra
Return -1
else
Step 2. PTR = START
Step 3. START = PTR -> next
Step 4. PTR -> next -> Prev = NULL
Step 5. End
 Deletion in Doubly Linked List

Algorithm : Delete node in Linked List (At Last)

DELETE_AT_LAST(START, PTR, PREV)

Step 1. If (START = NULL) // List Empty

Sweta Bohra
Return -1
else
Step 2. PTR = START
Step 3. PREV=PTR
Step 4. Repeat while PTR -> next !=null
Step 5. PREV=PTR
Step 6. PTR=PTR -> next
Endwhile
Step 7. PREV -> next = NULL
Step 8. End
 Deletion in Doubly Linked List

Algorithm : Delete node in Linked List (At Mid)

DELETE_AT_MID(START, PTR, PREV, RefV)

Step 1. If (START = NULL) // List Empty
Return -1

Sweta Bohra
else
Step 2. PTR = START
Step 3. PREV=PTR
Step 4. Repeat while PTR -> info != RefV
Step 5. PREV=PTR
Step 6. PTR=PTR -> next
Endwhile
Step 7. PREV -> next = PTR -> next
Step 8. PTR -> next -> Prev = PREV
Step 9. End
 Sweta Bohra
Linked List Completed…
 Sweta Bohra
Stack
Linear Structure
Stack
A Stack is a list of element in which an element may be Inserted or
Deleted only at one end called the TOP of Stack.

max

Sweta Bohra
F
E
D
C
B
min A
STACK
Operations on Stack
2 basic Operations:

1. Push.
2. Pop.

1. Push : It is term used to insert an element into a Stack.

2. POP : It is term used to delete an element into a Stack.

Sweta Bohra
Representation of Stack
2 Representation:

1. Array Representation.
2. Linked Representation
Insert an element in Stack :
Push Operation
Algorithm : Push an element in Stack.
PUSH(STACK, TOS, max, Item)

Step 1: If (TOS = max)

print “overflow condition”
Endif

Sweta Bohra
Step 2: TOS=TOS+1. Case 1: Case 2:
Step 3: STACK[TOS] = Item. TOS
Step 4: END. max H 7 max 7
G 6 6
F 5 TOS F 5
E 4 E 4
D 3 D 3
C 2 C 2
B 1 B 1
min A 0 min A 0
STACK STACK
Insert an element in Stack :
Pop Operation
Algorithm : Pop an element in Stack.
POP(STACK, TOS, max, Item)

Step 1: If (TOS = -1)

print “underflow condition”
Endif

Sweta Bohra
Step 2: Item = STACK[TOS} Case 1: Case 2:
Step 3: TOS = TOS - 1 TOS
Step 4: END. max 7 max 7
6 6
5 TOS F 5
4 TOS E 4
3 D 3
2 C 2
1 B 1
min 0 min A 0
STACK STACK
Linked Representation of Stack
Algorithm: Adding node in Linked List (PUSH)

PUSH(Value)
Step 1. NewNode = Request for Memory Allocation
Step 2. NewNode->Info = Value
Step 3. If TOS = NULL
TOS=NewNode

Sweta Bohra
Else
NewNode->Next = TOS
TOS=NewNode
Step 4. End
Linked Representation of Stack

Sweta Bohra
Linked Representation of Stack
Algorithm: Deleting node in Linked List (POP)

DELETE_FIRST(START)
Step 1. If (TOS = NULL) // List Empty
Return -1
Step 2. Val = TOS->Val
Step 3. TOS = TOS->Next

Sweta Bohra
Step 4. Return Val
Arithmetic Expression
Let
Q is an Arithmetic expression involving constant and operations.

3 levels of precedence for usual 5 binary operations

Highest : Exponentiation ()

Sweta Bohra
Next Highest : Multiplication (*) and Division (/)
Lowest : Addition (+) and Subtraction (-)

For simplicity
we use BINARY operations
No UNARY operations
Operations performed left to right
Arithmetic Expression
Notations are of 3 types
PreFix (Polish Notation)
+AB Opr OpRand OpRand

InFix

Sweta Bohra
A+B OpRand Opr OpRand

PostFix (Reverse Polish Notation)

AB+ OpRand OpRand Opr

The compiler usually evaluates Infix Expression in 2 steps

1. Convert Infix to Postfix Expression
2. Evaluation of Postfix Expression
And in both the cases STACK is important
Arithmetic Expression

Sweta Bohra
Arithmetic Expression

Sweta Bohra
Arithmetic Expression

Sweta Bohra
Arithmetic Expression
1. Infix to Postfix Notation

Let Q, Arithmetic Expression in InFix notation

Having
Operators
Exponentiation ()
Multiplication (*) and Division (/)

Sweta Bohra
Addition (+) and Subtraction (-)
with 3 level precedence
(if on same level LEFT to RIGHT)
Operands
( left parenthesis
) right parenthesis

Algorithm
Uses STACK to hold Operators and (.
Will be constructed from Left to Right using
Operands from Q
Operators which are removed from STACK
Arithmetic Expression
Suppose Q is Infix Expression

Step 1. PUSH (
Step 2. ADD ) at End of Q
Step 3. Scan Q from Left to Right
Step 4. Repeat Step _ to _ Until Stack is Empty
Step 5. If OPERAND

Sweta Bohra
ADD it to P
Step 6. If (
PUSH (
Step 7. If OPEARTOR
Val = POP and ADD to P
Until having same precedence and higher precedence than Val
PUSH Val
Step 8. If )
Val = POP and ADD to P
Until ) encountered
Remove ); but not add to P
Step 9. Exit
 Arithmetic Expression
Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Sweta Bohra
The final postfix expression of infix expression

(K + L - M*N + (O^P) * W/U/V * T + Q) is

KL+MN*-OP^W*U/V/T*+Q+.
Arithmetic Expression
2. Evaluation of Postfix Notation

Suppose P is an Arithmetic expression

(postfix expression)
Algorithm will use Stack to hold Operands

Sweta Bohra
Step 1. ADD “)” at End of P
Step 2. Val = Scan P from Left to Right and Repeat Step 3 to 6
Untill “)” encountered
Step 3. If (Val = Operand)
PUSH(Val)
Step 4. If(Val = Operator)
V1 = POP()
V2 = POP()
Step 5. Res = Eval(V1 Val V2)
Step 6. PUSH(Res)
Step 7. FinalRes = POP()
Arithmetic Expression
Now let us consider the following infix expression
2 * (4+3) - 5.
Its equivalent postfix expression is
2 4 3 + * 5.

The following step illustrates how this postfix expression is evaluated.

Sweta Bohra
Recursion
The process in which a function calls itself directly or indirectly is called
recursion and the corresponding function is called as recursive function.

Examples of such problems are Towers of Hanoi

(TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.

APPROACH(1) – Simply adding one by one

Sweta Bohra
f(n) = 1 + 2 + 3 +……..+ n
but there is another mathematical approach of representing this,

APPROACH(2) – Recursive adding

f(n) = 1 n=1
f(n) = n + f(n-1) n>1
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;

Sweta Bohra
else
return n*fact(n-1);
}
 Direct and Indirect recursion
A function fun is called direct recursive if it calls the same function fun.
A function fun is called indirect recursive if it calls another function
// An example of direct recursion
void directRecFun()
{
// Some code....

directRecFun();

// Some code...

Sweta Bohra
}

// An example of indirect recursion

void indirectRecFun1()
{
// Some code...
indirectRecFun2();
// Some code...
}
void indirectRecFun2()
{
// Some code...
indirectRecFun1();
// Some code...
}
Tailed and non-tailed recursion

A recursive function is tail recursive when recursive call is the last thing
executed by the function.

For example the following C++ function print() is tail recursive.

// An example of tail recursive function

Sweta Bohra
void print(int n)
{
if (n < 0) return;
cout << " " << n;

// The last executed statement is recursive call

print(n-1);
}
Memory allocation to different function
calls in recursion
void printFun(int test)
{
if (test < 1)
return;
else {
cout << test << " ";
printFun(test - 1); // statement 2

Sweta Bohra
cout << test << " ";
return;
}
}

// Driver Code
int main()
{
int test = 3;
printFun(test);
}
Output :
321123
Memory allocation to different function
calls in recursion

Sweta Bohra
Application of stack : Recursion [Factorial]

Sweta Bohra
Application of stack : Recursion [Factorial]

Sweta Bohra
Application of stack : Recursion [Fibonacci
series]

Sweta Bohra
 Application of stack : Recursion [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

Sweta Bohra
on a stack.
3. No disk may be placed on top of a smaller disk.
 Application of stack : Recursion [Tower of
Hanoi]
Case 1: With 2 Disk

Sweta Bohra
 Application of stack : Recursion [Tower of
Hanoi]
Case 1 With 2 Disk

Take an example for 2 disks:

Let rod 1 = 'A', rod 2 = 'B', rod 3 = 'C'.

Step 1 : Shift first disk from 'A' to 'B'.

Sweta Bohra
Step 2 : Shift second disk from 'A' to 'C'.

Step 3 : Shift first disk from 'B' to 'C'.

Output :
Disk 1 moved from A to B
Disk 2 moved from A to C
Disk 1 moved from B to C

The pattern here is:

Shift 'n-1' disks from 'A' to 'B'.
Shift last disk from 'A' to 'C'.
Shift 'n-1' disks from 'B' to 'C'.
 Application of stack : Recursion [Tower of
Hanoi]
Case 2: With 3 Disk

Sweta Bohra
 Application of stack : Recursion [Tower of
Hanoi]
Case 2: With 3 Disk
Output :

Disk 1 moved from A to C

Disk 2 moved from A to B

Sweta Bohra
Disk 1 moved from C to B

Disk 3 moved from A to C

Disk 1 moved from B to A

Disk 2 moved from B to C

Disk 1 moved from A to C

Application of stack : Recursion [Tower of
Hanoi]

Sweta Bohra
Application of stack : Recursion [QuickSort]
Partition Exchange Sort

Application of Stack

Divide and Conquer

Sweta Bohra
A technique of breaking down the algorithms into subproblems then solving
the subproblems, and combining the results back together to solve the
original problem.

It picks an element as pivot and partitions the given array around the picked
pivot.
There are many different versions of quickSort that pick pivot in different
ways.
Always pick first element as pivot.
Always pick last element as pivot (implemented below)Pick a random
element as pivot.
Pick median as pivot.
Application of stack : Recursion [QuickSort]

Sweta Bohra
Application of stack : Recursion [QuickSort]

Sweta Bohra
Application of stack : Recursion [QuickSort]

Sweta Bohra
Application of stack : Recursion [QuickSort]

Sweta Bohra
Application of stack : Recursion [QuickSort]
The algorithm works as follows:
QuickSort(LA,BEG,END)
1. If(BEG < END)
2. X=partition(LA,BEG,END)
3. QuickSort(LA,BEG,x-1)
4. QuickSort(LA,x+1,END)
Endif

Sweta Bohra
5. End.

Partition function Partition(LA,BEG,END)

1. Piv=BEG
2. Repeat while(1)
3. Repeat while(LA[Piv]<=LA[END] and Piv!=END)
4. END—
5. [end while]
6. If(Piv = = End)
7. Return Piv
8. Swap(LA[Piv],LA[End])
9. Piv=End
Application of stack : Recursion [QuickSort]
[Link] while(LA[Piv]>=LA[BEG]and Piv!=BEG)
[Link]++
[Link](Piv= =BEG)
[Link] Piv
[Link](LA[Piv],LA[BEG])
[Link]=BEG

Sweta Bohra
[endwhile]
[Link].

Swap(LA,BEG,END)
1. Temp=LA[Piv]
2. LA[Piv]=LA[END]
3. LA[END]=Temp
4. End.
 Sweta Bohra
Stack Completed…
 Sweta Bohra
Queue
Linear Structure
Queue
A queue is open at both its ends.
One end is always used to insert data (enqueue)
And the other is used to remove data (dequeue)

The order is First In First Out (FIFO).

The difference between stacks and queues is in removing.

Sweta Bohra
In a stack we remove the item the most recently added;
In a queue, we remove the item the least recently added.
Array Implementation
Algorithm 1: Only access first element (peek)

PEEK(Queue, Front, MAXSize)

Step 1. Return Queue[Front]

Sweta Bohra
Array Implementation
Algorithm 2: Check whether queue is full (isFull)

isFull(Queue, Front, Rear, MAXSize)

Step 1. if(rear == MAXSIZE - 1)
return true;
else

Sweta Bohra
return false;
Step 2. END
Array Implementation
Algorithm 3: Insert element in queue (Enqueue)

enQueue(Queue, Front, Rear, MAXSize, Value)

Step 1. if(isfull())
return 0;

Sweta Bohra
Step 2. Rear = Rear + 1;
Step 3. Queue [Rear] = Value;

Step 4. END
Array Implementation
Algorithm 4: Remove element in queue (Dequeue)

deQueue(Queue, Front, Rear, MAXSize)

Step 1. if(isEmpty())
return 0;
Step 2. Value = Queue [0];

Sweta Bohra
Step 3. I=0

Step 4. Repeat Step 5 to Step 6

Step 5. Queue[I] = Queue[I+1]

Step 6. I = I +1;

Step 7. Rear = Rear - 1

Step 8. return Value

Array Implementation
Remove element in queue (Dequeue)

Sweta Bohra
Linked Implementation
Adding node in Queue Linked List
(Insert/EnQueue)

INSERT_AT_Rear (Front, Rear, Value)

Sweta Bohra
Step 1. NewNode = Request for Memory Allocation
Step 2. NewNode->Info = Value
Step 3. If Rear = NULL
Rear = Front = NewNode
Else
Rear->Next = NewNode
Rear=NewNode
Step 4. End
Linked Implementation

Sweta Bohra
Linked Implementation
Algorithm:
Remove node from Queue (Linked List) (Remove/Dequeue)

Remove_from_Front (Front, Rear, Value)

Sweta Bohra
Step 1. If (Front = NULL) // List Empty
Return -1
Step 2. Val = Front->Info
Step 3. Front = Front->Next
Step 4. return Val
Linked Implementation

Sweta Bohra
Circular Queue
Circular Queue is a linear data structure in which the operations are
performed based on FIFO (First In First Out) principle
And the last position is connected back to the first position to make a
circle. It is also called ‘Ring Buffer’.

Sweta Bohra
Applications of Circular Queue
Memory management: The circular queue provides memory
management. As we have already seen that in linear queue,
the memory is not managed very efficiently. But in case of a
circular queue, the memory is managed efficiently by placing
the elements in a location which is unused.

Sweta Bohra
CPU Scheduling: The operating system also uses the circular
queue to insert the processes and then execute them.

Traffic system: In a computer-control traffic system, traffic

light is one of the best examples of the circular queue. Each
light of traffic light gets ON one by one after every jinterval of
time. Like red light gets ON for one minute then yellow light
for one minute and then green light. After green light, the red
light gets ON.
Insert an element in circular queue
Algorithm : Insert

INSERT(Queue, Rear, MAX)

Step 1. N = Rear
Step 2. IF ( Rear = MAX-1 ) // Element is at Last

Sweta Bohra
Rear = 0
ELSE
Rear = Rear + 1
Step 3. IF ( Rear == Front)
Rear = N // OVER FLOW

Step 4. Queue[Rear] = Val

Insertion in circular queue

MAX : 8

Sweta Bohra
Delete an element in circular queue
Algorithm : Remove

REMOVE(Queue, Rear, MAX)

Step 1. IF (Rear == Front)
Rear = N // UNDER FLOW

Sweta Bohra
Step 2. IF (Front = MAX-1) // Element is at Last
Front = 0
ELSE
Front = Front + 1

Step 3. Val = Queue[Front]

Step 4. return Val

DeQueue
The eQueue stands for Double Ended Queue.
In the queue, the insertion takes place from one end while
the deletion takes place from another end.
The end at which the insertion occurs is known as the rear
end.

Sweta Bohra
Whereas the end at which the deletion occurs is known
as front end.
Properties of DeQueue
DeQueue can be used both as stack and queue as it allows the insertion
and deletion operations on both ends.

1. In DeQueue, the insertion and deletion operation can be performed

from one side. The stack follows the LIFO rule in which both the
insertion and deletion can be performed only from one end;

Sweta Bohra
therefore, we conclude that DeQueue can be considered as a stack.
Properties of DeQueue
DeQueue can be used both as stack and queue as it allows the insertion
and deletion operations on both ends.

2. In deque, the insertion can be performed on one end, and the

deletion can be done on another end. The queue follows the FIFO rule in
which the element is inserted on one end and deleted from another

Sweta Bohra
end. Therefore, we conclude that the deque can also be considered as
the queue.
Types of DeQueue
There are two types of Queues:
1. Input-restricted queue.
2. Output-restricted queue.

1. Input-restricted queue: The input-restricted queue means that

some restrictions are applied to the insertion. In input-restricted

Sweta Bohra
queue, the insertion is applied to one end while the deletion is
applied from both the ends.
Types of DeQueue
There are two types of Queues:
1. Input-restricted queue.
2. Output-restricted queue.

2. Output-restricted queue: The output-restricted queue means that

some restrictions are applied to the deletion operation. In an

Sweta Bohra
output-restricted queue, the deletion can be applied only from one
end, whereas the insertion is possible from both ends.
Operations on DeQueue
The following are the operations applied on dequeue:

1. Insert at FRONT
2. Delete from REAR
3. Insert at REAR
4. Delete from FRONT

Sweta Bohra
 Sweta Bohra
Queue Completed…
 Sweta Bohra
Tree
Non-Linear Structure
Factors are considered for choosing the
data structure:
1. What type of data needs to be stored?

2. Cost of operations.

Sweta Bohra
3. Memory usage
 Tree
A tree is the data structures that represent hierarchical data.

Sweta Bohra
This particular logical structure is known as a Tree. Its structure is similar
to the real tree, so it is named a Tree. In this structure, the root is at the
top, and its branches are moving in a downward direction. Therefore,
we can say that the Tree data structure is an efficient way of storing the
data in a hierarchical way.
Key points used in Tree
1. A tree data structure is defined as a collection of objects or entities
known as nodes that are linked together to represent or simulate
hierarchy.

2. A tree data structure is a non-linear data structure because it does

not store in a sequential manner. It is a hierarchical structure as

Sweta Bohra
elements in a Tree are arranged in multiple levels.

3. In the Tree data structure, the topmost node is known as a root

node. Each node contains some data, and data can be of any type.
In the above tree structure, the node contains the name of the
employee, so the type of data would be a string.

4. Each node contains some data and the link or reference of other
nodes that can be called children.
Basic terms used in Tree

Sweta Bohra
In the above structure, each node is labeled with some
number. Each arrow shown in the above figure is known
as a link between the two nodes.
Basic terms used in Tree
Root: The root node is the topmost node in the tree hierarchy. In other
words, the root node is the one that doesn't have any parent. In the
above structure, node numbered 1 is the root node of the tree. If a
node is directly linked to some other node, it would be called a parent-
child relationship.

Sweta Bohra
Child node: If the node is a descendant of any node, then the node is
known as a child node.

Parent: If the node contains any sub-node, then that node is said to be
the parent of that sub-node.

Sibling: The nodes that have the same parent are known as siblings.
Basic terms used in Tree
Leaf Node:- The node of the tree, which doesn't have any child node, is
called a leaf node. A leaf node is the bottom-most node of the tree.
There can be any number of leaf nodes present in a general tree. Leaf
nodes can also be called external nodes.

Internal nodes: A node has atleast one child node known as an internal

Sweta Bohra
Ancestor node:- An ancestor of a node is any predecessor node on a
path from the root to that node. The root node doesn't have any
ancestors. In the tree shown in the above image, nodes 1, 2, and 5 are
the ancestors of node 10.

Descendant: The immediate successor of the given node is known as a

descendant of a node. In the above figure, 10 is the descendant of node
5.
Types of tree
1. General tree

Sweta Bohra
Types of tree
2. Binary tree

Sweta Bohra
Types of tree
3. Binary Search tree

Sweta Bohra
Binary tree representation
A binary tree data structure is represented using two
methods. Those methods are as follows...

Sweta Bohra
1. Array representation.
2. Linked list representation.
1. Array representation of Binary tree

Sweta Bohra
1. Array representation of Binary tree

Sweta Bohra
1. Array representation of Binary tree

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Sweta Bohra
10 5 16 - 8 15 20 - - - - - - - 23

we can easily get the posi on of two children of one node by using this formula −
To get parent index from child we have to follow this formula

To get parent index from child we have to follow this formula −

2. Linked representation of Binary tree

Sweta Bohra
 Basic operations on BST
1. Insert − Inserts an element in a tree/create a tree.

2. Search − Searches an element in a tree.

Sweta Bohra
3. Preorder Traversal − Traverses a tree in a pre-order
manner.

4. Inorder Traversal − Traverses a tree in an in-order

manner.

5. Postorder Traversal − Traverses a tree in a post-order

manner.
 Tree traversal
1. Insert − Inserts an element in a tree/create a tree.
2. Search − Searches an element in a tree.
3. Traversal
Recursive
Preorder Traversal
Inorder Traversal

Sweta Bohra
Postorder Traversal
Non-recursive
Using Stack
Preorder Traversal
Inorder Traversal
Postorder Traversal
Without using Stack
Pointer to Father
Threading
 Tree Traversal :
1. Inorder Traversal [Left-Node-Right]
In this traversal method, the left subtree is visited first, then the root and later
the right sub-tree. We should always remember that every node may
represent a subtree itself.

If a binary tree is traversed in-order, the output will produce sorted key values
in an ascending order.

Sweta Bohra
Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)
Tree Traversal :
1. Inorder Traversal [Left-Node-Right]

Sweta Bohra
D→B→E→A→F→C→G
Tree Traversal :
1. Inorder Traversal [Left-Node-Right]

Sweta Bohra
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
 Tree Traversal :
1. Inorder Traversal [Left-Node-Right]
Algorithm Recursive
Step 1: Repeat Steps 2 to 4 while TREE != NULL
Step 2: INORDER(TREE -> LEFT)
Step 3: Write TREE -> DATA
Step 4: INORDER(TREE -> RIGHT) [END OF LOOP]
Step 5: END

Sweta Bohra
C Recursive Function
void traverseInorder(struct node* root)
{
if (root == NULL)
return;
traverseInorder(root->left);
printf(" %d ", root->element);
traverseInorder(root->right);
}
 Tree Traversal :
2. Preorder Traversal [Node-Left-Right]
In this traversal method, the root node is visited first, then the left subtree
and finally the right subtree.

Algorithm Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)

Sweta Bohra
3. Traverse the right subtree, i.e., call Preorder(right-subtree)
Tree Traversal :
2. Preorder Traversal [Node-Left-Right]

Sweta Bohra
A→B→D→E→C→F→G
Tree Traversal :
2. Preorder Traversal [Node-Left-Right]

Sweta Bohra
{40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70}
 Tree Traversal :
2. Preorder Traversal [Node-Left-Right]
Algorithm Recursive
Step 1: Repeat Steps 2 to 4 while TREE != NULL
Step 2: Write TREE -> DATA
Step 3: PREORDER(TREE -> LEFT)
Step 4: PREORDER(TREE -> RIGHT)
[END OF LOOP]

Sweta Bohra
Step 5: END

C Recursive Function
void traversePreorder(struct node* root)
{
if (root == NULL)
return;
printf(" %d ", root->element);
traversePreorder(root->left);
traversePreorder(root->right);
}
 Tree Traversal :
3. Postorder Traversal (REVERSE POLISH NOTATION)
[Left-Right-Node]

In this traversal method, the root node is visited last, hence the name.
First we traverse the left subtree, then the right subtree and finally the root
node.

Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)

Sweta Bohra
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.
Tree Traversal :
3. Postorder Traversal (REVERSE POLISH NOTATION)
[Left-Right-Node]

Sweta Bohra
D→E→B→F→G→C→A
Tree Traversal :
3. Postorder Traversal (REVERSE POLISH NOTATION) [Left-
Right-Node]

Sweta Bohra
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
 Tree Traversal :
3. Postorder Traversal (REVERSE POLISH NOTATION) [Left-
Right-Node]
Algorithm Recursive
Step 1: Repeat Steps 2 to 4 while TREE != NULL
Step 2: POSTORDER(TREE -> LEFT)
Step 3: POSTORDER(TREE -> RIGHT)
Step 4: Write TREE -> DATA [END OF LOOP]

Sweta Bohra
Step 5: END

C Recursive Function
void traversePostorder(struct node* root)
{
if (root == NULL)
return;
traversePostorder(root->left);
traversePostorder(root->right);
printf(" %d ", root->element);
}
 Tree Traversal :
1. Preorder Traversal [Root-Left-Right]
Algorithm Non Recursive using STACK
Pre-order [Info,left,Right,Root]
Step 1: Begin
Step 2: Set TOP:=1, Stack[I]=null & ptr=Root.
Step 3:Repeat step 4 to 6 while ptr != null
Step 4: Apply process to Info[ptr]

Sweta Bohra
Step 5: If (Right[ptr] != null then
Top:=Top+1
Stack[Top]:=Right[ptr]
Endif
Step 6: If (left[ptr] != null) then
Ptr:=left[ptr]
Else
Ptr:=Stack[Top]
Top:=Top-1
Endif
Endloop
Step 7: END
 Tree Traversal :
2. Inorder Traversal [Left-Root-Right]
Algorithm Non Recursive using STACK
In-order [Info,left,Right,Root]
Step 1: Begin
Step 2: Set TOP:=1, Stack[I]=null & ptr=Root.
Step 3: Repeat while ptr != null
set Top:=Top+1 & Stack[Top]:=ptr
set ptr:=left[ptr]

Sweta Bohra
endloop
Step 4: Set ptr:=Stack[Top]
Top:=Top-1
Step 5: Repeat step 6 to 8 while ptr != null
Step 6: Apply process to Info[ptr]
Step 7: If (Right[ptr] != null) then
set ptr:= Right[ptr]
goto Step 3.
endif
Step 8: Set ptr := Stack[Top]
Top := Top-1
Step 9: Exit
 Tree Traversal :
3. Postorder Traversal [Left-Right-Root]
Algorithm Non Recursive using STACK
Post-order [Info,left,Right,Root]
Step 1: Begin
Step 2: Set TOP:1, Stack[I]=null ptr=Root.
Step 3: Repeat step 4 to 6 while ptr != null
Step 4: Set TOP:=TOP+1
Step 5: Stack[TOP]:= ptr
Step 6: If(Right[ptr] != null) then
Top:=Top+1

Sweta Bohra
Stack[Top]:=Right[ptr]
Endif
Step 7: Set ptr:= Left[ptr]
End Loop
Step 8: Ptr:=Stack[TOP]
Step 9: TOP:TOP-1
Step 10: Repeat while ptr>0
Apply process to Info[ptr]
TOP:=TOP-1
End loop
Step 11: If ptr < 0 then
Step 12: Set ptr:= Right[ptr]
Go to Step 3
Step12: END
 Precedence Table
Precedence Table
^ R-L
/*% L-R
+- L-R

In-order expression to Pre-order expression

A + (B * C) ^ D - E

Sweta Bohra
A + *BC ^ D - E
A + ^*BCD - E
+A^*BCD - E
-+A^*BCDE

In-order expression to Post-order expression

A + (B * C) ^ D - E
A + BC* ^ D - E
ABC*D^+ - E
ABC*D^+E-
 Generation of Tree using Pre and In Order
Precedence Table
^ R-L
/*% L-R
+- L-R

In-order expression to Pre-order expression

A + (B * C) ^ D - E

Sweta Bohra
A + *BC ^ D - E
A + ^*BCD - E
+A^*BCD - E
-+A^*BCDE

In-order expression to Post-order expression

A + (B * C) ^ D - E
A + BC* ^ D - E
ABC*D^+ - E
ABC*D^+E-
 Generation of Tree using Pre and In Order
Pre : - + A ^ * B C D E
In : A + (B * C) ^ D - E

-+A^*BCDE //- is ROOT

A + (B * C) ^ D – E //find – in In-order tree

Sweta Bohra
Generation of Tree using Pre and In Order

Sweta Bohra
Generation of Tree using Pre and In Order

Sweta Bohra
 Generation of Tree using Pre and In Order
Let us consider the below traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

Inorder Traversal : { 4, 2, 1, 7, 5, 8, 3, 6 }

Sweta Bohra
Preorder Traversal: { 1, 2, 4, 3, 5, 7, 8, 6 }

PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3

InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11
 Generation of Tree using Post and In Order
Inorder = [9,3,15,20,7]
Postorder = [9,15,7,20,3]

Sweta Bohra
 Generation of Tree using Post and In Order
Inorder Traversal : { 4, 2, 1, 7, 5, 8, 3, 6 }
Postorder Traversal : { 4, 2, 7, 8, 5, 6, 3, 1 }

Sweta Bohra
 Generation of Tree using Post and In Order
InOrder[] = {20, 30, 35, 40, 45, 50, 55, 60, 70};
PostOrder[] = {20, 35, 30, 45, 40, 55, 70, 60, 50};

Sweta Bohra
 Sweta Bohra
Tree Completed…
 Sweta Bohra
Graph
Non-Linear Structure
Graph
A Graph consists of a finite set of vertices(or nodes) and set of Edges
which connect a pair of nodes.

A graph G can be defined as an ordered set G(V, E) where V(G)

represents the set of vertices and E(G) represents the set of edges
which are used to connect these vertices.

Sweta Bohra
A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C),
(C,E), (E,D), (D,B), (D,A)) is shown in the following figure.
 Graph

Sweta Bohra
Types of graph
1. Finite graph
The graph G=(V, E) is called a finite graph if the number of
vertices and edges in the graph is limited in number.

Sweta Bohra
Types of graph
2. Infinite Graph
The graph G=(V, E) is called a finite graph if the number of
vertices and edges in the graph is interminable.

Sweta Bohra
Types of graph
3. Trivial Graph
A graph G= (V, E) is trivial if it contains only a single vertex
and no edges.

Sweta Bohra
4. Simple Graph
If each pair of nodes or vertices in a graph G=(V, E) has only
one edge, it is a simple graph. As a result, there is just one
edge linking two vertices, depicting one-to-one
interactions between two elements.
Types of graph
5. Multi Graph
If there are numerous edges between a pair of vertices in a
graph G= (V, E), the graph is referred to as a multigraph.

There are no self-loops in a Multigraph.

Sweta Bohra
Types of graph
6. Null Graph
It's a reworked version of a trivial graph. If several vertices
but no edges connect them, a graph G= (V, E) is a null
graph.

Sweta Bohra
Types of graph
7. Complete Graph
If a graph G= (V, E) is also a simple graph, it is complete.
Using the edges, with n number of vertices must be
connected.
It's also known as a full graph because each vertex's degree

Sweta Bohra
must be n-1.
Types of graph
8. Pseudo Graph
If a graph G= (V, E) contains a self-loop besides other
edges, it is a pseudograph.

Sweta Bohra
Types of graph
9. Regular Graph
If a graph G= (V, E) is a simple graph with the same degree
at each vertex, it is a regular graph. As a result, every
whole graph is a regular graph.

Sweta Bohra
Types of graph
10. Weighted Graph
A graph G= (V, E) is called a labeled or weighted graph
because each edge has a value or weight representing the
cost of traversing that edge.

Sweta Bohra
Types of graph
11. Directed Graph
A directed graph also referred to as a digraph, is a set of
nodes connected by edges, each with a direction.

Sweta Bohra
Types of graph
12. Undirected Graph
An undirected graph comprises a set of nodes and links
connecting them. The order of the two connected vertices
is irrelevant and has no direction. You can form an
undirected graph with a finite number of vertices and

Sweta Bohra
edges.
Types of graph
13. Connected Graph
If there is a path between one vertex of a graph data
structure and any other vertex, the graph is connected.

Sweta Bohra
Types of graph
14. Disconnected Graph
When there is no edge linking the vertices, you refer to the
null graph as a disconnected graph.

Sweta Bohra
Types of graph
15. Cyclic Graph
If a graph contains at least one graph cycle, it is considered
to be cyclic.

Sweta Bohra
Types of graph
16. Acyclic Graph
When there are no cycles in a graph, it is called an acyclic
graph.

Sweta Bohra
Types of graph
17. Directed Acyclic Graph
It's also known as a directed acyclic graph (DAG), and it's a
graph with directed edges but no cycle.
It represents the edges using an ordered pair of vertices
since it directs the vertices and stores some data.

Sweta Bohra
Types of graph
18. Subgraph
The vertices and edges of a graph that are subsets of
another graph are known as a subgraph.

Sweta Bohra
Terminology

Sweta Bohra
Terminology
1. Vertex
Individual data element of a graph is called as
Vertex. Vertex is also known as node. In above example
graph, A, B, C, D & E are known as vertices.

Sweta Bohra
2. Edge
An edge is a connecting link between two vertices. Edge is
also known as Arc. An edge is represented as
(startingVertex, endingVertex). For example, in above
graph the link between vertices A and B is represented as
(A,B). In above example graph, there are 7 edges (i.e.,
(A,B), (A,C), (A,D), (B,D), (B,E), (C,D), (D,E)).
Terminology
Edges are three types.

a. Undirected Edge - An undirected edge is a bidirectional

edge. If there is undirected edge between vertices A and B
then edge (A , B) is equal to edge (B , A).

Sweta Bohra
b. Directed Edge - A directed edge is a unidirectional edge. If
there is directed edge between vertices A and B then edge
(A , B) is not equal to edge (B , A).

c. Weighted Edge - A weighted edge is a edge with value

(cost) on it.
Terminology
3. Undirected Graph
A graph with only undirected edges is said to be undirected
graph.

4. Directed Graph
A graph with only directed edges is said to be directed

Sweta Bohra
graph.

5. Mixed Graph
A graph with both undirected and directed edges is said to
be mixed graph.

6. End vertices or Endpoints

The two vertices joined by edge are called end vertices (or
endpoints) of that edge.
Terminology
7. Origin
If a edge is directed, its first endpoint is said to be the origin
of it.
8. Destination
If a edge is directed, its first endpoint is said to be the origin
of it and the other endpoint is said to be the destination of

Sweta Bohra
that edge.
9. Adjacent
If there is an edge between vertices A and B then both A and
B are said to be adjacent. In other words, vertices A and B
are said to be adjacent if there is an edge between them.
10. Incident
Edge is said to be incident on a vertex if the vertex is one of
the endpoints of that edge.
Terminology
11. Degree
Total number of edges connected to a vertex is said to be
degree of that vertex.
12. Indegree
Total number of incoming edges connected to a vertex is
said to be indegree of that vertex.

Sweta Bohra
13. Outdegree
Total number of outgoing edges connected to a vertex is
said to be outdegree of that vertex.
14. Loop
A node connect to itself create a loop.
15. Cycle
Path from a node to a node itself is called a cycle.
Representation of graph
There are two ways of maintaining a graph ‘G’ in the
memory of a computer.
1. Adjacency matrix.
2. Linked representation.

1. Adjacency matrix representation

Sweta Bohra
An adjacency matrix is a square matrix used to represent a
finite graph. The elements of the matrix indicate whether
pairs of vertices are adjacent or not in the graph.
Representation of graph
1. Adjacency matrix representation
a. Undirected graph

Sweta Bohra
Representation of graph
1. Adjacency matrix representation
a. Undirected graph

Sweta Bohra
Representation of graph
1. Adjacency matrix representation
b. Directed graph

Sweta Bohra
Representation of graph
1. Adjacency matrix representation
b. Undirected Weighted graph

Sweta Bohra
Representation of graph
1. Adjacency matrix representation
b. Undirected Weighted graph

Sweta Bohra
Representation of graph
1. Adjacency list representation
a. Undirected graph

Sweta Bohra
Representation of graph
1. Adjacency list representation
b. Directed graph

Sweta Bohra
Traversing a graph
There are two standard way of traversing a graph :
Breadth First Search (BFS).
Depth First Search (DFS).

Breadth First Search : The general idea behind the breadth first search is
beginning at the starting node ‘A’. First we examine all the neighbors of ‘A’, then
we examine all the neighbors of ‘A’s neighbors and we need to guarantee that

Sweta Bohra
no node is processed more than one’s.
This is processed by Queue & by using field Status.

Status = 1 [Ready State]

Status = 2 [Waiting State]
Status = 3 [Processed State]
Traversing a graph
The algorithm works as follows:

1. Change the status of every node to its ready state [Status=1].

2. Put the Stating node ‘A’ in the Queue & change its states to Waiting State
[Status = 2]
3. Repeat Step 4 & 5 until Queue is not empty.
4. Remove the front node N of the Queue; Processed it; Change its status to

Sweta Bohra
processed state [Status = 3].
5. Add to the rear of the Queue and change its status to Status=1 to Status=2.
[End of Loop]
6. Exit.
Traversing a graph
Depth First Search : The general idea behind the depth first search is beginning
at the starting node ‘A’. First we examine all the neighbors to depth of ‘A’, then
we examine all the neighbors of ‘A’s neighbors and we need to guarantee that
no node is processed more than one’s.
This is processed by Stack & by using field Status.

Status = 1 [Ready State]

Status = 2 [Waiting State]
Status = 3 [Processed State]

Sweta Bohra
The algorithm works as follows:

Initialize all nodes to the ready state [Status=1].

Push the Stating node ‘A’ onto the Stack & change its states to Waiting State
[Status = 2].
Repeat Step 4 & 5 until Stack is not empty.
Pop the node ‘N’ of Stack; Processed it; Change its status to processed state
[Status = 3].
Push onto the Stack the neighbors of N that are still in ready state and change
its status to Status=1 to Status=2.
[End of Loop]
Exit.
 Sweta Bohra
Graph Completed…