Unit – 1 Introduction to Data Structure

[Link] is Data Structure?

Data structures are used to store data in a computer in an organized form. In C Programming
Language Different types of data structures are; Array, Stack, Queue, Linked List, Tree. In
simple terms, data structure can be defined as a representation of data along with its
associated operations.
[Link] need and characteristics of data structure.
Need of DS:
1. It allows to manage large amount of data such as large databases and indexing services
such as hash table.
2. Data structures can be used to organize the storage and retrieval of information stored in
both main memory and secondary memory.
Characteristics of DS:
1. It depicts the logical representation of data in computer memory.
2. It represents the logical relationship between the various data elements.
3. It helps in efficient manipulation of stored data elements.
4. It allows the program to process the data in an efficient manner.
3. Define Abstract data type.

The abstract datatype is special kind of datatype, whose behaviour is defined by a set of
values and set of operations. The keyword “Abstract” is used as we can use these datatypes
and we can perform different operations. But how those operations are working that is totally
hidden from the user. The ADT is made of with primitive datatypes, but operation logics are
hidden. Some examples of ADT are Stack, Queue, List etc.
[Link] Primitive and Non-Primitive types of data structure.
1. PRIMITIVE DATASTRUCTURE the primitive data structures are the basic data types
that are available in most of the programming languages. The primitive data structures are
used to represent single values. Example: Integer, character, string, Boolean.
2. NON-PRIMITIVE DATASTRUCTURE The data structure that are derived from
primary data structure is known as non-Primitive data structure. These data types are used to
store group of values. Example: Arrays, Structure, Union, linked list, Stacks, Queue etc.
5. Differentiate between linear and non-linear data structure.

[Link] the operations that can be performed on data structure.

1. Inserting
2. Deleting
3. Sorting
4. Searching
5. Traversing
6. Merging
7. Copying
8. Concatenation

7. Give classification of data structure.

8. Explain time and space complexity with an example.

Time Complexity

Time complexity measures how the runtime of an algorithm increases with the size of the
input (n). It gives an estimate of how efficient an algorithm is.

Example: Printing elements of an array.

#include <stdio.h>
void main() {
int arr[] = {1, 2, 3, 4, 5};
int n = 5;
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
}
• Analysis:
o The for loop runs n times, so the time complexity is O(n).

Space Complexity

Space complexity measures the total memory required by an algorithm as a function of the
input size (n).
It includes:
1. Auxiliary space: Temporary or extra space used during execution.
2. Input space: Memory occupied by the input.

Example: Reversing an array.

#include <stdio.h>
void main() {
int arr[] = {1, 2, 3, 4, 5};
int n = 5;
int temp;
for (int i = 0; i < n / 2; i++) {
temp = arr[i];
arr[i] = arr[n - i - 1];
arr[n - i - 1] = temp;
}
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
}
• Analysis:
o The input array arr takes O(n) space.
o The variable temp takes O(1) auxiliary space.
o Total space complexity is O(n).
 Unit – 2 Searching and Sorting
1. State the following terms:
(i) searching
(ii) sorting

(i)Searching: The process of finding the desired information from the set of items stored in
the form of elements in the computer memory is referred to as 'searching in data structure.'
(ii)Sorting: Sorting is the processing of arranging the data in ascending and descending order.
[Link] Linear Search with example.
Linear search is also called as sequential search. Linear search is the easiest search technique
in which each element is scanned in a sequential manner to locate the desire element. Linear
search is a method for finding a particular value in a list. In this searching technique you need
to check every element one by one until desired element found.
Example of linear search:
Array = [3 21 11 19 91 4 80], Key element to search = 91

[Link] algorithm for Linear search.

