PROGRAM-1

AIM:-Write a program to sort an array using Bubble Sort Technique.

ALGORITHM

1. Repeat steps 2 & 3 for k = 1 to N-1

2. Set ptr =1
3. Repeat while ptr <= N-k
4. (a) If data[ptr] > data[ptr + 1],then
Interchange data[ptr] and data[ptr + 1]
(b) ptr = ptr + 1
5. Exit

CODE
#include <stdio.h>
int main()
{
int n;
// Input the size of the array
printf("Enter the number of elements in the array: ");
scanf("%d", &n);
int arr[n]; // Declare the array with size n
// Input the elements of the array
printf("Enter %d integers:\n", n);
for (int i = 0; i< n; i++) {
printf("Element %d: ", i + 1);
scanf("%d", &arr[i]);
}
// Bubble Sort algorithm
for (int i = 0; i< n - 1; i++) {
// Track whether a swap was made
int swapped = 0;
// Last i elements are already sorted
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] >arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1; // Set swapped to indicate a swap occurred
}
}

// If no two elements were swapped in the inner loop, then the array is sorted
if (swapped == 0) {
break;
}
}

// Display the sorted array

printf("Sorted array: \n");
for (int i = 0; i< n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

OUTPUT
Enter the number of elements in the array: 6
Enter 6 integers:
Element 1: 5
Element 2: 5
Element 3: 6
Element 4: 7
Element 5: 9
Element 6: 4
Sorted array:
455679
 PROGRAM NO: 2

AIM:- Write a program to sort an array using Selection Sort Technique.

ALGORITHM

1. For (i = 0; i <=n-2 ; i++) min = a[i] for (j = i+1 ; j <=n-1 ; j++)

If (min >a[j])
Swap (min,a[j])
2. Exit selection sort

CODE
#include <stdio.h>
int main() {
int n;
// Input the size of the array
printf("Enter the number of elements in the array: ");
scanf("%d", &n);
int arr[n]; // Declare the array with size n
// Input the elements of the array
printf("Enter %d integers:\n", n);
for (int i = 0; i< n; i++) {
printf("Element %d: ", i + 1);
scanf("%d", &arr[i]);
}

// Selection Sort algorithm

for (int i = 0; i< n - 1; i++) {
// Assume the minimum is the first element of the unsorted part
int minIndex = i;

// Find the index of the minimum element in the unsorted part

for (int j = i + 1; j < n; j++) {
if (arr[j] <arr[minIndex]) {
minIndex = j;
 }
}

// Swap the found minimum element with the first element of the unsorted part
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}

// Display the sorted array

printf("Sorted array: \n");
for (int i = 0; i< n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}

OUTPUT
Enter the number of elements in the array: 5
Enter 5 integers:
Element 1: 34
Element 2: 45
Element 3: 56
Element 4: 67
Element 5: 78
Sorted array:
34 45 56 67 78
 PROGRAM NO: 3

AIM:- Write a Program to sort an array using Quick Sort Technique.

ALGORITHM

1. low =l, high = h, key a[(l+h)/2]

2. Repeat through step 7 while (low <= high)
3. Repeat step 4 while (a[low] < key)
4. low = low +1
5. Repeat step 6 while (a[high] > key)
6. high = high – 1 7. If (low <= high)
a) temp = a[low]
b) a[low] = a[high]
c) a[high] = temp
d) low = low + 1
e) high = high + 1
8. If (l < high) quicksort (a,l,high)
9. If (h>low) quicksort (a,low,h)

CODE

#include <stdio.h>

