Assignment: 1

OBJECTIVE: Write a program to search an element from a list. Give user the op on to
perform Linear or Binary search.
ALGORITHM:
1. Linear Search Algorithm:
LinearSearch(arr, n, key)
1. Start
2. Repeat for i = 0 to n-1
a. If arr[i] == key, then
i. Return i (index found)
3. If key not found, return -1
4. Stop
2. Binary Search Algorithm (Array must be sorted):
BinarySearch(arr, low, high, key)
1. Start
2. Repeat while low <= high
a. mid = (low + high) / 2
b. If arr[mid] == key
i. Return mid
c. If arr[mid] > key
i. high = mid - 1
d. Else
i. low = mid + 1
3. If key not found, return -1
4. Stop

CODE:-
#include<stdio.h>

1
int linearsearch(int arr[],int n, int key){
int i;
for(i=0;i<n;i++){
if(arr[i]==key)
return i;
}
return -1;
}
int binarysearch(int arr[],int low,int high, int key){
while(low<=high){
int mid=(low+high)/2;
if (arr[mid]==key)
return mid;
else if(arr[mid]>key)
high=mid-1;
else
low=mid+1;
}
return -1;
}
int main(){
int i,j,key,result,arr[100],choice,n;
prin ("enter no. of elements : \n");
scanf("%d",&n);
prin ("enter %d elements : ",n);
for(i=0;i<n;i++){
scanf("%d",&arr[i]);
}
prin ("enter the elements to search : \n");
scanf("%d",&key);

2
 prin ("choose search method\n1. linear search\[Link]\n enter
choice : ");
scanf("%d",&choice);
if(choice==1)
{
result=linearsearch(arr,n,key);
}
else if(choice==2){
for(i=0;i<n-1;i++){
for(j=0;j<n-1-i;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;

}
}
}
result=binarysearch(arr,0,n-1,key);
}
else{
prin ("invalid choice");
return 0;
}
if(result != -1)
prin ("Element found at posi on %d (index %d)\n", result + 1, result);
else
prin ("Element not found in the list.\n");
return 0;

3
OUTPUT:

CONCLUSION:
In this program, we have successfully implemented both Linear Search and Binary Search
techniques to search for an element in a list:
 Linear Search is simple and works on both sorted and unsorted lists but is less
efficient for large datasets (Time Complexity: O(n)).
 Binary Search is more efficient (Time Complexity: O(log n)) but requires the list to be
sorted.
By giving the user the op on to choose the search method, the program becomes flexible
and demonstrates the prac cal use of both algorithms. This enhances the user's
understanding of when and how to apply each searching technique effec vely based on the
nature of the data.

4
 Assignment:-2
OBJECTIVE: Write a program to sort a list of elements. using Inser on sort. Give user the
op on to perform sor ng in ascending or descending order.

Algorithm:
Inser onSort(arr, n, order)
1. Start
2. For i = 1 to n-1 do:
a. key = arr[i]
b. j = i - 1
c. While j >= 0 and
(order == ASCENDING and arr[j] > key) or
(order == DESCENDING and arr[j] < key)
i. arr[j+1] = arr[j]
ii. j = j - 1
d. arr[j+1] = key
3. Stop

Code:
#include<stdio.h>
void inser onsort(int arr[],int n,int order){
int i;
for(i=1;i<n;i++){
int key=arr[i];
int j=i-1;
if (order==1){//ascending
while(j>=0 && arr[j]>key){
arr[j+1]=arr[j];
j--;
}
}

5
 else{// descending
while(j>=0 && arr[j]<key){
arr[j+1]=arr[j];
j--;
}
}
arr[j+1]=key;
}
}
int main(){
int arr[100],n,i,order;
prin ("enter no. of elements: ");
scanf("%d",&n);
prin ("enter %d elements: \n",n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
prin ("choose sor ng order:\n1. ascending\n2. desending\n enter choice: ");
scanf("%d",&order);
if(order!=1 && order!=2){
prin ("invalid choice.\n");
return 0;
}
inser onsort(arr,n,order);
prin ("sorted array: \n");
for(i=0;i<n;i++)
prin ("%d\t",arr[i]);
prin ("\n");
return 0;
}

6
Output:

Conclusion:
In this program, we implemented the Inser on Sort algorithm which is simple and efficient
for small datasets. The program allows users to choose between ascending and descending
sor ng orders:
 In ascending order, the smallest elements are placed first.
 In descending order, the largest elements come first.
Inser on sort works by inser ng each element into its correct posi on among the already-
sorted part of the array.
Its me complexity is O(n²) in the worst case, making it less efficient for large lists, but it is
s ll useful for small datasets or par ally sorted arrays.

7
 Assignment: 3
Objec ve:- Implement Linked List. Include func ons for inser on, dele on and search of a
number, reverse the list and concatenate two linked lists.

Algorithm:
1. Create Node / Insert at End
Algorithm InsertAtEnd(data):
1. Create a new node with the given data.
2. If head is NULL:
Set head = new node.
3. Else:
Traverse to the last node.
Set last node’s next = new node.
4. End
2. Delete a Node by Value
Algorithm DeleteByValue(key):
1. If head is NULL:
Print "List is empty" and return.
2. If head's data = key:
Temp = head
head = head->next
Free temp
Return
3. Else:
Traverse the list to find the node with value = key.
Keep track of previous node.
If found:
previous->next = current->next
Free current
Else:
Print "Key not found"
4. End
8
3. Search a Number
Algorithm Search(key):
1. Set temp = head
2. While temp is not NULL:
If temp->data == key:
Print "Found" and return
Move to next node
3. If loop ends, print "Not found"
4. Reverse the List
Algorithm ReverseList():
1. Ini alize prev = NULL, current = head, next = NULL
2. While current != NULL:
next = current->next
current->next = prev
prev = current
current = next
3. Set head = prev
5. Concatenate Two Lists
Algorithm Concatenate(head1, head2):
1. If head1 is NULL:
return head2
2. Traverse to the end of list1
3. Set last node’s next = head2
4. Return head1

Code:
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
9
 struct Node* next;
};

struct Node* head = NULL;

void insert(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

if (head == NULL)
head = newNode;
else {
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
}

void delete(int value) {

struct Node* temp = head;
struct Node* prev = NULL;

if (temp != NULL && temp->data == value) {

head = temp->next;
free(temp);
return;
}

while (temp != NULL && temp->data != value) {

10
 prev = temp;
temp = temp->next;
}

if (temp == NULL)
prin ("Value not found!\n");
else {
prev->next = temp->next;
free(temp);
}
}

void search(int value) {

struct Node* temp = head;
while (temp != NULL) {
if (temp->data == value) {
prin ("Found %d\n", value);
return;
}
temp = temp->next;
}
prin ("Not Found %d\n", value);
}

void reverse() {
struct Node *prev = NULL, *current = head, *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
11
 }
head = prev;
}

void display(struct Node* h) {

while (h != NULL) {
prin ("%d -> ", h->data);
h = h->next;
}
prin ("NULL\n");
}

struct Node* concatenate(struct Node* h1, struct Node* h2) {

if (h1 == NULL) return h2;
struct Node* temp = h1;
while (temp->next != NULL)
temp = temp->next;
temp->next = h2;
return h1;
}

int main() {
insert(10);
insert(20);
insert(30);
prin ("List: ");
display(head);

search(20);
delete(20);
prin ("A er dele on: ");
12
 display(head);

reverse();
prin ("A er reversing: ");
display(head);

// Second list
struct Node* head2 = NULL;
struct Node* temp;
temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = 100; temp->next = NULL;
head2 = temp;
temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = 200; temp->next = NULL;
head2->next = temp;

prin ("Second List: ");

display(head2);

head = concatenate(head, head2);

prin ("Concatenated List: ");
display(head);

return 0;
}

13
Output:

Conclusion:
The implementa on of a linked list allows efficient inser on and dele on opera ons
without realloca ng or reorganizing the en re structure.
This program demonstrates:
 Inser ng elements at the end
 Dele ng a specific value
 Searching for a value
 Reversing the list
 Concatena ng two lists
It showcases dynamic memory usage and pointer manipula on—essen al skills in low-level
programming.

14
 Assignment : 4

Objec ve: Implement Doubly Linked List. Include func ons for inser on, dele on and
search of a number, reverse the list.

Algorithm:
1. Inser on at End
Algorithm Insert(value)
1. Create a new node with given value
2. If head is NULL:
head ← new node
3. Else:
Traverse to the last node
Set last_node.next ← new node
new_node.prev ← last_node
2. Dele on by Value
Algorithm Delete(value)
1. Set temp ← head
2. While temp ≠ NULL and [Link] ≠ value:
temp ← [Link]
3. If temp = NULL:
Print "Not Found"
4. Else:
If [Link] ≠ NULL: [Link] ← [Link]
If [Link] ≠ NULL: [Link] ← [Link]
If temp = head: head ← [Link]
Free temp
3. Search
Algorithm Search(value)

15
1. Set temp ← head, pos ← 1
2. While temp ≠ NULL:

If [Link] = value: Print posi on and return

temp ← [Link]; pos ← pos + 1
3. Print "Not Found"
4. Reverse
Algorithm Reverse()
1. Set current ← head
2. While current ≠ NULL:
Swap [Link] and [Link]
current ← [Link] (which is original next)
3. Set head ← last node processed

Code:
#include <stdio.h>
#include <stdlib.h>

// Define the node structure

struct Node {
int data;
struct Node* prev;
struct Node* next;
};

// Func on prototypes
void insertEnd(struct Node** head, int data);
void deleteNode(struct Node** head, int key);
struct Node* search(struct Node* head, int key);
void reverseList(struct Node** head);

16
void display(struct Node* head);

// Main func on
int main() {
struct Node* head = NULL;

// Inser ng elements
insertEnd(&head, 10);
insertEnd(&head, 20);
insertEnd(&head, 30);
insertEnd(&head, 40);

prin ("Doubly Linked List: ");

display(head);

// Searching
int searchKey = 20;
struct Node* found = search(head, searchKey);
if (found != NULL)
prin ("Element %d found.\n", searchKey);
else
prin ("Element %d not found.\n", searchKey);

// Dele on
deleteNode(&head, 20);
prin ("A er dele ng 20: ");
display(head);

// Reversing

17
 reverseList(&head);
prin ("A er reversing: ");

display(head);

return 0;
}

// Func on to insert at end

void insertEnd(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;

if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}

struct Node* temp = *head;

while (temp->next != NULL)
temp = temp->next;

temp->next = newNode;
newNode->prev = temp;
}