Step 1: Start
Step 2: Accept n values from user i.e. array elements.
Step 3: Accept element to be searched from user i.e. target.
Step 4: Set i=0, flag=0
Step 5: Compare A[i] with target If(A[i] is a target)
Step 6: Set flag=1 go to step 7 Else Move to next data element i= i+1;
Step 7: If (i<=n) go to step 5
Step 8: If(flag=1) then Return i as position of target located Else Report as target not found.
Step 9: Stop
[Link] Binary Search with example.
Binary search is the search technique which works efficiently on the sorted lists. Hence, in
order to search an element into some list by using binary search technique, we must ensure
that the list is sorted.
Binary search follows divide and conquer approach in which, the list is divided into two
halves and the item is compared with the middle element of the list. If the match is found
then, the location of middle element is returned otherwise, we search into either of the halves
depending upon the result produced through the match.
Example of binary search:
Array = [2 4 7 9 10 11 15 20 46 72], Key element to search = 15

[Link] algorithm for binary search.

Step 1: Start
Step 2: Set i = 0, j = size, k = 0
Step 3: Repeat Steps 4-9 while i <= j
Step 4: Set k = (i + j)/2
Step 5: If arr[k] = num goto Step 6 else goto Step 7
Step 6: return k and goto Step 11
Step 7: If array[k] < num goto Step 8 else goto Step 9
Step 8: i = k + 1
Step 9: j = k - 1
Step 10: Return NULL and goto Step 11
Step 11: Stop
6. Explain bubble sort with example.
Bubble sort is one of the oldest and simplest of sorting techniques. In Bubble sort each
element of the array is compared with its adjacent element. It focuses on bringing the largest
element to the end of the list with each successive pass. The algorithm processes the list in
passes. A list with n elements requires n-1 passes for sorting.
Consider an array A of n elements whose elements are to be sorted by using Bubble sort. The
algorithm processes like following. In Pass 1, A[0] is compared with A[1], A[1] is compared
with A[2], A[2] is compared with A[3] and so on. At the end of pass 1, the largest element of
the list is placed at the highest index of the list.
Example of bubble sort: Array [18 3 2 33 21]

[Link] algorithm for bubble sort.

Step 1: Start
Step 2: Set i = size, j = 0 and temp = 0
Step 3: Repeat Steps 4-9 while i > 1
Step 4: Set j = 0
Step 5: Repeat Steps 6-8 while j < i-1
Step 6: if arr[j] > arr[j+1] goto Step 7 else goto Step 8
Step 7: Swap the elements stored at arr[j] and arr[j+1] by performing the
following steps
Set temp = a[j+1]
Set arr[j+1] = arr[j]
Set a[j]=temp
Step 8: Set j = j + 1
Step 9: Set i = i - 1
Step 10: Stop.
[Link] selection sort with example.
In selection sort, the smallest value among the unsorted elements of the array is selected in
every pass and inserted to its appropriate position into the array. First, find the smallest
element of the array and place it on the first position. Then, find the second smallest element
of the array and place it on the second position. The process continues until we get the sorted
array.
Example of selection sort: Array [18 3 2 33 21]

[Link] algorithm for selection sort.

Step 1: Start
Step 2: Set i = 0, loc = 0 and temp = 0
Step 3: Repeat Steps 4-6 while i < size
Step 4: Set loc = Min(arr, i, size)
Step 5: Swap the elements stored at arr[i] and a[loc] by performing the
following steps
Set temp = a[loc]
Set a[loc] = a[i]
Set a[i]=temp
Step 6: Set i = i +1
Step 8: Stop
[Link] insertion sort with example.
Insertion Sort is a simplest data Sorting algorithm which sorts the array elements by shifting
elements one by one and inserting each element into its proper position. This technique is
also used for sort array elements. This is less efficient than the other sort algorithms like
quick sort, merge sort, etc.
Example of insertion sort: Array [ 18 3 2 33 21]

11. State algorithm for insertion sort.

Step 1: Start
Step 2: Set i = 1, j = 0 and temp = 0
Step 3: Repeat Steps 4-12 while i < size
Step 4: Set temp = arr[i]
Step 5: Set j = i-1
Step 6: Repeat Steps 7-10 while j>=0
Step 7: if arr[j] > temp goto Step 8 else goto Step 9
Step 8: Set arr[j+1] = arr[j]
Step 9: Branch out and go to Step 11
Step 10: Set j = j-1
Step 11: Set arr[j+1] = temp
Step 12: Set i = i + 1
Step 13: Stop
[Link] quick sort with example.
Quick Sort, as the name indicate, sorts any list of data very quickly. Quick sort very fast data
sorting technique and it requires very less additional space. It is based on the rule of Divide
and Conquer (also called partition-exchange sort).
Quick sort algorithm contains mainly three parts;
• Elements less than the Pivot element
• Pivot element
• Elements greater than the pivot element
Example of quick sort: Array [ 10 80 30 90 40 50 70]
 Unit – 3 Linked list