int main() {
int n;

// Input the size of the array

printf("Enter the number of elements in the array: ");
scanf("%d", &n);

intarr[n]; // Declare the array with size n

// Input the elements of the array

printf("Enter %d integers:\n", n);
for (int i = 0; i< n; i++) {
printf("Element %d: ", i + 1);
scanf("%d", &arr[i]);
}

// Quick Sort algorithm

int stack[n]; // Stack to hold indices for the sub-arrays
int top = -1; // Initialize stack top

// Push the initial indices of the array onto the stack

stack[++top] = 0; // Start index
stack[++top] = n - 1; // End index

// Continue until the stack is empty

while (top >= 0) {
// Pop the end index and start index from the stack
int end = stack[top--];
int start = stack[top--];

// Choose the pivot (last element of the current sub-array)

int pivot = arr[end];
inti = (start - 1); // Index of the smaller element

// Partitioning process
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
i++; // Increment index of smaller element
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap the pivot element with the element at i + 1
int temp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = temp;

// The pivot is now at the correct position

int pivotIndex = i + 1;

// Push the indices of the left sub-array onto the stack

if (pivotIndex - 1 > start) {
stack[++top] = start;
stack[++top] = pivotIndex - 1;
}

// Push the indices of the right sub-array onto the stack

if (pivotIndex + 1 < end) {
stack[++top] = pivotIndex + 1;
stack[++top] = end;
}
}

// Display the sorted array

printf("Sorted array: \n");
for (int i = 0; i< n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

OUTPUT
Enter the number of elements in the array: 5
Enter 5 integers:
Element 1: 98
Element 2: 87
Element 3: 67
Element 4: 76
Element 5: 45
Sorted array:
45 67 76 87 98
 PROGRAM NO: 4

AIM:- Write a program to merge two sorted arrays using Merge Sort Technique.

ALGORITHM

ENTER (a[10],n)
1. Repeat step 2 for i = 0 to (n-1)
2. Input a[i]
3. Return
DISPLAY(c[20],p)
1. Repeat step 2 for k = 0 to p-1
2. Print c[k]
3. Return
MAIN( )
1. Start
2. Input no. of elements in 1st & 2nd array as ‘n’
& ‘m’
3. Enter (a.n)
4. Enter (b,m)
5. i = j = k = 0
6. Repeat step 7 to 12 while ((i < n)&&(j < m))
7. If (a[i] >= b[j]),goto step 9
8. c[k+1] = a[i+1]
9. If a[i] = b[j] ,goto step 11 10. c[k++] = b[j+
+] goto step 7 11. c[k++] = a[i++]
12. j++
13. Repeat step 14 while (i<n)
14. c[k++] = a[i++]
15. Repeat step 16 while m > j
16. c[k++] = b[j++]
17. Display merged arrays as display(c;k)
18. Exit

CODE
#include <stdio.h>
int main() {
int n1, n2;
// Input the size of the first sorted array
printf("Enter the number of elements in the first sorted array: ");
scanf("%d", &n1);
int arr1[n1]; // Declare the first sorted array
// Input the elements of the first sorted array
printf("Enter %d sorted integers for the first array:\n", n1);
for (inti = 0; i< n1; i++) {
printf("Element %d: ", i + 1);
scanf("%d", &arr1[i]);
}
// Input the size of the second sorted array
printf("Enter the number of elements in the second sorted array: ");
scanf("%d", &n2);
int arr2[n2]; // Declare the second sorted array
// Input the elements of the second sorted array
printf("Enter %d sorted integers for the second array:\n", n2);
for (inti = 0; i< n2; i++) {
printf("Element %d: ", i + 1);
scanf("%d", &arr2[i]);
}
// Merge the two sorted arrays
int merged[n1 + n2]; // Array to hold the merged result
inti = 0, j = 0, k = 0;
// Merge the arrays while there are elements in both
while (i< n1 && j < n2) {
if (arr1[i] <= arr2[j]) {
merged[k++] = arr1[i++];
} else {
merged[k++] = arr2[j++];
}
}
// If there are remaining elements in arr1
while (i< n1) {
 merged[k++] = arr1[i++];
}
// If there are remaining elements in arr2
while (j < n2) {
merged[k++] = arr2[j++];
}
// Display the merged sorted array
printf("Merged sorted array:\n");
for (inti = 0; i< n1 + n2; i++) {
printf("%d ", merged[i]);
}
printf("\n");

return 0;
}

OUTPUT
Enter the number of elements in the first sorted array: 4
Enter 4 sorted integers for the first array:
Element 1: 34
Element 2: 54
Element 3: 67
Element 4: 78
Enter the number of elements in the second sorted array: 3
Enter 3 sorted integers for the second array:
Element 1: 4
Element 2: 7
Element 3: 8
Merged sorted array:
4 7 8 34 54 67 78
 PROGRAM NO: 5

AIM:- Write a program to search an element using Linear Search Technique.

ALGORITHM

1. Set k := 1 & loc : = 0

2. Repeat step 3 & 4 while loc : = 0 &k < = n 3. If (item = data[k]) loc : = k
Else
K=k+1
4. If loc : = 0
,then Print “no. not found”
Else
Print “loc is the location of item”
5. Exit

CODE

#include<stdio.h>
int main() {
int n, searchElement, found = 0;

// Input the size of the array

printf("Enter the number of elements in the array: ");
scanf("%d", &n);

int arr[n]; // Declare the array with size n

// Input the elements of the array

printf("Enter %d integers:\n", n);
for (int i = 0; i< n; i++) {
printf("Element %d: ", i + 1);
scanf("%d", &arr[i]);
}
 // Input the element to search for
printf("Enter the element to search for: ");
scanf("%d", &searchElement);

// Perform Linear Search

for (int i = 0; i< n; i++) {
if (arr[i] == searchElement) {
printf("Element %d found at index %d.\n", searchElement, i);
found = 1; // Set found flag
break; // Exit the loop if found
}
}

if (!found) {
printf("Element %d not found in the array.\n", searchElement);
}

return 0;
}

OUTPUT

Enter the number of elements in the array: 7

Enter 7 integers:
Element 1: 9
Element 2: 8
Element 3: 7
Element 4: 6
Element 5: 5
Element 6: 4
Element 7: 3
Enter the element to search for: 6
Element 6 found at index 3.
 PROGRAM NO: 6

AIM:-Write programs for finding the element in the array using the Binary Search Technique.

ALGORITHM

1. low = 1,high = n
2. Repeat step 3 to 5 while low <= high
3. mid = (low + high)
4. If a[mid] = x
Print “ found at mid”
Return
5. If (a[mid] < x) low = mid + 1 Else
High = mid – 1
6. Print “x not found”
7. Exit

CODE

#include <stdio.h>

int main() {
int n, searchElement, left, right, middle;

// Input the size of the array

printf("Enter the number of elements in the sorted array: ");
scanf("%d", &n);

intarr[n]; // Declare the array with size n

// Input the elements of the array

printf("Enter %d sorted integers:\n", n);
for (inti = 0; i< n; i++) {
printf("Element %d: ", i + 1);
scanf("%d", &arr[i]);
}

// Input the element to search for

printf("Enter the element to search for: ");
scanf("%d", &searchElement);

// Binary Search Implementation

left = 0;
right = n - 1;
int found = 0; // Flag to check if the element is found

while (left <= right) {

middle = left + (right - left) / 2; // Calculate the middle index

if (arr[middle] == searchElement) {
printf("Element %d found at index %d.\n", searchElement, middle);
found = 1; // Set found flag
break; // Exit the loop if found
} else if (arr[middle] <searchElement) {
left = middle + 1; // Search in the right half
} else {
right = middle - 1; // Search in the left half
}
}
if (!found) {
printf("Element %d not found in the array.\n", searchElement);
}
return 0;
}

OUTPUT
Enter the number of elements in the sorted array: 4
Enter 4 sorted integers:
Element 1: 45
Element 2: 56
Element 3: 76
Element 4: 87
Enter the element to search for: 46
Element 46 not found in the array.
 PROGRAM NO: 7

AIM:- Write a menu driven program to implement stack using an Array.

ALGORITHM

INSERTION
PUSH(item)
1. If (item = max of stack)
Print “overflow”
Return
2. top = top + 1
3. stack[top] = item 4. Return
DELETION
POP(item)
1. If (top = - 1)
Print “underflow”
Return
2. Item = stack[top]
3. top = top – 1
4. Return
DISPLAY
1. If top = - 1
Print “underflow”
2. repeat step 3 for i = top to i >= 0
3. Print stack[i] 4. Return

CODE

#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Maximum size of the stack
// Stack structure
struct Stack {
int arr[MAX];
int top;
};
// Function to initialize the stack
void initStack(struct Stack* stack) {
stack->top = -1; // Stack is initially empty
}
// Function to check if the stack is full
int isFull(struct Stack* stack) {
return stack->top == MAX - 1;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// Function to push an element onto the stack
void push(struct Stack* stack, int value) {
if (isFull(stack)) {
printf("Stack Overflow! Cannot push %d\n", value);
} else {
stack->arr[++stack->top] = value;
printf("%d pushed onto stack.\n", value);
}
}
// Function to pop an element from the stack
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow! Cannot pop from an empty stack.\n");
return -1; // Return -1 to indicate stack is empty
} else {
return stack->arr[stack->top--];
}
}

// Function to display the stack

void display(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
 } else {
printf("Stack elements: ");
for (inti = stack->top; i>= 0; i--) {
printf("%d ", stack->arr[i]);
}
printf("\n");
}
}
// Main function
int main() {
struct Stack stack;
initStack(&stack);
int choice, value;
do {
printf("\nMenu:\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Display Stack\n");
printf("4. Check if Stack is Empty\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to push: ");
scanf("%d", &value);
push(&stack, value);
break;
case 2:
value = pop(&stack);
if (value != -1) {
printf("%d popped from stack.\n", value);
}
break;
case 3:
display(&stack);
 break;
case 4:
if (isEmpty(&stack)) {
printf("Stack is empty.\n");
} else {
printf("Stack is not empty.\n");
}
break;
case 5:
printf("Exiting...\n");
break;
default:
printf("Invalid choice! Please try again.\n");
}
} while (choice != 5);
return 0;
}