// Func on to delete a node by key

void deleteNode(struct Node** head, int key) {

18
 struct Node* temp = *head;

// Find the node to delete

while (temp != NULL && temp->data != key)
temp = temp->next;

if (temp == NULL) {
prin ("Element %d not found.\n", key);
return;
}

// If it's the head node

if (temp == *head)
*head = temp->next;

if (temp->next != NULL)
temp->next->prev = temp->prev;

if (temp->prev != NULL)
temp->prev->next = temp->next;

free(temp);
}

// Func on to search a key

struct Node* search(struct Node* head, int key) {
while (head != NULL) {
if (head->data == key)
return head;

19
 head = head->next;
}

return NULL;
}

// Func on to reverse the list

void reverseList(struct Node** head) {
struct Node* temp = NULL;
struct Node* current = *head;

while (current != NULL) {

temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}

if (temp != NULL)
*head = temp->prev;
}

// Func on to display the list

void display(struct Node* head) {
while (head != NULL) {
prin ("%d ", head->data);
head = head->next;
}
prin ("\n");
}

20
Output:

Conclusion
This program demonstrates the fundamental opera ons of a Doubly Linked List in C,
including:
 Inser on at the end of the list
 Dele on of a node by its value
 Searching for a specific value
 Reversing the en re list
 Displaying the list for verifica on