[Link] linked list with example.

Linked list: It is linear collection of data elements. Each element in linked list is called as
‘node’. Each node contains two fields. First is INFO which stores data & second is
LINK/NEXT which is linked with address of next node in a list.

[Link] and describe linked list terminologies.

➢ Node: Each data element in a linked list is represented as a node. Node contains two parts
one is info (data) and other is next pointer (address). Info part stores data and next pointer
stores address of next node.

➢ Data: data field stores the data for each data element, a node is acquired dynamically.
Address of the successor node can be stored in the pointer type field next.

➢ Pointer: pointer in c language is treated like a variable. It can store the address of any
variable or address of a memory block, acquired dynamically.

➢ Next pointer: Next pointer: It is a pointer that holds address of next node in the list i.e.
next pointer points to next node in the list.

➢ Null pointer: It is a pointer that does not hold any memory address i.e. it is pointing to
nothing. It is used to specify end of the list. The last element of list contains NULL pointer to
specify end of list.

➢ Empty list: Each linked list has a header node. When header node contains NULL value,
then that list is said to be empty list.
3. Difference between Static and Dynamic Memory Allocation.
[Link] Inserting an element in singly linked list at beginning.
There are the following steps which need to be followed in order to insert a new node in the
list at beginning.
1. Allocate the space for the new node and store data into the data part of the node.
2. Make the link part of the new node pointing to the existing first node of the list.
3. At the last, need to make the new node as the first node of the list.

Algorithm:
Step 1: Start
Step 2: Create the node pointer *temp
Struct node * temp
Step 3: Allocate address to temp using malloc
temp = malloc(sizeof(struct node));
Step 4: Check whether temp is null, if null then
Display “Overflow”
else
temp-> info=data
temp-> next=start
Step 5: Start=temp
Step 6 : Stop.
5. Explain Inserting an element in singly linked list at the end.
In order to insert a node at the last, there are two following scenarios which need to be
mentioned.
1. The node is being added to an empty list
2. The node is being added to the end of the linked list

Algorithm:
Step 1: Start
Step 2: Create two node pointers *temp, *q
struct node * temp, *q;
Step 3: q= start
Step 4: Allocate address to temp using malloc
temp = malloc(sizeof(struct node));
Step 5: Check whether temp is null, if null then
Display “Overflow”
else
temp-> info=data
temp-> next=null
Step 6: While(q->next!=null)
q= q-> next
Step 7: q->next= temp
Step 8: Stop.
6. Explain deleting an element in singly linked list at the beginning.
Deleting a node from the beginning of the list is the simplest operation of all. Since the first
node of the list is to be deleted, therefore, we just need to make the head, point to the next of
the head.

Algorithm
Step 1: Start
Step 2: If head = null;
Write ‘Underflow’
Goto step 5
End if
Step 3: Set temp = head
Step 4: Set head= head ->next
Step 5: Free temp
Step 6: Stop
[Link] deleting an element in singly linked list at the end.
In order to delete a last node, must position a pointer on the last node. Address of the node to
be deleted is stored in pointer P.
Algorithm:
Step 1: Start
Step 2: Create a temporary node as ‘temp’ and ‘q’.
Step 3: Set temp node as address of first node.
Step 4: Traverse the node to the last node and set as ‘q’
Step 5: Store null value in address field of ‘temp’ node.
Step 6: Delete q pointer.
Step 7: Stop.
[Link] deleting an element in singly linked list at the middle.
Algorithm:
Step 1: Start
Step 2: Create a temporary node as ‘temp’ and ‘q’.
Step 3: Set ‘temp’ node with the address of first node.
Step 4: Traverse the list up to the previous node of node 3 and mark the next node as ‘q’.
Step 5: Store address from node ‘q’ into address field of ‘temp’ node.
Step 6: delete ‘q’ pointer with free function.
Step 7: Deleting ‘q’ pointer deletes the node 3 from the list.
Step 8: Stop.
[Link] circular linked list.
A circular linked list is a variation of linked list in which the last element is linked to the first
element. This forms a circular loop.
A circular linked list can be either singly linked or doubly linked. for singly linked list, next
pointer of last item points to the first item. In doubly linked list, prev pointer of first item
points to last item as well.