OUTPUT

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 1
Enter value to push: 10
10 pushed onto stack.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 1
Enter value to push: 20
20 pushed onto stack.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 3
Stack elements: 20 10

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 2
20 popped from stack.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 3
Stack elements: 10

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 4
Stack is not empty.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 2
10 popped from stack.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 4
Stack is empty.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 5
Exiting...
 PROGRAM NO: 8

AIM:- Write a menu driven program to implement stack using Linked List.

ALGORITHM
PUSH( )
1. t = newnode( )
2. Enter info to be inserted
3. Read n
4. t info = n
5. t next = top
6. top = t
7. Return
POP( )
1. If (top = NULL)
Print “ underflow”
Return
2. x = top
3. top = top next
4. delnode(x)
5. Return

CODE
#include <stdio.h>
#include <stdlib.h>

// Node structure for the linked list

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

// Stack structure
struct Stack {
struct Node* top;
};
// Function to initialize the stack
void initStack(struct Stack* stack) {
stack->top = NULL; // Stack is initially empty
}

// Function to check if the stack is empty

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

// Function to push an element onto the stack

void push(struct Stack* stack, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed! Cannot push %d\n", value);
return;
}
newNode->data = value;
newNode->next = stack->top; // Link new node to the previous top
stack->top = newNode; // Update top to new node
printf("%d pushed onto stack.\n", value);
}

// Function to pop an element from the stack

int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow! Cannot pop from an empty stack.\n");
return -1; // Return -1 to indicate stack is empty
}
else {
struct Node* temp = stack->top; // Get the top node
int poppedValue = temp->data; // Store the value to return
stack->top = stack->top->next; // Update top to the next node
free(temp); // Free the memory of the popped node
return poppedValue;
}
}

// Function to display the stack

void display(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
} else {
struct Node* current = stack->top;
printf("Stack elements: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
}

// Main function
int main() {
struct Stack stack;
initStack(&stack);
int choice, value;
do {
printf("\nMenu:\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Display Stack\n");
printf("4. Check if Stack is Empty\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter value to push: ");
scanf("%d", &value);
push(&stack, value);
 break;
case 2:
value = pop(&stack);
if (value != -1) {
printf("%d popped from stack.\n", value);
}
break;
case 3:
display(&stack);
break;
case 4:
if (isEmpty(&stack)) {
printf("Stack is empty.\n");
} else {
printf("Stack is not empty.\n");
}
break;
case 5:
printf("Exiting...\n");
break;
default:
printf("Invalid choice! Please try again.\n");
}
} while (choice != 5);
return 0;
}

OUTPUT
Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 1
Enter value to push: 23
23 pushed onto stack.
Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 1
Enter value to push: 60
60 pushed onto stack.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 3
Stack elements: 60 23

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 2
60 popped from stack.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 3
Stack elements: 23
Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 4
Stack is not empty.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 2
23 popped from stack.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 4
Stack is empty.

Menu:
1. Push
2. Pop
3. Display Stack
4. Check if Stack is Empty
5. Exit
Enter your choice: 5
Exiting...
 PROGRAM NO: 9

AIM:-Write a program to evaluate postfix expression.

ALGORITHM
P postfix expression
1. Add a right parenthesis “)” at the end of P
2. Scan P from left to right and repeat steps 3 & 4
until sentinel “)” is encountered
3. If an operand is encountered, put it on stack
4. 4. If an operator is encountered , then:
a) Remove the top two elements of stack , where A is the top element &
B is the next to top element b) Evaluate B A
c) Place the result of (b) back on stack
5. Set value equal to the top element on stack
6. Exit

CODE
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAX 100 // Maximum size of the stack

// Stack structure
struct Stack {
int arr[MAX];
int top;
};

// Function to initialize the stack

void initStack(struct Stack* stack) {
stack->top = -1; // Stack is initially empty
}
// Function to check if the stack is full
int isFull(struct Stack* stack) {
return stack->top == MAX - 1;
}

// Function to check if the stack is empty

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

// Function to push an element onto the stack

void push(struct Stack* stack, int value) {
if (isFull(stack)) {
printf("Stack Overflow! Cannot push %d\n", value);
} else {
stack->arr[++stack->top] = value;
}
}

// Function to pop an element from the stack

int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow! Cannot pop from an empty stack.\n");
return -1; // Return -1 to indicate stack is empty
} else {
return stack->arr[stack->top--];
}
}

// Function to evaluate a postfix expression

int evaluatePostfix(char* expression) {
struct Stack stack;
initStack(&stack);
int i = 0;

while (expression[i] != '\0') {

// Skip spaces
if (expression[i] == ' ') {
i++;
continue;
}

// If the character is a digit, push it to the stack

if (isdigit(expression[i])) {
int num = 0;
while (isdigit(expression[i])) {
num = num * 10 + (expression[i] - '0');
i++;
}
push(&stack, num);
} else {
// Operator handling
int rightOperand = pop(&stack);
int leftOperand = pop(&stack);

if (leftOperand == -1 || rightOperand == -1) {

return -1; // Error case if stack underflows
}

int result;
switch (expression[i]) {
case '+':
result = leftOperand + rightOperand;
break;
case '-':
result = leftOperand - rightOperand;
break;
case '*':
result = leftOperand * rightOperand;
break;
case '/':
if (rightOperand == 0) {
printf("Error: Division by zero.\n");
return -1; // Error condition
 }
result = leftOperand / rightOperand;
break;
default:
printf("Error: Invalid operator %c\n", expression[i]);
return -1; // Error condition
}
push(&stack, result);
}
i++;
}

return pop(&stack); // The final result will be the only element left in the stack
}