Using a doubly linked list provides flexibility in traversal (both forward and backward) and
simplifies dele on opera ons compared to singly linked lists. This implementa on lays a
strong founda on for understanding dynamic data structures and memory management in
C programming.

21
 Assignment:5

Objec ve: Perform Stack opera ons using Array implementa on.

Algorithm:
1. Ini alize:
 Set top = -1.
 Define an array of a fixed size MAX.
2. Push Opera on:
 If top == MAX - 1, report "Stack Overflow".
 Else, increment top and insert element at stack[top].

3. Pop Opera on:

 If top == -1, report "Stack Underflow".
 Else, retrieve and display stack[top], then decrement top.
4. Peek Opera on:
 If top == -1, report "Stack is empty".
 Else, display stack[top].
5. Display Opera on:
 If top == -1, report "Stack is empty".
 Else, display elements from top to 0.
6. Exit:

 End the program when the user chooses to exit.

Code:
#include <stdio.h>
#define MAX 100

22
int stack[MAX];
int top = -1;

// Func on prototypes
void push();
void pop();
void peek();
void display();

int main() {
int choice;

while (1) {
prin ("\n*** Stack Menu ***\n");
prin ("1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n");
prin ("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1: push(); break;
case 2: pop(); break;
case 3: peek(); break;
case 4: display(); break;
case 5:
prin ("Exi ng program...\n");
return 0;
default:
prin ("Invalid choice! Please try again.\n");
}

23
 }
return 0;

void push() {
int value;
if (top == MAX - 1) {
prin ("Stack Overflow! Cannot push element.\n");
} else {
prin ("Enter value to push: ");
scanf("%d", &value);
top++;
stack[top] = value;
prin ("%d pushed onto stack.\n", value);
}
}

void pop() {
if (top == -1) {
prin ("Stack Underflow! Cannot pop element.\n");
} else {
prin ("%d popped from stack.\n", stack[top]);
top--;
}
}

void peek() {
if (top == -1) {
prin ("Stack is empty.\n");

24
 } else {
prin ("Top element is: %d\n", stack[top]);

}
}

void display() {
int i;
if (top == -1) {
prin ("Stack is empty.\n");
} else {
prin ("Stack elements are:\n");
for (i = top; i >= 0; i--) {
prin ("%d\n", stack[i]);
}
}
}

25
Output:

Conclusion:
This program demonstrates the fundamental stack opera ons using an array in C. It
includes:
 Push for inser ng elements,
 Pop for removing the top element,
 Peek for viewing the top without removing, and
 Display for showing all elements in the stack.
This is a sta c stack implementa on, and hence, it has a fixed maximum size. This method is
efficient for small-scale applica ons, but for dynamic memory needs, a linked list
implementa on of a stack is recommended.

26
 Assignment:6

Objec ve: Perform Queue opera ons using linked list implementa on.

Algorithm:
1. Ini alize:
o Create a structure Node containing data and a pointer to the next node.
o Define two pointers: front and rear, both ini ally set to NULL.
2. Enqueue (Insert):
o Create a new node.
o If memory is not available, print "Overflow".
o If the queue is empty (front == NULL), set both front and rear to the new
node.
o Else, set rear->next = new node and update rear = new node.
3. Dequeue (Delete):
o If front == NULL, print "Underflow".
o Else, save the front node, print its data, move front = front->next, and free
the old node.
4. Peek (Front Element):
o If front == NULL, print "Queue is empty".
o Else, print front->data.
5. Display:
o Traverse from front to rear, prin ng each node's data.
6. Exit:
o Exit when the user selects the op on.

27
Code:
#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
int data;
struct Node* next;
};