We declare the structure for the circular linked list in the same way as follows:
Struct node
{
Int data;
Struct node *next;
};
Typedef struct node *Node;
Node *start = null;
Node *last = null;
[Link] inserting an element in circular linked list at beginning.
Algorithm:
Step 1: Start
Step 2: If ptr = null
write overflow
go to step 12
end if
Step 3: Set new_node = ptr
Step 4: Set ptr = ptr->next
Step 5: Set new_node->data = val
Step 6: Set temp = head
Step 7: Repeat step 9 while temp-> next != head
Step 8: Set temp = temp->next
end of loop
Step 9: Set new_node->next = head
Step 10: Set temp->next = new_node
Step 11: Set head = new_node
Step 12: Stop

[Link] inserting an element in circular linked list at end.

Algorithm:
Step 1: Start
Step 2: If ptr = null
write overflow go to step 1 [end of if]
Step 3: Set new_node = ptr
Step 4: Set ptr = ptr -> next
Step 5: Set new_node -> data = val
Step 6: Set new_node -> next = head
Step 7: Set temp = head
Step 8: Repeat step 8 while temp -> next != head
Step 9: Set temp = temp -> next
[end of loop]
Step 10: Set temp -> next = new_node
Step 11: Stop

[Link] an algorithm to searching an element in single linked list.

Algorithm:
Step 1: Start
Step 2: Declare variable no, flag and pointer temp
Step 3: Input search element
Step 4: Initialize pointer temp with the address from start pointer.( temp=start), flag with 0
Step 5: Repeat step 6 till temp != NULL
Step 6: Compare: temp->info = no then
set flag=1 and go to step 7
otherwise
increment pointer temp and go to step5
Step 7: Compare: flag=1 then
display "Node found"
otherwise
display "node not found"
Step 8: Stop
13. Write an algorithm to search a particular node in the given linked list.

[Link]
2. Take input as Initial Linked list
3. Set pos=1, flag =1
4. Input key element (x) to be searched.
4. Declare pointer ptr
5. Set ptr = start;
while (ptr ! = NULL)
do
if (ptr->data == x) then
do flag=1
break
else
do
ptr= ptr -> link;
pos = pos +1;
//end of if-else
//end of while loop
if ( ptr ! = NULL) then

Do Printf(“ Node is found\n”);

else
Printf(“Node not found\n”);

[Link]

[Link] Linked List and Array.

[Link] of Linked List.
Dynamic Memory Allocation
• Used to implement dynamic data structures where memory requirements change
frequently, such as stacks and queues.
Implementation of Data Structures
• Helps in creating other data structures like stacks, queues, deques, and graphs
efficiently.
Efficient Insertions and Deletions
• Ideal for scenarios where frequent insertions and deletions are required, such as
in real-time systems.
Dynamic Memory Management
• Helps in managing free blocks of memory in systems that dynamically allocate
memory, such as garbage collection.
Graph Representation
• Adjacency lists for representing sparse graphs are implemented using linked
lists.
 Unit – 4 Stack
[Link] is stack?
Stack is a linear data structure in which items are added or removed only at one end, called
top of the stack. Thus, there is no way to add or delete elements anywhere else in the stack. A
stack is based on Last-In-First-Out (LIFO) principle that means the data item that is inserted
last into the stack is the first one to be removed from the stack.
Example: Stack of Moulded chairs in which the last chair you put has to remove first for
seating.
[Link] stack representation in memory with the help of diagram.
Stacks appear as a group of elements stored at contiguous locations in memory. Each
successive insert or delete operation adds or removes an item from the group. The top
location of the stack or the point of addition or deletion is maintained by a pointer called top.