// Main function
int main() {
char expression[MAX];

printf("Enter a postfix expression (e.g., 5 6 2 + * 12 4 / -): ");

fgets(expression, sizeof(expression), stdin);
// Remove newline character from the input
expression[strcspn(expression, "\n")] = 0;

int result = evaluatePostfix(expression);

if (result != -1) {
printf("Result: %d\n", result);
}

return 0;
}

OUTPUT
Enter a postfix expression (e.g., 5 6 2 + * 12 4 / -): 5 6 2 + * 12 4 / -
Result: 37
 PROGRAM NO: 10

AIM:- Write a program to convert an infix to postfix expression.

ALGORITHM
Q arithmetic expression
P postfix expression
1. Push “(“ onto stack, and add “)” to the end of Q
2. Scan Q from left to right and repeat steps 3 to 6 for each element of
Q untill the stack is empty
3. If an operand is encountered , add it to P
4. If a left parenthesis is encountered, push it onto stack 5. If an
operator is encountered , then:
(a) Repeatedly pop from stack and add to P each operator
which has the same precedence as or higher precedence
than
(b) Add to stack
6. If a right parenthesis is encountered, then:
(a) Repeatedly pop from stack and add to P each operator until a left
parenthesis is encountered (b) Remove the left parenthesis
7. Exit
CODE
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAX 100 // Maximum size for the stack and expression

// Stack structure
struct Stack {
char arr[MAX];
int top;
};

// Function to initialize the stack

void initStack(struct Stack* stack) {
stack->top = -1; // Stack is initially empty
}

// Function to check if the stack is full

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

// Function to check if the stack is empty

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

// Function to push an element onto the stack

void push(struct Stack* stack, char value) {
if (isFull(stack)) {
printf("Stack Overflow! Cannot push %c\n", value);
} else {
stack->arr[++stack->top] = value;
}
}

// Function to pop an element from the stack

char pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow! Cannot pop from an empty stack.\n");
return '\0'; // Return null character to indicate stack is empty
} else {
return stack->arr[stack->top--];
}
}

// Function to peek the top element of the stack

char peek(struct Stack* stack) {
if (!isEmpty(stack)) {
return stack->arr[stack->top];
}
return '\0'; // Return null character if stack is empty
}

// Function to check operator precedence

int precedence(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return 0;
}
}

// Function to convert infix expression to postfix

void infixToPostfix(char* infix, char* postfix) {
struct Stack stack;
initStack(&stack);
int i = 0, j = 0;

while (infix[i] != '\0') {

if (isspace(infix[i])) {
i++; // Skip whitespace
continue;
}

// If the character is an operand, add it to the output

if (isalnum(infix[i])) {
postfix[j++] = infix[i];
}
// If the character is '(', push it to the stack
else if (infix[i] == '(') {
push(&stack, infix[i]);
}
// If the character is ')', pop from stack until '(' is found
else if (infix[i] == ')') {
while (!isEmpty(&stack) && peek(&stack) != '(') {
postfix[j++] = pop(&stack);
}
pop(&stack); // Remove '(' from stack
}
// The character is an operator
else {
while (!isEmpty(&stack) && precedence(peek(&stack)) >= precedence(infix[i])) {
postfix[j++] = pop(&stack);
}
push(&stack, infix[i]);
}
i++;
}

// Pop all the operators from the stack

while (!isEmpty(&stack)) {
postfix[j++] = pop(&stack);
}

postfix[j] = '\0'; // Null-terminate the postfix expression

}

// Main function
int main() {
char infix[MAX], postfix[MAX];
 printf("Enter an infix expression (e.g., A + B * C): ");
fgets(infix, sizeof(infix), stdin);
infix[strcspn(infix, "\n")] = 0; // Remove trailing newline

infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);

return 0;
}

OUTPUT
Enter an infix expression (e.g., A + B * C): A + B * C
Postfix expression: ABC*+
 PROGRAM NO: 11

AIM:- Write a menu driven program to implement queue using Linked List.

ALGORITHM
CREATE
1. t = new node
2. Enter info to be inserted
3. Read n
4. t info = n
5. t next = front 6. front = t
INSERTION
1. r next = t
2. t next = NULL
3. Return
DELETION
1. x = front
2. front = front next
3. delnode(x) 4. Return
DISPLAY
1. If (front = NULL)
Print “ empty queue”
Return
Else
P = start
Repeat until (p<> NULL)
Print p info
P = p next
Return
Program

CODE
#include <stdio.h>
#include <stdlib.h>

// Structure for a queue node

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

// Structure for the queue

struct Queue {
struct Node* front;
struct Node* rear;
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to initialize the queue

struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = queue->rear = NULL;
return queue;
}

// Function to check if the queue is empty

int isEmpty(struct Queue* queue) {
return queue->front == NULL;
}

// Function to add an element to the queue

void enqueue(struct Queue* queue, int data) {
struct Node* newNode = createNode(data);
if (queue->rear == NULL) {
queue->front = queue->rear = newNode;
return;
}
queue->rear->next = newNode;
queue->rear = newNode;
printf("%d enqueued to queue\n", data);
}

// Function to remove an element from the queue

int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty! Cannot dequeue.\n");
return -1; // Error condition
}
struct Node* temp = queue->front;
int data = temp->data;
queue->front = queue->front->next;

// If the queue becomes empty, set rear to NULL

if (queue->front == NULL) {
queue->rear = NULL;
}
free(temp);
printf("%d dequeued from queue\n", data);
return data;
}

// Function to display the queue

void displayQueue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty!\n");
 return;
}
struct Node* temp = queue->front;
printf("Queue: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

// Main function
int main() {
struct Queue* queue = createQueue();
int choice, data;

while (1) {
printf("\nMenu:\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display Queue\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter the value to enqueue: ");
scanf("%d", &data);
enqueue(queue, data);
break;
case 2:
dequeue(queue);
 break;
case 3:
displayQueue(queue);
break;
case 4:
printf("Exiting the program.\n");
free(queue); // Free the queue structure
exit(0);
default:
printf("Invalid choice! Please try again.\n");
}
}
return 0;
}

OUTPUT
Menu:
1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 1
Enter the value to enqueue: 10
10 enqueued to queue

Menu:
1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 1
Enter the value to enqueue: 20
20 enqueued to queue
Menu:
1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 3
Queue: 10 20

Menu:
1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 2
10 dequeued from queue

Menu:
1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 3
Queue: 20

Menu:
1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 4
Exiting the program.
 PROGRAM NO: 12

