IFT312

Introduction to Data Structures and Algorithms (DSA)

CA1:110325 CA2: 150425

1.0 Data Structures and Algorithm (DSA)

DSA are two important aspects of any programming language. Every programming language has
its own data structures and different algorithms to handle the data structures.

Data structures are used to organize and store data to use in an effective way when performing
data operations.

Algorithm is a step by step procedure which defines a set of instructions to be executed in a

certain order to get the desired output. Algorithms are generally independent of underlying
programming languages.

1.1 Why Learn DSA

Applications are getting complex and increasing data, hence applications face the following three
problems:

Data search: Searching through a heap of data for every request for data, e.g. an inventory app
of 1 million items has to search 106 items every time, thereby slowing down the search.

Processor Speed: The processor speed does not catch up with the rate of growth of data. The
processor speed is limited, whereas the data continues to grow.

Multiple requests: As many user requests are entertained simultaneously, servers could fail the
requests of multiple users while searching for data.

DSA has come to solve these problems, whereby data are organized in such a way that all data
items may not be searched to get a desired data.

TQ1: Why is it necessary to study DSA?

1.2 What is Data Structure?

Data structure is a systematic way to organize data in order to use it efficiently.

Types of data structures:

The following are the different data structures type:

1. Array Data structure

2. String data structure
3. Linked list
4. Double-linked list
5. Circular-linked list
6. Stack DS
7. Queue DS
8. Heap DS
9. Hash DS
10. Matrix/Grid DS
11. Graph DS, and
12. Tree DS

TQ 2: Group the above data structures into Static and Dynamic storage system; then group
according to Linear and non-linear.

1.3 Algorithms:
We are going to study the following Algorithms:
1. Searching Algorithms
2. Sorting Algorithms
3. Approximation Algorithms
4. Divide and Conquer Algorithms
5. Greedy Algorithms
6. Recursion Algorithms
7. Backtracking Algorithms
8. Randomized Algorithms

1.4 Characteristics of an Algorithm

Unambiguous: An algorithms should be clear and unambiguous, each of the steps, together with
the input(s) should lead to a clear output.

Input: An algorithm should have zero or more well-defined inputs.

Output: An algorithm should have 1 or more well-defined outputs

Finiteness: An algorithm must terminate after a finite number of steps.

Feasibility: An algorithm should be feasible or amenable to desk-check

Independent: An algoriyhm should be independent of any programming language.

1.5 How to write an Algorithm:

Write an algorithm to add two numbers

Step1: START
Step2: declare three variables, a, b and c
Step3: Assign values to variables a and b
Step4: Add the content of variables and b
Step5: Store the output of step 4 into variable c
Step6 : Print the content of variable c
Step7: STOP

An Analyst writes the algorithm and the programmer writes the code. Note that a problem can be
solved in more than one ways, hence many algorithms can be derived for a given problem.

1.6 Algorithm Analysis

The efficiency of an algorithm can be analyzed at two different stages, i.e. before
implementation and after implementation as follows:

a. A Priori Analysis: this is the analysis of an algorithm where its efficiency is measured
based on the assumption that the processor speed is constant and it has no effect on the
implementation.
b. A Posterior Analysis: this is the analysis of an algorithm using a selected programming
language on a target computer considering the running time and the space consumption
of the implementation.
Built-in Data Type
Those data types for which a language has built-in
support are known as Built-in Data
types. For example, most of the languages provide
the following built-in data types.

Derived Data Type

Those data types which are implementation independent as they can be implemented in
one or the other way are known as derived data types. These data types are normally
built by the combination of primary or built-in data types and associated operations on
them. For example:
There are
generally two
types of Data
Structures:
Linear and
Non-Linear Data Structures.

2.1 Static Linear Data Structures

In Static Linear Data Structures, the memory allocation is not scalable. Once the entire memory
is used, no more space can be retrieved to store more data. Hence, the memory is required to be
reserved based on the size of the program. This will also act as a drawback since reserving more
memory than required can cause a wastage of memory blocks. The best example for static linear
data structures is an array.

Dynamic Linear Data Structures

In Dynamic linear data structures, the memory allocation can be done dynamically when

required.
These data
structures
are efficient
considering
the space
complexity
of the program. Few examples of dynamic linear data structures include: linked lists, stacks and
queues.

Non-Linear Data Structures

Non-Linear data structures store the data in the form of a hierarchy. Therefore, in contrast to the
linear data structures, the data can be found in
multiple levels and are difficult to
traverse through.