Stack implementation involves choosing the data storage mechanism for storing stack
elements and implementing methods for performing the two stack operations, push and pop.
[Link] stack with ADT.
The representation of stack as an abstract data type is very straightforward. We use eltype to
denote the type of the stack element and parameterize the stack type with eltype.
abstract typedef <<eltype>> stack (eltype).
C Implementation of stack: A stack s of integer data type can be declared as:
int s[10];
int Top = 1;
where s is an array of integer type which can hold integer values and top is the variable used
to hold top position of the list.
4. List any four applications of stack.

1)Reversing a list
2)Conversion of infix to prefix expression
3)Conversion of infix to postfix expression
4)Evaluation of prefix expression
5)Evaluation of postfix expression
6)Tower of Hanoi
7)Polish notation
[Link] stack operation condition.

➢ CREATE: Creates a new Stack. This operation creates a new stack which is empty.

➢ PUSH: The process of adding a new element to the top of stack is called Push operation.

➢ POP: The process of deleting an element from the top of stack is called Pop operation.

➢ IS EMPTY: Checks whether a stack is empty. This operation returns TRUE if the stack is
empty and false otherwise.

➢ IS FULL: Checks whether a stack is full. This operation returns TRUE if the stack is full
and false otherwise.

➢ UNDERFLOW: Stack underflow happens when we try to pop (remove) an item from the
stack, when stack is empty.

➢ OVERFLOW: Stack overflow happens when we try to push one more item onto our stack
when stack is already full.
6. State push and pop operation algorithm of stack.
push(stack[MAX],element)
Step 1: Start
Step 2: If top = MAX-1 goto Step 3 else goto Step 4
Step 3: Display message ”Stack Full” and exit
Step 4: top = top + 1
Step 5: stack[top] = element
Step 6: Stop
pop(stack[MAX],element)
Step 1: Start
Step 2: If top = -1 goto Step 3 else goto Step 4
Step 3: Display message ”Stack Empty” and exit
Step 4: Return stack[top] and set top = top - 1
Step 5: Stop
[Link] the effect of PUSH and POP operation on the stack size 10. The stack contains
40, 30, 52, 86, 39, 45, 50 with 50 begin at top of the stack. Show diagrammatically effects
of: push 59, push 85, pop, pop, push 59, pop
[Link] infix, prefix, postfix.
1. Infix notation: We write expression in infix notation, example a + b, where operators are
used in-between operands.
2. Prefix notation: In this (polish) notation, operator is written ahead of operands. For
example, +ab.
3. Postfix notation: This notation style is known as Reversed Polish Notation. In this notation
style, the operator is written after the operands. For example, ab+.
9. Explain PUSH and POP operation on stack with suitable example.

1) PUSH: The process of adding new element to the top of the stack is called PUSH
operation.
Algorithm:
Step 1: [Check for stack full/ overflow] If stack top is equal to max-1 then write “Stack
Overflow” return S
Step 2: [Increment top] top= top +1;
Step 3 : [Insert element] stack [top] = item;
Step 4 : return

2) POP: The process of deleting an element from top of the stack is called POP operation.
Algorithm:
Step 1: [Check for stack empty/ underflow] If stack top is equal to -1 then write “Stack
Underflow” return
Step 2:
[Copy data] item=stack[top];
Step 3 : [decrement top] top = top-1;
Step 4 : return

10. Differentiate between Stack and Queue (any four points).

[Link] the concept of recursion.