struct Node* front = NULL;

struct Node* rear = NULL;

// Func on declara ons

void enqueue(int value);
void dequeue();
void peek();
void display();

int main() {
int choice, value;

while (1) {
prin ("\n*** Queue Menu ***\n");
prin ("1. Enqueue\n2. Dequeue\n3. Peek\n4. Display\n5. Exit\n");
prin ("Enter your choice: ");
scanf("%d", &choice);

28
 switch (choice) {

case 1:
prin ("Enter value to enqueue: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
peek();
break;
case 4:
display();
break;
case 5:
prin ("Exi ng program...\n");
exit(0);
default:
prin ("Invalid choice! Try again.\n");
}
}
return 0;
}

void enqueue(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {

29
 prin ("Overflow! Memory not allocated.\n");
return;

}
newNode->data = value;
newNode->next = NULL;

if (rear == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
prin ("%d enqueued to the queue.\n", value);
}

void dequeue() {
if (front == NULL) {
prin ("Underflow! Queue is empty.\n");
return;
}

struct Node* temp = front;

prin ("%d dequeued from the queue.\n", front->data);
front = front->next;

if (front == NULL) {
rear = NULL;
}

30
 free(temp);
}

void peek() {
if (front == NULL) {
prin ("Queue is empty.\n");
} else {
prin ("Front element is: %d\n", front->data);
}
}

void display() {
if (front == NULL) {
prin ("Queue is empty.\n");
return;
}

struct Node* temp = front;

prin ("Queue elements: ");
while (temp != NULL) {
prin ("%d ", temp->data);
temp = temp->next;
}
prin ("\n");
}

Output:

31
Conclusion:
This program demonstrates the dynamic implementa on of Queue using a linked list in C.
The opera ons include:
 Enqueue: Add elements to the rear.
 Dequeue: Remove elements from the front.
 Peek: View the front element.
 Display: Print all elements in order.

32
 Assignment:7
Objec ve: Create and perform different opera ons on Double-ended Queues using Linked
List implementa on.

Algorithm:
1. Ini alize:
 Define a structure Node with data, prev, and next pointers.
 Maintain two pointers: front and rear, ini alized to NULL.
2. Insert at Front:
 Create a new node.
 If the deque is empty, set both front and rear to the new node.
 Else, link the new node before the front and update front.
3. Insert at Rear:
 Create a new node.
 If the deque is empty, set both front and rear to the new node.
 Else, link the new node a er the rear and update rear.
4. Delete from Front:
 If the deque is empty, report underflow.

 Else, remove the front node and update front.

5. Delete from Rear:
 If the deque is empty, report underflow.
 Else, remove the rear node and update rear.
6. Display:
 Traverse from front to rear and print elements.

Code:
#include <stdio.h>
#include <stdlib.h>

33
// Node structure

struct Node {
int data;
struct Node* prev;
struct Node* next;
};

struct Node* front = NULL;

struct Node* rear = NULL;

// Func on prototypes
void insertFront(int value);
void insertRear(int value);
void deleteFront();
void deleteRear();
void display();

int main() {
int choice, value;

while (1) {
prin ("\n*** Double-ended Queue (Deque) Menu ***\n");
prin ("1. Insert at Front\n2. Insert at Rear\n");
prin ("3. Delete from Front\n4. Delete from Rear\n");
prin ("5. Display\n6. Exit\n");
prin ("Enter your choice: ");
scanf("%d", &choice);

34
 switch (choice) {
case 1:

prin ("Enter value to insert at front: ");

scanf("%d", &value);
insertFront(value);
break;
case 2:
prin ("Enter value to insert at rear: ");
scanf("%d", &value);
insertRear(value);
break;
case 3:
deleteFront();
break;
case 4:
deleteRear();
break;
case 5:
display();
break;
case 6:
prin ("Exi ng program...\n");
exit(0);
default:
prin ("Invalid choice! Try again.\n");
}
}
return 0;
}

35
void insertFront(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;
newNode->prev = NULL;
newNode->next = front;

if (front == NULL) {
rear = newNode;
} else {
front->prev = newNode;
}
front = newNode;
prin ("%d inserted at front.\n", value);
}

void insertRear(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
newNode->prev = rear;

if (rear == NULL) {
front = newNode;
} else {
rear->next = newNode;
}
rear = newNode;
prin ("%d inserted at rear.\n", value);

36
}

void deleteFront() {
if (front == NULL) {
prin ("Deque is empty! Cannot delete from front.\n");
return;
}

struct Node* temp = front;

prin ("%d deleted from front.\n", front->data);
front = front->next;

if (front == NULL) {
rear = NULL;
} else {
front->prev = NULL;
}

free(temp);
}

void deleteRear() {
if (rear == NULL) {
prin ("Deque is empty! Cannot delete from rear.\n");
return;
}

struct Node* temp = rear;

prin ("%d deleted from rear.\n", rear->data);

37
 rear = rear->prev;

if (rear == NULL) {
front = NULL;
} else {
rear->next = NULL;
}

free(temp);
}

void display() {
if (front == NULL) {
prin ("Deque is empty.\n");
return;
}

struct Node* temp = front;

prin ("Deque elements: ");
while (temp != NULL) {
prin ("%d ", temp->data);
temp = temp->next;
}
prin ("\n");
}

Output:

38
39
Conclusion
This C program demonstrates the double-ended queue (deque) using a doubly linked list,
which allows:
 Inser on and dele on from both front and rear ends.
 Efficient dynamic memory usage without overflow (unless memory is exhausted).
 Flexible data management useful in various real-life scheduling and resource
management problems.

40
 Assignment:8

Objec ve: Write a program to scan a polynomial using linked list and add two polynomials.

Algorithm:
1. Structure Defini on:
 Create a structure Node with:
o int coeff (coefficient),
o int pow (power),
o Node* next.
2. Scan (Create) a Polynomial:
 Use a func on to repeatedly insert terms (coeff, power) in decreasing order of
power into a linked list.
3. Addi on of Two Polynomials:
 Traverse both lists simultaneously:
o If power of first term > second term → copy first term to result.
o If power of first term < second term → copy second term to result.
o If powers are equal → add the coefficients and insert result term.
 If one list is exhausted, copy remaining terms of the other list.
4. Display:
 Traverse and print each term in the format: coeff x^pow.

Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int coeff;
int pow;
struct Node* next;
};

41
void insertTerm(struct Node** poly, int coeff, int pow);
void createPolynomial(struct Node** poly);
void displayPolynomial(struct Node* poly);
struct Node* addPolynomials(struct Node* poly1, struct Node* poly2);
int main() {
struct Node* poly1 = NULL;
struct Node* poly2 = NULL;
struct Node* result = NULL;
prin ("Enter first polynomial:\n");
createPolynomial(&poly1);
prin ("\nEnter second polynomial:\n");
createPolynomial(&poly2);
prin ("\nFirst Polynomial: ");
displayPolynomial(poly1);
prin ("Second Polynomial: ");
displayPolynomial(poly2);
result = addPolynomials(poly1, poly2);
prin ("Sum of Polynomials: ");
displayPolynomial(result);

return 0;
}
void insertTerm(struct Node** poly, int coeff, int pow) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->coeff = coeff;
newNode->pow = pow;
newNode->next = NULL;
if (*poly == NULL || (*poly)->pow < pow) {
newNode->next = *poly;
*poly = newNode;
} else {
42
 struct Node* temp = *poly;
while (temp->next != NULL && temp->next->pow >= pow)
temp = temp->next;
if (temp->pow == pow) {
temp->coeff += coeff;
free(newNode);
} else {
newNode->next = temp->next;
temp->next = newNode;
}
}
}
void createPolynomial(struct Node** poly) {
int n,i, coeff, pow;
prin ("Enter number of terms: ");
scanf("%d", &n);
for ( i = 0; i < n; i++) {
prin ("Enter coefficient and power of term %d: ", i + 1);
scanf("%d%d", &coeff, &pow);
insertTerm(poly, coeff, pow);
}
}
void displayPolynomial(struct Node* poly) {
while (poly != NULL) {
prin ("%dx^%d", poly->coeff, poly->pow);
poly = poly->next;
if (poly != NULL)
prin (" + ");
}
prin ("\n");
}
43
struct Node* addPolynomials(struct Node* poly1, struct Node* poly2) {
struct Node* result = NULL;
while (poly1 != NULL && poly2 != NULL) {
if (poly1->pow > poly2->pow) {
insertTerm(&result, poly1->coeff, poly1->pow);
poly1 = poly1->next;
} else if (poly1->pow < poly2->pow) {
insertTerm(&result, poly2->coeff, poly2->pow);
poly2 = poly2->next;
} else {
insertTerm(&result, poly1->coeff + poly2->coeff, poly1->pow);
poly1 = poly1->next;
poly2 = poly2->next;
}
}
while (poly1 != NULL) {
insertTerm(&result, poly1->coeff, poly1->pow);
poly1 = poly1->next;
}
while (poly2 != NULL) {
insertTerm(&result, poly2->coeff, poly2->pow);
poly2 = poly2->next;
}
return result;
}