AIM:- Write a Menu Driven Program to implement various operation of Singly Linked List.

ALGORITHM
1. t = newmode( )
2. Enter info to be inserted
3. Read n
4. t info = n
5. t next = start
6. Start = t
INSERTION
BEGIN
1. t next = start
2. start = t
Return
MIDDLE
1. Enter info of the node after which new node
to be inserted
2. Read x
3. p = start
4. Repeat step 5 until p info <> x
5. p = p next
6. t next = p next
7. p next = t
8. Return
LAST
1. p = start
2. Repeat step 3 until p next NULL
3. p = p next
4. t next = NULL
5. p next = t
6. Return
DELETION
BEGIN
1. x = start
2. start = start next
3. delnode(x)
MIDDLE
1. Enter the info of node to be deleted
2. Read n
3. p = start
4. c = start
5. while (c info <> NULL) p = c c = c
next 6. p next = c next
7. delnode ( c )
8. Return
LAST
1. p = start c = start
2. while (c next <>
NULL)
p = c c = c next 3. p
next = c next
4. delnode ( c)
5. Return
TRAVERSAL
1. p = start
2. while (p <> NULL) Print p info
P=p next
3. Return

CODE
#include <stdio.h>
#include <stdlib.h>

// Structure for a linked list node

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

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to insert a node at the beginning

void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
printf("%d inserted at the beginning.\n", data);
}

// Function to insert a node at the end

void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
printf("%d inserted at the end.\n", data);
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
printf("%d inserted at the end.\n", data);
}

// Function to delete a node by value

void deleteNode(struct Node** head, int data) {
struct Node* temp = *head, *prev = NULL;

// If the head node itself holds the key to be deleted

if (temp != NULL && temp->data == data) {
 *head = temp->next; // Changed head
free(temp); // Free old head
printf("%d deleted from the list.\n", data);
return;
}

// Search for the key to be deleted

while (temp != NULL && temp->data != data) {
prev = temp;
temp = temp->next;
}

// If key was not present in the linked list

if (temp == NULL) {
printf("%d not found in the list.\n", data);
return;
}

// Unlink the node from linked list

prev->next = temp->next;
free(temp); // Free memory
printf("%d deleted from the list.\n", data);
}

// Function to display the linked list

void displayList(struct Node* head) {
if (head == NULL) {
printf("The list is empty.\n");
return;
}
struct Node* temp = head;
printf("Linked List: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

// Function to search for an element in the list

void searchElement(struct Node* head, int data) {
struct Node* temp = head;
while (temp != NULL) {
if (temp->data == data) {
printf("%d found in the list.\n", data);
return;
}
temp = temp->next;
}
printf("%d not found in the list.\n", data);
}

// Main function
int main() {
struct Node* head = NULL;
int choice, data;

while (1) {
printf("\nMenu:\n");
printf("1. Insert at Beginning\n");
printf("2. Insert at End\n");
printf("3. Delete Node\n");
printf("4. Display List\n");
printf("5. Search Element\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter the value to insert at the beginning: ");
scanf("%d", &data);
insertAtBeginning(&head, data);
break;
 case 2:
printf("Enter the value to insert at the end: ");
scanf("%d", &data);
insertAtEnd(&head, data);
break;
case 3:
printf("Enter the value to delete: ");
scanf("%d", &data);
deleteNode(&head, data);
break;
case 4:
displayList(head);
break;
case 5:
printf("Enter the value to search: ");
scanf("%d", &data);
searchElement(head, data);
break;
case 6:
printf("Exiting the program.\n");
// Free the linked list
while (head != NULL) {
struct Node* temp = head;
head = head->next;
free(temp);
}
exit(0);
}
}
}

OUTPUT

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 1
Enter the value to insert at the beginning: 10
10 inserted at the beginning.

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 2
Enter the value to insert at the end: 20
20 inserted at the end.

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 4
Linked List: 10 -> 20 -> NULL

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 3
Enter the value to delete: 10
10 deleted from the list.

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 4
Linked List: 20 -> NULL

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 5
Enter the value to search: 20
20 found in the list.

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 6
Exiting the program.
 PROGRAM NO: 13

AIM:-Write a Menu Driven Program to implement various operation of Doubly Linked List.

ALGORITHM
1. t = new node
2. Enter “the info to be inserted”
3. Read n
4. t info = n
5. t next = NULL 6. t prev NULL
INSERTION
BEGIN
1. If start = NULL start = t
2. else
t next = NULL t
next prev = t
start = t
Return
MIDDLE
1. Print “ enter info of the node after which you
want to insert”
2. Read x
3. p = start
4. Repeat while p<> NULL If (p info = n) t
next = p next p next = t t
prev = p p next prev = t
Return
Else
P = p next
5. Print x not found
t next = NULL p
next = t
DELETION
BEGIN
1. p = start
2. p next prev = NULL
3. start = p next
4. start = p next
5. delnode(p)
6. Return
MIDDLE
1. Enter “info of the node to be deleted”
2. Read x
3. p = start
4. Repeat until p<> NULL If(p info = x)
p prev next = p
next p next prev = p
prev delnode(p) Return
Else
P = p next
5. Print “x not found”
LAST
1. P = start
2. Repeat while p<> NULL
If(p next = NULL)
Delnode(p)
3. Return
DISPLAY
1. p = start
2. Repeat while p <> NULL
Print p info
P=p next

CODE
#include <stdio.h>
#include <stdlib.h>

// Structure for a doubly linked list node

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

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}

// Function to insert a node at the beginning

void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
printf("%d inserted at the beginning.\n", data);
}

// Function to insert a node at the end

void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
printf("%d inserted at the end.\n", data);
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
 printf("%d inserted at the end.\n", data);
}

// Function to delete a node by value

void deleteNode(struct Node** head, int data) {
struct Node* temp = *head;

// If the list is empty

if (temp == NULL) {
printf("List is empty. Cannot delete %d.\n", data);
return;
}

// If the head node itself holds the key to be deleted

if (temp != NULL && temp->data == data) {
*head = temp->next; // Changed head
if (*head != NULL) {
(*head)->prev = NULL; // Update previous of new head
}
free(temp); // Free old head
printf("%d deleted from the list.\n", data);
return;
}

// Search for the key to be deleted

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

// If key was not present in the linked list

if (temp == NULL) {
printf("%d not found in the list.\n", data);
return;
}

// Unlink the node from linked list

if (temp->next != NULL) {
 temp->next->prev = temp->prev;
}
if (temp->prev != NULL) {
temp->prev->next = temp->next;
}
free(temp); // Free memory
printf("%d deleted from the list.\n", data);
}