However, they are designed to overcome the issues and limitations of linear data structures. For
instance, the main disadvantage of linear data structures is the memory allocation. Since the data
is allocated sequentially in linear data structures, each element in these data structures uses one
whole memory block. However, if the data uses less memory than the assigned block can hold,
the extra memory space in the block is wasted. Therefore, non-linear data structures are
introduced. They decrease the space complexity
and use the memory optimally.

Few types of non-linear data structures are -

2.2 Array Data Structure

An array is a linear data structure that is defined as a collection of elements with same data types.
They exist in both single dimension and multiple dimensions. These data structures come into
picture when there is a necessity to store multiple elements of similar nature together at one
place.

Figure 1: A Simple Array Data Structure

The difference between an array index and a memory address is that the array index acts like a
key value to label the elements in the array. However, a memory address is the starting address of
free memory available.

Array Data Structure Terms

Element - Each item stored in an array is called an element.

Index - Each location of an element in an array has a numerical index, which is
used to identify the element.

How to Create an Array

To create an array in C language :

data_type ArrayName[size] e.g.
data_type IFT[5], or data_type IFT[5,3] { for a two dimension array}

In BASIC: DIM IFT[5] or DIM IFT[5,3]

IFT 2-Dimensional Array

(1,1) (1,2) (1,3)
(2,1) (2,2) (2,3)
(3,1)
(4,1)
(5,1) (5,3)
Figure 2: A 2-dimensional Array

Arrays are used as solutions to many problems from the small sorting problems to more complex
problems like travelling salesperson problem. An array has a random access lookup time, that is,
accessing the 1st index of the array and the 1000th index of the array will both take the same
time. This is due to the fact that array comes with a pointer and an offset value.

The pointer points to the right location of the memory and the offset value shows how far to look
in the said memory.

Array Representation
Arrays are represented as a collection of buckets where each bucket stores one element. These
buckets are indexed from '0' to 'n-1', where n is the size of the array. For example, an array with
size 10 will have buckets indexed from 0 to 9.

This indexing will be similar for the multidimensional arrays as well. If it is a 2-dimensional
array, it will have sub-buckets in each bucket. Then it will be indexed as array_name[r,c], where
m and n are the sizes of each level in the array in a row and column (r,c) manner. See the IFT
matrix above.
Figure 3: A Single Dimension Array

Important points to note here about Fig. 3:

 An array Index starts with 0.
 Array length is the size of the array. In Fig.3, it is 9 which means it can store 9 elements.
 Each array element can be accessed via its index. For example, we can fetch an
element at index 6 as 23.

TQ. 3: a. Write out Six important points about an array data structure.
b. Is an array static or a dynamic data structure?

Basic Operations in Arrays

The basic operations in the Arrays are insertion, deletion, searching, display, traverse,
and update. These operations are usually performed to either modify the data in the
array or to report the status of the array.

The basic operations supported by an array are:

 Traverse – Visit all the array elements one by one.
 Insertion - Adds an element at a given index.
 Deletion - Deletes an element at a given index.
 Search - Searches an element using the given index or by the value.
 Update - Updates an element at the given index.
 Display - Displays the contents of the array

2.3 Linked List Data Structure

A linked list is a linear data structure which can store a collection of "nodes" connected together
via links i.e. pointers. Linked lists nodes are not stored at a contiguous location, rather they are
linked using pointers to the different memory locations. A node consists of the data value and a
pointer to the address of the next node within the linked list.

A linked list is a dynamic linear data structure whose memory size can be allocated or de-
allocated at run time based on the operation insertion or deletion, this helps in using system
memory efficiently. Linked lists can be used to implement various other data structures like a
stack, queue, graph, hash maps, etc.

A linked list starts with a head node which points to the first node. Every node consists
of data which holds the actual data (value) associated with the node and a next pointer
which holds the memory address of the next node in the linked list. The last node is
called the tail node in the list which points to null indicating the end of the list.
2.3.1 Differences Between an Array and a Linked-List
In case of arrays, the size is given at the time of creation and so arrays are of fixed length (Static
data structure); whereas Linked lists are dynamic in size and any number of nodes can be added
in the linked lists dynamically. An array can accommodate similar types of data types whereas
linked lists can store various nodes of different data types.

TQ 4: What are the differences between Array and Linked List data structures?

2.3.2 Types of Linked List