Recursion is a process of calling a function by itself. a recursive function body contains a
function call statement that calls itself repetitively. Recursion is an application of stack. When
a recursive function calls itself from body, stack is used to store temporary data handled by
the function in every iteration
Example:
function call from main() : fact(n); // consider n=5
Function definition:
int fact(int n)
{
if(n==1)
return 1;
else
return(n*fact(n-1));
}
[Link] of recursion
s1. Factorial Calculation
- Compute the factorial of a number (`n!`) recursively.
2. Fibonacci Series
- Generate the `n`th Fibonacci number by solving smaller subproblems.
3. Tree Traversals
- Perform Inorder, Preorder, and Postorder traversals in binary trees.
4. Binary Search
- Recursively divide a sorted array to find a target element.
5. Tower of Hanoi
- Solve the classic problem of moving disks between rods using recursive steps.
6. Maze Solving
- Find paths through a maze using recursive backtracking.
7. Graph Traversal (DFS)
- Depth First Search in graphs is implemented using recursion to explore nodes.
[Link] the given infix expression to the postfix expression using stack:
((a / (b – c + d)) *( e – a) *c)
 Unit – 5 Queue
[Link] Queue as an ADT.
Queue is a linear data structure in which the insertion and deletion operations are performed
at two different ends. In a queue data structure, adding and removing elements are performed
at two different positions. The insertion is performed at one end and deletion is performed at
another end. In a queue data structure, the insertion operation is performed at a position
which is known as 'rear' and the deletion operation is performed at a position which is known
as 'front'. In queue data structure, the insertion and deletion operations are performed based
on FIFO (First In First Out) principle.
[Link] Queue representation of memory in array.
A queue data structure can be implemented using one dimensional array. The queue
implemented using array stores only fixed number of data values. The implementation of
queue data structure using array is very simple. Just define a one-dimensional array of
specific size and insert or delete the values into that array by using FIFO (First In First Out)
principle with the help of variables 'front' and 'rear'. Initially both 'front' and 'rear' are set to -
1. Whenever, we want to insert a new value into the queue, increment 'rear' value by one and
then insert at that position. Whenever we want to delete a value from the queue, then delete
the element which is at 'front' position and increment 'front' value by one.
Queue Operations using Array
1. enQueue(value) - Inserting value into the queue
2. deQueue() - Deleting a value from the Queue
3. display() - Displays the elements of a Queue
[Link] Queue operations
There are two key operations associated with the queue data structure: enqueue and dequeue.
The enqueue operation adds an element at the rear end of the queue while the dequeue
operation removes an element from the front end of the queue.
➢ Enqueue: The insert operation involves the following subtasks:
1. Receiving the element to be inserted.
2. Incrementing the queue pointer, rear.
3. Storing the received element at new location of rear.

➢ enqueue operation algorithm:

insert(queue[MAX], element, front, rear)
Step 1: Start
Step 2: If front = NULL goto Step 3 else goto Step 6
Step 3: front = rear = 0
Step 4: queue[front]=element
Step 5: Goto Step 10
Step 6: if rear = MAX-1 goto Step 7 else goto Step 8
Step 7: Display the message, “Queue is Full” and goto Step 10
Step 8: rear = rear +1
Step 9: queue[rear] = element
Step 10: Stop
➢ Dequeue: The delete operation involves the following subtasks:
1. Retrieving or removing the element from the front end of the queue.
2. Incrementing the queue pointer, front, to make it point to the next element in the queue.

➢ Dequeue operation algorithm

delete(queue[MAX],front, rear)
Step 1: Start
Step 2: If front = NULL and rear = NULL goto Step 3 else goto Step 4
Step 3: Display the message, “Queue is Empty” and goto Step 10
Step 4: if front != NULL and front = rear goto Step 5 else goto Step 8
Step 5: Set i = queue[front]
Step 6: Set front = rear = -1
Step 7: Return the deleted element i and goto Step 10
Step 8: Set i = queue[front]
Step 9: Return the deleted element i
Step 10: Stop
[Link] Queue operation condition.
Queue full: A queue is full when its rear pointer points to max -1 position. Max is maximum
number of elements in a queue. If rear pointer is not equal to max-1 then a new element can
be added to a queue. If queue is full then new element cannot be added to a queue.
Example: Consider max=4. First element is stored at 0th position and last element is stored at
3rd position in queue. In the diagram given below rear pointer is pointing to max-1 (3)
position so queue is full.

Queue empty: A queue is empty when its front pointer points to -1 position. When front
pointer is -1 then one cannot delete any data from a queue.