// Function to display the doubly linked list

void displayList(struct Node* head) {
if (head == NULL) {
printf("The list is empty.\n");
return;
}
struct Node* temp = head;
printf("Doubly Linked List: ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

// Function to search for an element in the list

void searchElement(struct Node* head, int data) {
struct Node* temp = head;
while (temp != NULL) {
if (temp->data == data) {
printf("%d found in the list.\n", data);
return;
}
temp = temp->next;
}
printf("%d not found in the list.\n", data);
}
// Main function
int main() {
struct Node* head = NULL;
int choice, data;

while (1) {
printf("\nMenu:\n");
printf("1. Insert at Beginning\n");
printf("2. Insert at End\n");
printf("3. Delete Node\n");
printf("4. Display List\n");
printf("5. Search Element\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter the value to insert at the beginning: ");
scanf("%d", &data);
insertAtBeginning(&head, data);
break;
case 2:
printf("Enter the value to insert at the end: ");
scanf("%d", &data);
insertAtEnd(&head, data);
break;
case 3:
printf("Enter the value to delete: ");
scanf("%d", &data);
deleteNode(&head, data);
break;
case 4:
displayList(head);
break;
case 5:
printf("Enter the value to search: ");
 scanf("%d", &data);
searchElement(head, data);
break;
case 6:
printf("Exiting the program.\n");
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}

OUTPUT

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 1
Enter the value to insert at the beginning: 10
10 inserted at the beginning.

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 2
Enter the value to insert at the end: 20
20 inserted at the end.
Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 4
Doubly Linked List: 10 <-> 20 <-> NULL

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 3
Enter the value to delete: 10
10 deleted from the list.

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 4
Doubly Linked List: 20 <-> NULL

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 5
Enter the value to search: 20
20 found in the list.

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Display List
5. Search Element
6. Exit
Enter your choice: 6
Exiting the program.
 PROGRAM NO: 14

AIM:- Write a program to implement Binary Search Tree.

ALGORITHM
INSERTION
1. t = newnode
2. t -> info = n
3. t -> left = t -> right = NULL 4. If (root =
NULL) root = t return 5. ptr = root
6. Repeat step 7 until ptr = NULL
7. If (ptr -> info > n)
If (ptr -> left = NULL)
Ptr ->left = t
Return
Else
Ptr = ptr -> left
Else
If (ptr ->right = NULL)
Ptr ->right = t
Return
Else
Ptr = ptr -> right
DELETION
1. If (root = NULL)
Print “Empty tree “
Return
2. ptr = root, par = NULL
3. Repeat step 4 & 5 until (ptr info = n or ptr
= NULL)
4. par = ptr
5. If (ptr-> info > n) ptr = ptr ->left Else
Ptr = ptr ->right 6.
If ptr = NULL
print “ no. not present”
 CODE
#include <stdio.h>
#include <stdlib.h>

// Structure for a BST node

struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Function to insert a node into the BST

struct Node* insert(struct Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}

// Function to search for a value in the BST

struct Node* search(struct Node* root, int data) {
if (root == NULL || root->data == data) {
return root;
 }
if (data < root->data) {
return search(root->left, data);
}
return search(root->right, data);
}

// Function to find the minimum value node in the BST

struct Node* findMin(struct Node* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}

// Function to delete a node from the BST

struct Node* deleteNode(struct Node* root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// Node with only one child or no child
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}

// Node with two children: Get the inorder successor (smallest in the right subtree)
 struct Node* temp = findMin(root->right);
root->data = temp->data; // Copy the inorder successor's content to this node
root->right = deleteNode(root->right, temp->data); // Delete the inorder successor
}
return root;
}

// Function to perform in-order traversal of the BST

void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}

// Main function
int main() {
struct Node* root = NULL;
int choice, data;

while (1) {
printf("\nMenu:\n");
printf("1. Insert\n");
printf("2. Search\n");
printf("3. Delete\n");
printf("4. In-order Traversal\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter the value to insert: ");
scanf("%d", &data);
root = insert(root, data);
printf("%d inserted into the BST.\n", data);
 break;
case 2:
printf("Enter the value to search: ");
scanf("%d", &data);
struct Node* foundNode = search(root, data);
if (foundNode != NULL) {
printf("%d found in the BST.\n", data);
} else {
printf("%d not found in the BST.\n", data);
}
break;
case 3:
printf("Enter the value to delete: ");
scanf("%d", &data);
root = deleteNode(root, data);
printf("%d deleted from the BST.\n", data);
break;
case 4:
printf("In-order Traversal: ");
inorderTraversal(root);
printf("\n");
break;
case 5:
printf("Exiting the program.\n");
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}

OUTPUT
Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 1
Enter the value to insert: 50
50 inserted into the BST.

Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 1
Enter the value to insert: 25
30 inserted into the BST.

Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 1
Enter the value to insert: 73
70 inserted into the BST.

Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 4
In-order Traversal: 25 50 73

Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 2
Enter the value to search: 25
30 found in the BST.

Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 3
Enter the value to delete: 25
30 deleted from the BST.

Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 4
In-order Traversal: 50 73

Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 5
Exiting the program.
 PROGRAM NO: 15

AIM:-Write a program to simulate various Tree Traversal Techniques.

ALGORITHM
Preorder(root)
If root = null then exit
Process root->info
Preorder root->left;
Preorder root->right
Exit
Inorder(root)
If root = null then exit
Inorder root->left
Process root->info
Inorder root->right
Exit
Postorder(root)
If root = null then exit
Postorder root->left
Postorder root->right
Postorder root->info exit

CODE
#include <stdio.h>
#include <stdlib.h>

// Structure for a binary tree node

struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// In-order Traversal (Left, Root, Right)

void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}

// Pre-order Traversal (Root, Left, Right)

void preorderTraversal(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}

// Post-order Traversal (Left, Right, Root)

void postorderTraversal(struct Node* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
}
// Level-order Traversal (Breadth-First Search)
void levelOrderTraversal(struct Node* root) {
if (root == NULL) {
return;
}

struct Node** queue = (struct Node**)malloc(100 * sizeof(struct Node*)); // Simple queue

implementation
int front = 0, rear = 0;

queue[rear++] = root;

while (front < rear) {

struct Node* current = queue[front++];
printf("%d ", current->data);

if (current->left != NULL) {
queue[rear++] = current->left;
}
if (current->right != NULL) {
queue[rear++] = current->right;
}
}

free(queue); // Free the allocated memory for the queue

}