The various types of linked lists are:
1. Singly Linked Lists
2. Doubly Linked Lists, and
3. Circular Linked Lists

2.3.2.1 Singly Linked Lists

Singly linked lists contain two "buckets" in one node; one bucket holds the data and the other
bucket holds the address of the next node of the list. Traversals can be done in one direction only
as there is only a single link between two nodes of the same list.

2.3.2.2 Doubly Linked Lists

Doubly Linked Lists contain three "buckets" in one node; one bucket holds the data and
the other buckets hold the addresses of the previous and next nodes in the list. Doubly Linked
List can be navigated in both forward as well as backward ways. Following are the important
terms to understand the concept of doubly linked list. The list is traversed twice as the nodes in
the list are connected to each other from both sides.

2.3.2.3 Circular Linked Lists

Circular linked lists can exist in both singly linked list and doubly linked list. Since the last node
and the first node of the circular linked list are connected, the traversal in this linked list will go
on forever until it is broken.
2.4 Basic Operations in Linked List
The basic operations in the linked lists are:

 Insertion - Adds an element at the beginning of the list;

 Deletion - Deletes an element at the beginning of the list;
 Display - Displays the complete list. Stacks;
 Search - Searches an element using the given key; and
 Delete - Deletes an element using the given key.

2.4.1 Linked List - Insertion Operation

Adding a new node in linked list is a more than one step activity. A new node could be added at
the beginning, in the middle and at the end. First, create a node using the same structure and find
the location where it has to be inserted as shown in Fig. 1.

Assume that we are inserting a node B (NewNode), between A (LeftNode) and C

(RightNode). Then point B.next to C as shown in Fig. 2

Figure 1: Linked List Insertion

Now, the next node at the left should point to the new node, as in Fig. 3

Figure 2: Linked list Change of pointers

Linked List Algorithm
Adding an element at the beginning of the list

1. START
2. Create a node to store the data
3. Check if the list is empty
4. If the list is empty, add the data to the node and assign the head pointer to it.
Figure 3: Linked list Insertion final step
5. If the list is not empty, add the data to a node and link to the current head. Assign the head to
the newly added node.
6. END

Adding an element at the ending of the list

1. START
2. Create a new node and assign the data

3. Find the last node

4. Point the last node to new node
5. END

Adding an element at any position within the list

1. START
2. Create a new node and assign data to it
3. Iterate until the node at position is found
4. Point first to new first node
5. END
Linked List - Deletion Operation
Deletion is also a more than one step process. First, locate the target node to be removed, by
using searching algorithms.

The left (previous) node of the target node now should point to the next node of the target node.

This will remove the link that was pointing to the target node. Now, using the following code, we
will remove what the target node is pointing at.
Figure 4:Deleting a node

We need to use the deleted node. We can keep that in memory otherwise we can
simply deallocate memory and wipe off the target node completely.

Similar steps should be taken if the node is being inserted at the beginning of the list.

While inserting it at the end, the second last node of the list should point to the new node and the

Figure 5 Deleting a node. Changing the pointers

new node will point to NULL. Deletion in linked lists is also performed in three different ways
as follows -

Deletion at Beginning
In this deletion operation of the linked, we are deleting an element from the beginning of the list.

For this, we point the head to the second node.

Algorithm
1. START
2. Assign the head pointer to the next node in the list
3. END

Deletion at Ending
In this deletion operation of the linked, we are deleting an element from the ending of the list.

Algorithm
1. START
2. Iterate until you find the second last element in the list.
3. Assign NULL to the second last element in the list.
4. END

Deletion at a Given Position

In this deletion operation of the linked list, we are deleting an element at any position of
the list.

Algorithm
1. START
2. Iterate until find the current node at position in the list.
3. Assign the adjacent node of current node in the list
Figure 6: Deletion at a given node
to its previous node.

4. END

3.0 Stack Data Structure

A stack is a linear data structure where elements are stored in the LIFO (Last In First Out)
principle where the last element inserted would be the first element to be deleted. A stack is an
Abstract Data Type (ADT), that is popularly used in most programming languages. It is named
stack because it has the similar operations as the real-world stacks, for example - a pack of cards
or a pile of plates, etc.

Stack is considered a complex data structure because it uses other data structures for
implementation, such as Arrays, Linked lists, etc.
Stack Representation
A stack allows all data operations at one end only. At any given time, we can only access
the top element of a stack.
The following diagram depicts a stack and its operations

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can
either be a fixed size one or it may have a sense of dynamic resizing.