Example: In the diagram given below front pointer points to -1 value i.e. it points no location
inside queue so queue is empty.
[Link] linear queue with example.
A basic queue is linear queue. Linear queue is an ordered list in which items may be added
only at one end called the “rear” and items may be removed only at the other end called
“front”.

➢ Real life example:

1. A line of passengers waiting to buy tickets in a reservation counter. Each new passenger
gets in line at the “rear”; the passenger at the front of the lines is reserved.
2. A linear queue can be found in a time-sharing computer system where many users share the
system simultaneously.
[Link] circular queue.
A circular queue is a queue whose start and end locations are logically connected with each
other. That means, the start location comes after the end location. If we continue to add
elements in a circular queue till its end location, then after the end location has been filled,
the next element will be added at the beginning of the queue. Circular queues remove one of
the main disadvantages of array implemented queues in which a lot of memory space is
wasted due to inefficient utilization.

Insert Operation: The insert operation for array implemented circular queues involves the
following tasks:
1. Checking whether the queue is already full.
2. Updating the rear pointer i
• I the queue is empty, set front and rear and
• If rear is pointing at the last location of the queue, set rear queue.
• If none of the above situations exist, simply increment the rear pointer by 1.
[Link] the new element at the rear location.

Delete Operation The delete operation for array implemented circular queues involves the
following tasks:
1. Checking whether the queue is already empty.
2. Retrieving the element at the front of the queue.
3. Updating the front pointer.
• If the queue has only one element left, set front and rear to point to NULL.
• If front is pointing at the last location of the queue, set front the queue.
• If none of the above situations exist, simply increment the front pointer by 1.
[Link] the element retrieved from the front location.
[Link] priority queue.
A priority queue is a data structure in which each element is assigned a priority. The priority
of the element will be used to determine the order in which the elements will be processed.
The general rules of processing the elements of a priority queue are
• An element with higher priority is processed before an element with a lower priority.
• Two elements with the same priority are processed on a first-come-first-served (FCFS)
basis.
• A priority queue can be thought of as a modified queue in which when an element has to be
removed from the queue, the one with the highest-priority is retrieved first.
Insertion: When a new element has to be inserted in a priority queue, we have to traverse the
entire list until we find a node that has a priority lower than that of the new element. The new
node is inserted before the node with the lower priority. However, if there exists an element
that has the same priority as the new element, the new element is inserted after that element.
Deletion: it is a very simple process in this case. The first node of the list will be deleted and
the data of that node will be processed first.
[Link] applications of queue.
• In computer system to maintain waiting list for single shared resources such as printer, disk,
etc.
• It is used as buffers on MP3 players, iPod playlist, etc.
• Used for CPU scheduling in multiprogramming and time-sharing systems.
• In real life, Call Center phone systems will use Queues, to hold people calling them in an
order, until a service representative is free.
• Handling of interrupts in real-time systems.
• Simulation.
 Unit – 6 Tree
[Link] Terminologies of tree.
a) Tree: a tree is a collection of elements called nodes, Tree is a non-linear data structure
which organizes data in a hierarchical structure and this is a recursive definition.
b) Root: The first node from where the tree originates is called as a root node. In any tree,
there must be only one root node. We can never have multiple root nodes in a tree data
structure.
c) Edge: The connecting link between any two nodes is called as an edge. In a tree with n
number of nodes, there are exactly (n-1) number of edges.
d) Parent: The node which has a branch from it to any other node is called as a parent node.
In other words, the node which has one or more children is called as a parent node. In a tree,
a parent node can have any number of child nodes.
e) Child: The node which is a descendant of some node is called as a child node. All the
nodes except root node are child nodes.
f) Siblings: Nodes which belong to the same parent are called as siblings. In other words,
nodes with the same parent are sibling nodes.
g) Leaf node: The node which does not have any child is called as a leaf node. Leaf nodes are
also called as external nodes or terminal nodes.