// Main function
int main() {
// Creating a simple binary tree
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
 root->right->left = createNode(6);
root->right->right = createNode(7);

printf("In-order Traversal: ");

inorderTraversal(root);
printf("\n");

printf("Pre-order Traversal: ");

preorderTraversal(root);
printf("\n");

printf("Post-order Traversal: ");

postorderTraversal(root);
printf("\n");

printf("Level-order Traversal: ");

levelOrderTraversal(root);
printf("\n");

// Free allocated memory (not shown for simplicity)

return 0;
}

OUTPUT

In-order Traversal: 4 2 5 1 6 3 7
Pre-order Traversal: 1 2 4 5 3 6 7
Post-order Traversal: 4 5 2 6 7 3 1
Level-order Traversal: 1 2 3 4 5 6 7
 ADDED PRACTICALS

PROGRAM NO: 1

AIM:- Write a program to perform following operations on matrix using functions - Addition,
Subtraction, Multiplication, and Transpose.

ALGORITHM
Matmul(a,b,m,n,p)
1 for(i=1 to m)
2 for(j = 1 to p)
3 c[i][j] =0;
4 for(k= 1to n)
5 c[i][j] = c[i][j]+a[i][j]*b[i][j]
6 exit

CODE

#include <stdio.h>
#define MAX 10 // Maximum size of the matrix

// Function prototypes
void inputMatrix(int matrix[MAX][MAX], int rows, int cols);
void displayMatrix(int matrix[MAX][MAX], int rows, int cols);
void addMatrices(int a[MAX][MAX], int b[MAX][MAX], int result[MAX][MAX], int rows, int cols);
void subtractMatrices(int a[MAX][MAX], int b[MAX][MAX], int result[MAX][MAX], int rows, int
cols);
void multiplyMatrices(int a[MAX][MAX], int b[MAX][MAX], int result[MAX][MAX], int rowsA, int
colsA, int colsB);
void transposeMatrix(int matrix[MAX][MAX], int result[MAX][MAX], int rows, int cols);

int main() {
int a[MAX][MAX], b[MAX][MAX], result[MAX][MAX];
int rowsA, colsA, rowsB, colsB;
int choice;

// Input for the first matrix

printf("Enter the number of rows and columns for the first matrix: ");
scanf("%d %d", &rowsA, &colsA);
printf("Enter elements of the first matrix:\n");
inputMatrix(a, rowsA, colsA);

// Input for the second matrix

printf("Enter the number of rows and columns for the second matrix: ");
scanf("%d %d", &rowsB, &colsB);
printf("Enter elements of the second matrix:\n");
inputMatrix(b, rowsB, colsB);

do {
printf("\nMenu:\n");
printf("1. Add Matrices\n");
printf("2. Subtract Matrices\n");
printf("3. Multiply Matrices\n");
printf("4. Transpose First Matrix\n");
printf("5. Transpose Second Matrix\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
if (rowsA == rowsB && colsA == colsB) {
addMatrices(a, b, result, rowsA, colsA);
printf("Result of Addition:\n");
displayMatrix(result, rowsA, colsA);
} else {
printf("Matrices must be of the same dimensions for addition.\n");
}
break;
case 2:
if (rowsA == rowsB && colsA == colsB) {
subtractMatrices(a, b, result, rowsA, colsA);
printf("Result of Subtraction:\n");
 displayMatrix(result, rowsA, colsA);
} else {
printf("Matrices must be of the same dimensions for subtraction.\n");
}
break;
case 3:
if (colsA == rowsB) {
multiplyMatrices(a, b, result, rowsA, colsA, colsB);
printf("Result of Multiplication:\n");
displayMatrix(result, rowsA, colsB);
} else {
printf("Number of columns in the first matrix must equal the number of rows in the second
matrix for multiplication.\n");
}
break;
case 4:
transposeMatrix(a, result, rowsA, colsA);
printf("Transpose of First Matrix:\n");
displayMatrix(result, colsA, rowsA);
break;
case 5:
transposeMatrix(b, result, rowsB, colsB);
printf("Transpose of Second Matrix:\n");
displayMatrix(result, colsB, rowsB);
break;
case 6:
printf("Exiting the program.\n");
break;
default:
printf("Invalid choice. Please try again.\n");
}
} while (choice != 6);

return 0;
}
// Function to input a matrix
void inputMatrix(int matrix[MAX][MAX], int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
printf("Enter element [%d][%d]: ", i, j);
scanf("%d", &matrix[i][j]);
}
}
}

// Function to display a matrix

void displayMatrix(int matrix[MAX][MAX], int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}

// Function to add two matrices

void addMatrices(int a[MAX][MAX], int b[MAX][MAX], int result[MAX][MAX], int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result[i][j] = a[i][j] + b[i][j];
}
}
}

// Function to subtract two matrices

void subtractMatrices(int a[MAX][MAX], int b[MAX][MAX], int result[MAX][MAX], int rows, int
cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result[i][j] = a[i][j] - b[i][j];
}
 }
}

// Function to multiply two matrices

void multiplyMatrices(int a[MAX][MAX], int b[MAX][MAX], int result[MAX][MAX], int rowsA, int
colsA, int colsB) {
for (int i = 0; i < rowsA; i++) {
for (int j = 0; j < colsB; j++) {
result[i][j] = 0;
for (int k = 0; k < colsA; k++) {
result[i][j] += a[i][k] * b[k][j];
}
}
}
}

// Function to transpose a matrix

void transposeMatrix(int matrix[MAX][MAX], int result[MAX][MAX], int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result[j][i] = matrix[i][j];
}
}
}

OUTPUT

Enter the number of rows and columns for the first matrix: 2 2
Enter elements of the first matrix:
Enter element [0][0]: 1
Enter element [0][1]: 2
Enter element [1][0]: 3
Enter element [1][1]: 4

Enter the number of rows and columns for the second matrix: 2 2
Enter elements of the second matrix:
Enter element [0][0]: 5
Enter element [0][1]: 6
Enter element [1][0]: 7
Enter element [1][1]: 8

Menu:
1. Add Matrices
2. Subtract Matrices
3. Multiply Matrices
4. Transpose First Matrix
5. Transpose Second Matrix
6. Exit
Enter your choice: 1

Result of Addition:
68
10 12

Menu:
1. Add Matrices
2. Subtract Matrices
3. Multiply Matrices
4. Transpose First Matrix
5. Transpose Second Matrix
6. Exit
Enter your choice: 2