2.5.1 Basic Operations on Stacks

Figure 8: Stack implemetation

Stack operations are usually performed for initialization, usage and, de-initialization of the stack
abstract data type (ADT). The most fundamental operations in the stack ADT include: push(),
pop(), peek(), isFull(), isEmpty(). These are all built-in operations to carry out data
manipulation and to check the status of the stack in a typical programming language.

Stack uses pointers that always point to the topmost element within the stack, hence
called the top pointer.
Stack Insertion: push()
The push() is an operation that inserts elements into the stack. The following is an
algorithm that describes the push() operation in a simpler way
Algorithm
1. Checks if the stack is full.
2. If the stack is full, produces an error and exit.
3. If the stack is not full, increments top to point next
empty space.
4. Adds data element to the stack location, where top
is pointing.
5. Returns success.

Stack Deletion: pop()

The pop() is a data manipulation operation which removes elements from the stack. The
following algorithm describes the pop() operation in a simpler way.

Algorithm
1. Checks if the stack is empty.
2. If the stack is empty, produces an error and exit.
3. If the stack is not empty, accesses the data element at
which top is pointing.
4. Decreases the value of top by 1.
5. Returns success.

Retrieving topmost Element from Stack: peek()

The peek() is an operation retrieves the topmost element within the stack, without deleting it.
This operation is used to check the status of the stack with the help of the top pointer.

Algorithm
1. START
2. return the element at the top of the stack
3. END

Verifying whether the Stack is full: isFull()

The isFull() operation checks whether the stack is full. This operation is used to check the status
of the stack with the help of top pointer.

Algorithm
1. START
2. If the size of the stack is equal to the top position of the stack,
the stack is full. Return 1.
3. Otherwise, return 0.
4. END

Verifying whether the Stack is empty: isEmpty()

The isEmpty() operation verifies whether the stack is empty. This operation is used to check the
status of the stack with the help of top pointer.

Algorithm
1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END

4.0 Queue Data Structure

A queue is a linear data structure where elements are stored in the FIFO (First In First Out)
principle where the first element inserted would be the first element to be accessed. A queue is an
Abstract Data Type (ADT) similar to stack, the thing that makes queue different from stack is
that a queue is open at both its ends. The data is inserted into the queue through one end and
deleted from it using the other end. Queue is very frequently used in most programming
languages.

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first,
exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops.

Representation of Queues
Similar to the stack Abstract Data Type (ADT), a queue ADT can also be implemented using
arrays, linked lists, or pointers. For better understanding, let us implement queues using a one-
Figure 9: A Queue
dimensional array.

Basic Operations in Queue

Queue operations include initialization of a queue, usage and permanently deleting
the data from the memory.

The most fundamental operations in the queue ADT include: enqueue(), dequeue(), peek(),
isFull(), isEmpty(). These are all built-in operations (in an object-oriented programming

language) to carry out data manipulation and to check the status of the queue.

Queue uses two pointers - front and rear. The front pointer accesses the data from the
front end (helping in enqueueing) while the rear pointer accesses data from the rear end
(helping in dequeuing).

Queue Insertion Operation: Enqueue()

The enqueue() is a data manipulation operation that is used to insert elements into the stack. The
following algorithm describes the enqueue() operation in a simpler way.
Algorithm
1. START
2. Check if the queue is full.
3. If the queue is full, produce overflow error and exit.
4. If the queue is not full, increment rear pointer to point
the next empty space.
5. Add data element to the queue location, where the rear
is pointing.
6. return success.
7. END

Queue Deletion Operation: dequeue()

The dequeue() is a data manipulation operation that is used to remove elements from the queue.
The following algorithm describes the dequeue() operation in a simpler way

Algorithm
1. START
2. Check if the queue is empty.
3. If the queue is empty, produce underflow error and exit.
4. If the queue is not empty, access the data where front
is pointing.
5. Increment front pointer to point to the next available
data element.

Queue - The peek() Operation

The peek() is an operation which is used to retrieve the frontmost element in the queue,
without deleting it. This operation is used to check the status of the queue with the help
of the pointer.

Algorithm
1. START
2. Return the element at the front of the queue
3. END

Queue - The isFull() Operation

The isFull() operation verifies whether the stack is full.

Algorithm
1. START
2. If the count of queue elements equals the queue size,
return true
3. Otherwise, return false
4. END