44
Output:

Conclusion
This program demonstrates how to represent polynomials using linked lists and how to add
two polynomials efficiently by:
 Storing terms in decreasing order of power,
 Merging terms with the same power during addi on,
 Dynamically alloca ng memory without any pre-fixed size limit.

45
 Assignment:9
Objec ve: Write a program to create a Binary Search Tree and include following opera ons
in tree:
(a) Inser on (Recursive and Itera ve Implementa on).
(b) Dele on.
(c) Search a node in BST.
(d) Display its preorder, postorder and inorder traversals recursively.
(e) Display height of tree.

Algorithm:
1. Inser on (Recursive)
Func on insertRecursive(root, key):
If root is NULL:
Create new node with key and return it
If key < root->data:
root->le = insertRecursive(root->le , key)
Else if key > root->data:
root->right = insertRecursive(root->right, key)
Return root

2. Inser on (Itera ve)

Func on insertItera ve(root, key):
Create newNode with key
If root is NULL:
Return newNode
Set current = root
While current is not NULL:
Set parent = current
If key < current->data:
current = current->le
46
 Else if key > current->data:
current = current->right

Else:
Return root // Duplicate, do nothing
A ach newNode to appropriate side of parent
Return root

3. Search
Func on search(root, key):
If root is NULL or root->data == key:
Return root
If key < root->data:
Return search(root->le , key)
Else:
Return search(root->right, key)