Result of Subtraction:
-4 -4
-4 -4

Menu:
1. Add Matrices
2. Subtract Matrices
3. Multiply Matrices
4. Transpose First Matrix
5. Transpose Second Matrix
6. Exit
Enter your choice: 3

Result of Multiplication:
19 22
43 50

Menu:
1. Add Matrices
2. Subtract Matrices
3. Multiply Matrices
4. Transpose First Matrix
5. Transpose Second Matrix
6. Exit
Enter your choice: 4

Transpose of First Matrix:

13
24

Menu:
1. Add Matrices
2. Subtract Matrices
3. Multiply Matrices
4. Transpose First Matrix
5. Transpose Second Matrix
6. Exit
Enter your choice: 5

Transpose of Second Matrix:

57
68

Menu:
1. Add Matrices
2. Subtract Matrices
3. Multiply Matrices
4. Transpose First Matrix
5. Transpose Second Matrix
6. Exit
Enter your choice: 6

Exiting the program.

 PROGRAM NO: 2
AIM:-Write a program to sort an array using Bucket Sort Technique.

ALGORITHM
1. Initialize Buckets:
 Determine the number of buckets based on the array size.
 Create an array of empty buckets.
2. Distribute Elements into Buckets:
 Calculate the index for each element in the array by mapping the element’s value to its
corresponding bucket.
 Place each element in its respective bucket.
3. Sort Each Bucket:
1. Sort each bucket individually. Use a sorting algorithm like Insertion Sort for each bucket,
which is efficient for small sizes.
4. Concatenate Buckets:
2. Combine all sorted buckets to obtain the final sorted array.

CODE
#include <stdio.h>
#include <stdlib.h>
#define MAX 10 // Maximum number of elements in the array
#define BUCKETS 5 // Number of buckets
void bucketSort(float arr[], int n);
void insertionSort(float arr[], int n);
void printArray(float arr[], int n);
int main() {
float arr[MAX] = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
int n = 7; // Number of elements in the array

printf("Original Array: \n");

printArray(arr, n);

bucketSort(arr, n);

printf("\nSorted Array: \n");

printArray(arr, n);

return 0;
}
void bucketSort(float arr[], int n) {
// Create empty buckets
float buckets[BUCKETS][MAX];
int bucketCount[BUCKETS] = {0}; // To keep track of the number of elements in each bucket

// Distribute array elements into buckets

for (int i = 0; i< n; i++) {
int bucketIndex = (int)(arr[i] * BUCKETS); // Map element to the appropriate bucket
buckets[bucketIndex][bucketCount[bucketIndex]++] = arr[i];
}

// Sort each bucket and concatenate them

int index = 0;
for (int i = 0; i< BUCKETS; i++) {
if (bucketCount[i] > 0) {
insertionSort(buckets[i], bucketCount[i]); // Sort the bucket
for (int j = 0; j <bucketCount[i]; j++) {
arr[index++] = buckets[i][j]; // Place sorted elements back into the array
}
}
}
}

// Insertion Sort used to sort individual buckets

void insertionSort(float arr[], int n) {
for (int i = 1; i< n; i++) {
float key = arr[i];
int j = i - 1;
while (j >= 0 &&arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void printArray(float arr[], int n) {
for (int i = 0; i< n; i++) {
printf("%.2f ", arr[i]);
}
printf("\n");
}

OUTPUT

Original Array:
0.45 0.32 0.36 0.67 0.37 0.47 0.49

Sorted Array:
0.32 0.36 0.37 0.45 0.47 0.49 0.67
 PROGRAM NO: 3
AIM:-Write a program to implement Tower of Hanoi problem using Stack..

ALGORITHM
 Initialize the Problem:
 Let n be the number of disks.
 There are three poles: Source (A), Auxiliary (B), and Destination (C).
 Represent each pole as a stack.
 Push Initial State to Stack:
 Define a structure, say Move, that contains information about the source pole, destination pole, and the
number of disks.
 Create an empty stack for moves, and push the initial move (i.e., move n disks from Source to
Destination using Auxiliary).
 Iteratively Process Moves:
 While there are moves in the stack:
o Pop the top move from the stack.
o Check the number of disks (num) for this move:
 If num is 1:
 Move the disk from the Source to Destination pole.
 If num> 1:
 Break down the move into three sub-moves (mimicking the recursive steps):
1. Push a move to transfer num - 1 disks from Auxiliary to Destination
using Source.
2. Push a move to transfer the single largest disk from Source to
Destination.
3. Push a move to transfer num - 1 disks from Source to Auxiliary using
Destination.
 End of Algorithm:
 Repeat the above steps until all disks have been moved from the Source pole to the Destination pole.
 Print each move as disks are transferred to visualize the process.

CODE
#include <stdio.h>
#include <stdlib.h>
typedef struct Move {
 int num; // Number of disks to move
char src; // Source pole
char dest; // Destination pole
char aux; // Auxiliary pole
} Move;
typedef struct Stack {
Move data[100];
int top;
} Stack;
void push(Stack *s, Move move) {
s->data[++(s->top)] = move;
}
Move pop(Stack *s) {
return s->data[(s->top)--];
}
int isEmpty(Stack *s) {
return s->top == -1;
}
void towerOfHanoi(int n, char src, char dest, char aux) {
Stack s;
s.top = -1;

Move initialMove = { n, src, dest, aux };

push(&s, initialMove);

while (!isEmpty(&s)) {
Move move = pop(&s);

if (move.num == 1) {
printf("Move disk 1 from %c to %c\n", move.src, move.dest);
} else {
// Push the steps in reverse order to simulate recursive calls in stack
Move step1 = { move.num - 1, move.aux, move.dest, move.src };
Move step2 = { 1, move.src, move.dest, move.aux };
Move step3 = { move.num - 1, move.src, move.aux, move.dest };
 push(&s, step1); // Move num-1 disks from auxiliary to destination
push(&s, step2); // Move the largest disk from source to destination
push(&s, step3); // Move num-1 disks from source to auxiliary
}
}
}

int main() {
int n;
printf("Enter the number of disks: ");
scanf("%d", &n);
towerOfHanoi(n, 'A', 'C', 'B');
return 0;
}

OUTPUT

Enter the number of disks: 3

Move disk 1 from A to C
Move disk 1 from A to B
Move disk 1 from C to B
Move disk 1 from A to C
Move disk 1 from B to A
Move disk 1 from B to C
Move disk 1 from A to C