Queue - The isEmpty() operation

The isEmpty() operation verifies whether the stack is empty. This operation is used to check the
status of the stack with the help of top pointer.

Algorithm
1. START
2. If the count of queue elements equals zero, return true
3. Otherwise, return false
4. END

5. Heap Data structure

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 key(α) ≥ key(β).
As the value of parent is greater than that of child, this property generates Max Heap.

Therefore, a heap can be of two types: Min-heap and max-Heap. For example, suppose we have
the following sequence of data: 35 33 42 10 14 19 27 44 26 31

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.
The trees are constructed using the input and order of arrival.

Figure 10: Min Heap data Structure

Figure 11: Max Heap Data Structure

Algorithm for a max heap

Step 1 – START
Step 2 - Create a new node at the end of heap, if heap not
empty, else create the first node

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 2 & 4 until the number sequence is
exhausted.

6. Hash Table Data structure

Hash Table is a data structure which stores data in an associative manner. In a hash table, data is
stored in an array format, where each data value has its own unique index value. Access of data
becomes very fast if we know the index of the desired data.

Hash Table uses an array as a storage medium and uses hash technique to generate an index
where an element is to be inserted or is to be located from.

Hashing
Hashing is a technique to convert a range of key values into a range of indexes of an array. We're
going to use modulo operator to get a range of key values. Consider an example of hash table of
size 20, and the following items are to be stored. Item are in the (key,value) format.

For example, given the following (key, value) pairs of number sequence:

(1,20), (2,70), (42,80), (4,25), (12,44), (14,32), (17,11), (13,78), (37,98).

To compute the array index with modulo 20 (or %20), we have:

Figure 12: Hash function

S. Key Hash Function Array

No. (Mod20) index
1 1 1 % 20 = 1 1
2 2 2 % 20 = 2 2
3 42 42 % 20 = 2 2
4 4 4 % 20 = 4 4
5 12 12 % 20 = 12 12
6 14 14 % 20 = 14 14
7 17 17 % 20 = 17 17
8 13 13 % 20 = 13 13
9 37 17 % 20 = 17 17

Linear Probing
Note that, the hashing technique generated an already used array index of the array. In such a
case, the next available location in the array is used searched and used, this technique is called
linear probing. Our array index table now becomes:

S. Key Hash Function Array index, after

No. (Mod20) Linear probing
1 1 1 % 20 = 1 1
2 2 2 % 20 = 2 2
3 42 42 % 20 = 2 3
4 4 4 % 20 = 4 4
5 12 12 % 20 = 12 12
6 14 14 % 20 = 14 14
7 17 17 % 20 = 17 17
8 13 13 % 20 = 13 13
9 37 17 % 20 = 17 18

Basic Operations:
The following operations can be performed on a hash table:

Search - Searches an element in a hash table.

Insert - Inserts an element in a hash table.
Delete - Deletes an element from a hash table.

To implement a hash table, define or create a pair of data item and a key value; then specify a
hashing function (e.g. modulo or any other arithmetic computation) to compute the array index.

Search Operation
Whenever an element is to be searched, compute the hash code of the key given and locate the
element using that hash code as index in the array. Use linear probing to get the element ahead if
the element is not found at the computed hash code.

Insert Operation
Whenever an element is to be inserted, compute the hash code of the key passed and locate the
index using that hash code as an index in the array. Use linear probing for empty location, if an
element is found at the computed hash code.

Delete Operation
Whenever an element is to be deleted, compute the hash code of the key passed and locate the
index using that hash code as an index in the array. Use linear probing to get the element ahead if
an element is not found at the computed hash code. When found, store a dummy item there to
keep the performance of the hash table intact.
7. Graph Data Structure

A graph data structure consists of a set of objects that are connected to each other via links. The

interconnected objects are represented by points termed as vertices, and the links that connect
the vertices are called edges.
Figure 13:A Graph Data Structure
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges,
connecting the pairs of vertices. Take a look at the following graph

In the above graph,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

Graph Data Structure

Mathematical graphs can be represented in data structure. We can represent a graph using an
array of vertices and a two-dimensional array of edges. Now, let's define some important terms.

Vertex - Each node of the graph is represented as a vertex. In the following example, the labeled
circle represents vertices. Thus, A to G are vertices. We can represent them using an array as
shown in the following image. Here A can be identified by index 0. B can be identified using
index 1 and so on.