4. Delete Node
Func on deleteNode(root, key):
If root is NULL:
Return NULL
If key < root->data:
root->le = deleteNode(root->le , key)
Else if key > root->data:
root->right = deleteNode(root->right, key)
Else:
If root has one or no child:
Replace root with child and delete root
Else:
Find in-order successor (min in right subtree)

47
 Replace root->data with successor->data
Delete successor node

Return root

5. Inorder Traversal (LNR)

Func on inorder(root):
If root is not NULL:
inorder(root->le )
Visit root->data
inorder(root->right)

6. Preorder Traversal (NLR)

Func on preorder(root):
If root is not NULL:
Visit root->data
preorder(root->le )
preorder(root->right)

7. Postorder Traversal (LRN)

Func on postorder(root):
If root is not NULL:
postorder(root->le )
postorder(root->right)
Visit root->data

8. Height of BST
Func on height(root):
If root is NULL:
Return -1

48
 le Height = height(root->le )
rightHeight = height(root->right)

Return max(le Height, rightHeight) + 1

Code:
#include <stdio.h>

#include <stdlib.h>

// Node structure

struct Node {

int data;

struct Node* le ;

struct Node* right;

};

struct Node* insertRecursive(struct Node* root, int data);

struct Node* insertItera ve(struct Node* root, int data);