h) Degree of node: Degree of a node is the total number of children of that node.
Degree of node A, E: 2 Degree of node B, C: 3
Degree of node D, F, H, I: 0 Degree of node G: 1
i) Degree of a tree: Degree of a tree is the highest degree of a node among all the nodes in the
tree.
j) Level of tree: In a tree, each step from top to bottom is called as level of a tree. The level
count starts with 0 and increments by 1 at each level or step.

k) Height of tree: Total number of edges that lies on the longest path from any leaf node to a
particular node is called as height of that node. Height of a tree is the height of root node.
Height of all leaf nodes = 0

l) Depth of tree: Total number of edges from root node to a particular node is called as depth
of that node. Depth of a tree is the total number of edges from root node to a leaf node in the
longest path. Depth of the root node = 0

m) In-degree: number of edges coming towards nodes is in- degree.

In-degree of A – 0 In-degree of B – 1
n) Out-degree: number of edges going out from nodes is out-degree.
Out-degree of A- 2 Out-degree of B-3
o) Path: It is a sequence of consecutive edges from the source node to the destination node.
For ex: A-B-E-J.
[Link] general tree.
• A general tree is a tree where each node may have zero or more children (a binary tree is a
specialized case of a general tree). General trees are used to model applications such as file
systems.
• In general tree, root has indegree 0 and maximum outdegree n.
• Height of a general tree is the length of longest path from root to the leaf of tree. Height(T)
= {max(height(child1) , height(child2) , … height(child-n) ) +1}
• Subtree of general tree are not ordered.

[Link] binary tree.

Binary tree is one of the most widely used non-linear data structures in the field of computer
science. It is a restricted form of a general tree. The restriction that it applies to a general tree
is that its nodes can have a maximum degree of 2. That means, the nodes of a binary tree can
have zero, one or two child nodes but not more than that.

[Link] binary search tree.

A binary tree is referred as a binary search tree if for any node n in the tree:
• the node elements in the left subtree of n are lesser in value than n.
• the node elements in the right subtree of n are greater than or equal to n.

Thus, binary search tree arranges its node elements in a sorted manner. As the name suggests,
the most important application of a binary search tree is searching. The average running time
of searching an element in a binary search tree is O (logn), which is better than other data
structures like array and linked lists.
The various operations performed on a binary search tree are:
1. Insert
2. Search
3. Delete

1. Insert: The insert operation involves adding an element into the binary tree. The location
of the new element is determined in such a manner that insertion does not disturb the sort
order of the tree.
2. Search: The search operation involves traversing the various nodes of the binary tree to
search the desired elements.
3. Delete: The delete operation involves removing an element from the binary search tree. It
is important to ensure that after the element is removed from the tree, the other elements are
shuffled in such a manner that the sort order of the tree is regained.
[Link] in-order, pre-order and post-order traversal.
Traversal is the process of visiting the various elements of a data structure. Binary tree
traversal can be performed using three methods:
1. Preorder
2. Inorder
3. Postorder

➢ Preorder: The preorder traversal method performs the following operations:

(a) Process the root node (N).

(b) Traverse the left subtree of N (L).
(c) Traverse the right subtree of N (R).

➢ Inorder: The inorder traversal method performs the following operations:

(a) Traverse the left subtree of N (L).

(b) Process the root node (N).
(c) Traverse the right subtree of N (R).

➢ Postorder: The postorder traversal method performs the following operations:

(a) Traverse the left subtree of N (L).
(b) Traverse the right subtree of N (R).
(c) Process the root node (N).
Example:

Inorder Traversal: Q,E,F,R,D,H,B,A,I,J,K,C,L,P

Preorder Traversal: A,B,D,E,Q,F,R,H,C,I,J,K,L,P
Postorder Traversal: Q,R,F,E,H,D,B,K,J,I,P,L,C,A
[Link] is expression tree? Draw an expression tree for the following expression: (a – 2b
+ 5c)2 * (4d = 6e)5

Expression tree is nothing but a binary tree containing mathematical expression. The internal
nodes of the tree are used to store operators while the leaf or terminal nodes are used to store
operands. Various compilers and parsers use expression trees for evaluating arithmetic and
logical expressions.
Expression: (a – 2b + 5c)2 * (4d = 6e)5