Edge - Edge represents a path between two vertices or a line between two vertices. In the
following example, the lines from A to B, B to C, and so on represents edges. We can use a two-
dimensional array to represent an array as shown in the following image. Here AB can be
represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other
combinations as 0.

Adjacency - Two node or vertices are adjacent if they are connected to each other through an
edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.

Path - Path represents a sequence of edges between the two vertices. In the following example,
ABCD represents a path from A to D.
Operations of Graphs
The primary operations of a graph include creating a graph with vertices and edges, and
displaying the said graph. However, one of the most common and popular operation performed
using graphs are Traversal, i.e. visiting every vertex of the graph in a specific order.

There are two types of traversals in Graphs:

i. Depth First Search Traversal, and

ii. Breadth First Search Traversal

Depth First Search Traversal (DFS)

Depth First Search is a traversal algorithm that visits all the vertices of a graph in the decreasing
order of its depth. In this algorithm, an arbitrary node is chosen as the starting point and the
graph is traversed back and forth by marking unvisited adjacent nodes until all the vertices are
marked.

The DFS traversal uses the stack data structure to keep track of the unvisited nodes.

Breadth First Search Traversal

Breadth First Search is a traversal algorithm that visits all the vertices of a graph present at one
level of the depth before moving to the next level of depth. In this algorithm, an arbitrary node is
chosen as the starting point and the graph is traversed by visiting the adjacent vertices on the
same depth level and marking them until there is no vertex left.

The DFS traversal uses the queue data structure to keep track of the unvisited nodes.

Representation of Graphs
While representing graphs, we must carefully depict the elements (vertices and edges) present in
the graph and the relationship between them. Pictorially, a graph is represented with a finite set
of nodes and connecting links between them. However, we can also represent the graph in other
most commonly used ways, like

Adjacency Matrix
Adjacency List

Adjacency Matrix
The Adjacency Matrix is a V x V matrix
where the values are filled with either 0 or 1. If
the link exists between Vi and Vj, it is
recorded 1; otherwise, 0. For the given graph
below, let us construct an adjacency matrix
Figure 14: Adjacency Matrix

Types of graph
There are two basic types of graph : Directed and Undirected Graphs

Figure 15: Adjacency List

Directed graph, consists of edges that possess a direction that goes either away from a vertex or
towards the vertex. Undirected graphs have edges that are not directed at all.
Figure 16: A Directed Graph
8. Tree Data Structure
A tree is a non-linear abstract data type with a hierarchy-based structure. It consists of
nodes (where the data is stored) that are connected via links. The tree data structure stems

Figure 17: An Undirected Graph

from a single node called a root node and has subtrees connected to the root.

Tree Data Structure Terms

Path - Path refers to the sequence of nodes along the edges of a tree.

Root - The node at the top of the tree is called root. There is only one root per tree and one path
from the root node to any node.

Parent - Any node except the root node has one edge upward to a node called parent.

Figure 18:A Tree Data Structure

Child - The node below a given node connected by its edge downward is called its child node.

Leaf - The node which does not have any child node is called the leaf node.

Subtree - Subtree represents the descendants of a node.

Visiting - Visiting refers to checking the value of a node when control is on the node.

Traversing - Traversing means passing through nodes in a specific order.

Levels - Level of a node represents the generation of a node. If the root

node is at level 0, then its next child node is at level 1, its grandchild is at
level 2, and so on.

Keys - Key represents a value of a node based on which a search operation

is to be carried out for a node.

Binary Trees
Binary Trees are general trees in which the root node can only hold up to maximum 2 subtrees:
left subtree and right subtree. Based on the number of children, binary trees are divided into three
types.

Binary Search Trees

Binary Search Trees possess all the properties of Binary Trees including some extra properties of
their own, based on some constraints, making them more efficient than binary trees.

The data in the Binary Search Trees (BST) is always stored in such a way that the values in the
left subtree are always less than the values in the root node and the values in the right subtree are
always greater than the values in the root node, i.e. left subtree < root node right subtree.

Tree Traversal
Traversal is a process to visit all the nodes of a tree. Since all nodes are connected via edges
(links) we always start from the root (head) node. Tress are traversed in three ways.

i. In-order Traversal
ii. Pre-order Traversal
iii.

Post-order Traversal
In-order Traversal
In this traversal method, the left subtree is visited first, then the root and later the right sub-tree
(L,Rt,R). 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.