struct Node* deleteNode(struct Node* root, int key);

struct Node* search(struct Node* root, int key);

void inorder(struct Node* root);

void preorder(struct Node* root);

void postorder(struct Node* root);

int height(struct Node* root);

struct Node* createNode(int data);

struct Node* findMin(struct Node* root);

// Main func on

int main() {

struct Node* root = NULL;

int choice, data;

while (1) {

prin ("\n---- Binary Search Tree Menu ----\n");

prin ("1. Insert (Recursive)\n");

prin ("2. Insert (Itera ve)\n");

49
prin ("3. Delete a node\n");

prin ("4. Search a node\n");

prin ("5. Inorder Traversal\n");

prin ("6. Preorder Traversal\n");

prin ("7. Postorder Traversal\n");

prin ("8. Height of Tree\n");

prin ("9. Exit\n");

prin ("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

prin ("Enter value to insert (recursive): ");

scanf("%d", &data);

root = insertRecursive(root, data);

break;

case 2:

prin ("Enter value to insert (itera ve): ");

scanf("%d", &data);

root = insertItera ve(root, data);

break;

case 3:

prin ("Enter value to delete: ");

scanf("%d", &data);

root = deleteNode(root, data);

break;

case 4:

prin ("Enter value to search: ");

scanf("%d", &data);

if (search(root, data))

prin ("Node found!\n");

else

50
 prin ("Node not found!\n");

break;

case 5:

prin ("Inorder: ");

inorder(root);

prin ("\n");

break;

case 6:

prin ("Preorder: ");

preorder(root);

prin ("\n");

break;

case 7:

prin ("Postorder: ");

postorder(root);

prin ("\n");

break;

case 8:

prin ("Height of tree: %d\n", height(root));

break;

case 9:

exit(0);

default:

prin ("Invalid choice!\n");

return 0;

// Create a new node

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

51
 newNode->data = data;

newNode->le = newNode->right = NULL;

return newNode;

// Recursive Inser on

struct Node* insertRecursive(struct Node* root, int data) {

if (root == NULL)

return createNode(data);

if (data < root->data)

root->le = insertRecursive(root->le , data);

else if (data > root->data)

root->right = insertRecursive(root->right, data);

return root;

// Itera ve Inser on

struct Node* insertItera ve(struct Node* root, int data) {

struct Node* newNode = createNode(data);

if (root == NULL)

return newNode;

struct Node* current = root;

struct Node* parent = NULL;

while (current != NULL) {

parent = current;

if (data < current->data)

current = current->le ;

else if (data > current->data)

current = current->right;

else

return root; // Duplicate, do nothing

if (data < parent->data)

52
 parent->le = newNode;

else

parent->right = newNode;

return root;

struct Node* search(struct Node* root, int key) {

if (root == NULL || root->data == key)

return root;

if (key < root->data)

return search(root->le , key);

else

return search(root->right, key);

// Find minimum node

struct Node* findMin(struct Node* root) {

while (root && root->le != NULL)

root = root->le ;

return root;

// Dele on

struct Node* deleteNode(struct Node* root, int key) {

if (root == NULL)

return root;

if (key < root->data)

root->le = deleteNode(root->le , key);

else if (key > root->data)

root->right = deleteNode(root->right, key);

else {

// Node found

if (root->le == NULL) {

53
 struct Node* temp = root->right;

free(root);

return temp;

else if (root->right == NULL) {

struct Node* temp = root->le ;

free(root);

return temp;

struct Node* temp = findMin(root->right);

root->data = temp->data;

root->right = deleteNode(root->right, temp->data);

return root;

// Traversals

void inorder(struct Node* root) {

if (root) {

inorder(root->le );

prin ("%d ", root->data);

inorder(root->right);

void preorder(struct Node* root) {

if (root) {

prin ("%d ", root->data);

preorder(root->le );

preorder(root->right);

54
}

void postorder(struct Node* root) {

if (root) {

postorder(root->le );

postorder(root->right);

prin ("%d ", root->data);

// Height of the tree

int height(struct Node* root) {

if (root == NULL)

return -1; // height of empty tree is -1

int le Height = height(root->le );

int rightHeight = height(root->right);

return (le Height > rightHeight ? le Height : rightHeight) + 1;

Output:

55
56
Conclusion
This C program efficiently demonstrates the crea on and manipula on of a Binary Search
Tree (BST). It includes:
 Recursive and itera ve inser on methods.
 Dele on logic that handles leaf nodes, nodes with one child, and nodes with two
children.
 Searching a key with log(n) complexity in balanced trees.
 Tree traversals (Inorder, Preorder, Postorder) to view the data in different orders.
 Height calcula on to understand the depth and balance of the tree.
57
 Assignment :10

Objec ve: Write a program to reverse the order of the elements in the stack using
addi onal stack.

Algorithm:
1. Create two stacks: original and temp.
2. While original stack is not empty:
o Pop an element from original.
o Push it into temp.
3. While temp stack is not empty:
o Pop from temp and push back into original.
4. Now, the original stack is reversed.

Code:
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Stack structure
struct Stack {

int top;
int arr[MAX];
};

// Ini alize stack

void init(struct Stack* stack) {
stack->top = -1;

58
}

// Check if stack is empty

int isEmpty(struct Stack* stack) {
return stack->top == -1;
}

// Check if stack is full

int isFull(struct Stack* stack) {
return stack->top == MAX - 1;
}

// Push element
void push(struct Stack* stack, int value) {
if (isFull(stack)) {
prin ("Stack Overflow\n");
return;
}
stack->arr[++stack->top] = value;
}

// Pop element
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
prin ("Stack Underflow\n");
return -1;
}
return stack->arr[stack->top--];
}

59
// Peek top element

int peek(struct Stack* stack) {

if (!isEmpty(stack))
return stack->arr[stack->top];
return -1;
}

// Display stack
void display(struct Stack* stack) {
int i;
if (isEmpty(stack)) {
prin ("Stack is empty\n");
return;
}
prin ("Stack: ");
for (i = 0; i <= stack->top; i++)
prin ("%d ", stack->arr[i]);
prin ("\n");
}

// Func on to reverse a stack using an auxiliary stack

void reverseStack(struct Stack* original) {
struct Stack temp;
init(&temp);

while (!isEmpty(original)) {
int val = pop(original);
push(&temp, val);

60
 }

// Copy back to original stack

while (!isEmpty(&temp)) {
int val = pop(&temp);
push(original, val);
}
}

// Driver code
int main() {
struct Stack s;
init(&s);

// Push elements
push(&s, 10);
push(&s, 20);
push(&s, 30);
push(&s, 40);

prin ("Original Stack:\n");

display(&s);

reverseStack(&s);

prin ("Reversed Stack:\n");

display(&s);
return 0;
}

61
Output:

Conclusion:
This program demonstrates how to reverse the order of elements in a stack using another
stack as a temporary storage.
 It uses the Last-In-First-Out (LIFO) property of stacks.
 By popping elements from the original stack and pushing them onto a new stack, the
order gets reversed.
 This technique is simple and efficient for stack reversal with O(n) me complexity
and O(n) auxiliary space.

62