We start from A, and following in-order traversal, we move to its left subtree B.B is also
traversed in-order. The process goes on until all the nodes are visited. The output of inorder
traversal of this tree will be - D B Figure
E A F19:CInorder
G Traversal
Pre-order Traversal
The root node is visited first, then the left subtree and finally the right subtree (R t, L,R).
We start from A, and following pre-order traversal,
we first visit A itself and then move
to its left subtree B. B is also traversed pre-order. The
process goes on until all the
nodes are visited. The output of pre-order traversal of
this tree will be -
A→B→D→E→C →F→G

Figure 20: Pre-order Traversal

Post-order Traversal
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 (L,R,Rt).
We start from A, and following pre-order traversal, we first visit the left subtree B. B is also
traversed post-order. The process goes on until all the nodes are visited. The output of post-order
traversal of this tree will be: D → E → B → F → G → C → A
Expression Parsing
An expression is any word or group of words or symbols that generates a value on evaluation.
Parsing expression means analyzing the expression for its words or symbols depending on a
particular criterion. Expression parsing is a term used in a programming language to evaluate
arithmetic and logical expressions.

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
Figure 21: Post-order Traversal
an expression. These notations are – Infix Notation, Prefix (Polish) Notation, and Postfix
(Reverse-Polish) Notation.
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.

S. No Infix Notation Prefix Notation Postfix

(a + b) ∗ c ∗+abc ab+c∗
1 a+b +ab ab+

a ∗ (b + c) ∗a+bc abc+∗
2
9. 3 Matrix Data

(a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗
4 a/b+c/d +/ab/cd ab/cd/+ Structure

((a + b) ∗ c) - d -∗+abcd ab+c∗d-

A matrix is a 5 two-
dimensional 6 data structure,
where we can store data in
rows and columns format. In data structures, a matrix is a two-dimensional array of elements,
with the same data type. All values in a matrix must have the same data type. The matrix can
have a fixed number of rows and columns, or it can be dynamically allocated based on the
requirement.

Matrices can be used in various applications, such as image processing, data analysis, and
machine learning.

If the matrix has m rows and n columns, there are m n elements. The matrix is represented by
uppercase letters (in this case, "A"), and the elements in the matrix are represented by lowercase
letters and two subscripts that represent the positions of the elements in the same order, e.g. a m,n
Types of Matrices in Data Structure
There are many types of matrices, which are basically categorized based on element values,
order, number of rows and columns, and so on. There are different types of matrices in linear
algebra. All types of matrices are distinguished based on their elements, order, and specific
conditions.
Special types of matrices are square, diagonal, identity, translocations, and symmetric matrices.
This is a square matrix with the same number of rows and columns.
Row Matrix: If a matrix has only one row, it is called a row matrix. 1 2 3 4

Column Matrix: If a matrix has only one column, it is called a column matrix.
1
2
3
4

Square Matrix: If the number of rows and columns in a matrix is the same, e.g. 2x2 , 3x3, etc.
4 5 8
2 7 0
6 9 1

Identity Matrix : If the diagonal elements of a square matrix are 1 and all other elements are 0.
1 0 0
0 1 0
0 0 1

Other forms of matrices can also be defined such as Triangular Matrix diagonal, symmetric and
scalar.
Operations on Matrices
Traversal - Traversing a matrix means visiting each element in the matrix exactly once. This
can be done using nested loops to iterate over each row and column in the matrix.

Search - Searching for an element in a matrix involves finding the position of a specific element
in the matrix. This can be done by traversing the matrix and comparing each element with the
target element.
The traversal and search of elements in matrix can be carried out in row-order (i.e. iterating row
first) or column order (i.e. iterating column first).

Application of Matrices
Image processing -
Matrices are used for images. let's say we have an image of 100x100 pixels, then the image can
be represented as a 100x100 matrix where each element represents the color of a pixel. Matrices
can be used to perform operations such as scaling, rotation, and filtering on images.
Data analysis -
It is also used for data analysis. Imagine we have a data set with multiple features, then the data
set can be represented as a matrix where each row represents a data point and each column
represents a feature. E.g. Name, Matric No,, Course, Grade, etc.
Other application areas of matrices are in scientific computing of mathematical numerical
analysis such as integration, differentiation, computer graphics (for representing 3-D images) and
machine learning.
Garbage collection
The automatic process of making space in computer’s memory by removing data that is no
longer required or in use.
T.Qx: Discuss any five types of Garbage collection.
Storage management