Sr.No. TITLE Pg.No.

1 Write a Program to Find Maximum value in an array 1

2 Write a Program to Display the array 3

3 Write a Program to Display the Matrix of two 5

4 Write a Program for Addition of Two Matrices 7

5 Write a Program for Multiplication of Two Matrices 9

6 Write a Program for Insertion in an Array 12

7 Write a Program for Deletion in an Array 14

8 Write a Program for Linear Search 16

9 Write a Program for Binary Search 18

10 Write a program for Bubble Sort 20

11 Write a program for Insertion Sort 23

12 Write a Program for Selection Sort 26

13 Write a Program for Quick Sort 29

14 Write a Program for Stack using Array 32

15 Write a Program for Queue using Array 35

16 Write a Program for Circular Queue 38

17 Write a Program for Traversing in Linked List 42

18 Write a Program for Insertion in Linked List 44

19 Write a Program for Deletion in Linked List 46

20 Write a Program for Binary Search Tree 49

21 Write a Program for BST Traversal 52

22 Write a Program for BST Insertion 55

23 Write a Program for BST Deletion 58

Index
 1. Write a Program to Find Maximum value in an array

#include<stdio.h>
#include<conio.h>
#include<string.h>

void main()
{
int i, n, a[20], max, loc = 0;

printf("Enter the size of array"); scanf("%d",

&n);

for (i = 0; i < n; i++)

scanf("%d", &a[i]);

printf("Array is:\n"); for

(i = 0; i < n; i++)
printf("a[%d] = %d\n", i, a[i]);

max = a[0];
for (i = 0; i < n; i++)
{
if (max < a[i])
{
max = a[i];
loc = i + 1;
}
}

printf("\nMaximum value in array = %d", max); printf("\

nLocation = %d", loc);

getch();
}
 2. Write a Program to Display the array
#include<stdio.h>
#include<conio.h>
#include<string.h>

void main()
{
int i, n, a[20]; clrscr();

printf("Enter the size of array"); scanf("%d",

&n);

printf("Enter the elements\n"); for

(i = 0; i < n; i++)
scanf("%d", &a[i]);

printf("Array is:\n"); for

(i = 0; i < n; i++)
printf("a[%d] = %d\n", i, a[i]);

getch();

}
 3. Write a Program to Display the Matrix of two

#include<stdio.h>
#include<conio.h>
#include<string.h>

void main()
{
int i, j, p, q, a[5][5], b[5][5];
clrscr();
printf("\n enter the size of matrix
a”)
scanf("%d%d",& p,&q);
printf("\nEnter the size of matrix b = ");
scanf("%d%d", &p, &q);
printf("\nEnter the elements of first matrix a = "); for (i =
0; i < p; i++)
for (j = 0; j < q; j++)
scanf("%d", &a[i][j]);
printf("\nEnter the elements of second matrix b = "); for (i
= 0; i < p; i++)
for (j = 0; j < q; j++)
scanf("%d", &b[i][j]);
printf("\nMatrix a = \n"); for
(i = 0; i < p; i++) {
for (j = 0; j < q; j++) printf("\t
%d", a[i][j]);
printf("\n");
}
printf("\nMatrix b = \n"); for
(i = 0; i < p; i++) {
for (j = 0; j < q; j++) printf("\t
%d", b[i][j]);
printf("\n");
}
getch();
}
 4. Write a Program for Addition of Two Matrices
#include <stdio.h>
#include <conio.h>
#include <string.h>
void main()
{
int i, j, p, q, a[5][5], b[5][5], c[5][5];
clrscr();

printf("\nEnter the size of matrix a = ");

scanf("%d%d", &p, &q);

printf("\nEnter the size of matrix b = ");

scanf("%d%d", &p, &q);

printf("\nEnter the elements of first matrix a = "); for (i =

0; i < p; i++)
for (j = 0; j < q; j++)
scanf("%d", &a[i][j]);
printf("\nEnter the elements of second matrix b = "); for (i
= 0; i < p; i++)
for (j = 0; j < q; j++)
scanf("%d", &b[i][j]);
printf("\nMatrix a =\n");
for (i = 0; i < p; i++) {
for (j = 0; j < q; j++) printf("\t
%d", a[i][j]);
printf("\n");
}

printf("\nMatrix b =\n");
for (i = 0; i < p; i++) {
for (j = 0; j < q; j++) printf("\t
%d", b[i][j]);
printf("\n");
}

printf("\nSum of the matrices a and b =\n"); for

(i = 0; i < p; i++) {
for (j = 0; j < q; j++)
printf("\t%d", a[i][j] + b[i][j]); printf("\
n");
}

getch();
}
 5. Write a Program for Multiplication of Two Matrices
#include <stdio.h>
#include <conio.h>
#include <string.h>
void main()
{
int i, j, k, m, n, p, q;
int a[5][5], b[5][5], c[5][5];
clrscr();
printf("\nEnter the size of matrix a = ");
scanf("%d%d", &m, &n);
printf("\nEnter the size of matrix b = ");
scanf("%d%d", &p, &q);
if (n != p) {
printf("\nMultiplication not possible");
} else {
printf("\nEnter the elements of first matrix a = "); for (i =
0; i < m; i++)
for (j = 0; j < n; j++) scanf("%d",
&a[i][j]);
printf("\nEnter the elements of second matrix b = "); for (i
= 0; i < p; i++)
for (j = 0; j < q; j++) scanf("%d",
&b[i][j]);
printf("\nMatrix a =\n");
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) printf("\t%d", a[i]
[j]);
printf("\n");
}
printf("\nMatrix b =\n");
for (i = 0; i < p; i++) {
for (j = 0; j < q; j++) printf("\t%d",
b[i][j]);
printf("\n");
printf("\nMultiplication of the matrix a and b =\n"); for (i =
0; i < m; i++) {
for (j = 0; j < q; j++) { c[i]
[j] = 0;
for (k = 0; k < n; k++)
c[i][j] += a[i][k] * b[k][j];
}
 }

for (i = 0; i < m; i++) { for (j

= 0; j < q; j++)
printf("\t%d", c[i][j]); printf("\n");
}
}

getch();
}

}
 6. Write a Program for Insertion in an Array
#include <stdio.h>
#include <conio.h>

void main()
{
int array[100], position, c, n, value;

printf("Enter number of elements in array\n");

scanf("%d", &n);

printf("Enter %d elements\n", n);

for (c = 0; c < n; c++)
scanf("%d", &array[c]);

printf("Enter the location where you wish to insert an element\n"); scanf("%d",

&position);

printf("Enter the value to insert\n");

scanf("%d", &value);

for (c = n; c >= position - 1; c--) array[c +

1] = array[c];

array[position - 1] = value;

printf("Resultant array is:\n"); for

(c = 0; c <= n; c++)
printf("%d\n", array[c]);

getch();
}
 7. Write a Program for Deletion in an Array
#include <stdio.h>
#include <conio.h>

void main()
{
int array[100], position, c, n;

printf("Enter number of elements in array\n");

scanf("%d", &n);

printf("Enter %d elements\n", n);

for (c = 0; c < n; c++)
scanf("%d", &array[c]);

printf("Enter the location where you wish to delete element\n");

scanf("%d", &position);

if (position >= n + 1)
printf("Deletion not possible.\n");
else {
for (c = position - 1; c < n - 1; c++)
array[c] = array[c + 1];

printf("Resultant array is:\n"); for (c

= 0; c < n - 1; c++)
printf("%d\n", array[c]);
}

getch();
}
 8. Write a Program for Linear Search
#include <stdio.h>
#include <conio.h>
#include <string.h>

void main()
{
int a[100], s, c, n;
clrscr();

printf("Enter the number of elements in array:\t");

scanf("%d", &n);

printf("\nEnter %d integer(s):\n", n); for

(c = 0; c < n; c++)
scanf("%d", &a[c]);

printf("\nEnter the number to search\t");

scanf("%d", &s);

for (c = 0; c < n; c++) { if

(a[c] == s) {
printf("\n\n\t%d is present at location %d\n", s, c + 1); break;
}
}

if (c == n)
printf("\n\n\t%d is not present in array.", s);

getch();
}
 9. Write a Program for Binary Search
#include <stdio.h>
#include <conio.h>

void main()
{
int c, first, last, middle, n, search, array[100];

printf("Enter number of elements\n");

scanf("%d", &n);

printf("Enter %d integers\n", n);

for (c = 0; c < n; c++)
scanf("%d", &array[c]);

printf("Enter value to find\n");

scanf("%d", &search);

first = 0; last
= n - 1;
middle = (first + last) / 2;

while (first <= last) {

if (array[middle] < search) first
= middle + 1;
else if (array[middle] == search) {
printf("%d found at location %d\n", search, middle + 1); break;
} else
last = middle - 1; middle
= (first + last) / 2;
}

if (first > last)

printf("Not found! %d is not present in the list", search);
getch();
}
10. Write a program for Bubble Sort
#include <stdio.h>
#include <conio.h>

void carray(int[10]);
void darray(int[10]);
void bsort(int[10]); int
n;

void main()
{
int a[10];
clrscr();

printf("\nEnter the number of elements:");

scanf("%d", &n);

carray(a);

printf("\nThe array is:"); darray(a);

bsort(a);

printf("\nSorted array:"); darray(a);

getch();
}

void carray(int x[10])

{
int i;
printf("\nEnter elements in array\n"); for
(i = 0; i < n; i++)
scanf("%d", &x[i]);
}

void darray(int x[10])

{
int i;
for (i = 0; i < n; i++) printf("\na[%d] =
%d", i, x[i]);
}
void bsort(int x[10])
{
int i, j, temp;
for (i = 0; i <= n - 1; i++) { for (j =
 0; j < n - 1; j++) {

if (x[j] > x[j + 1]) { temp =

x[j];
x[j] = x[j + 1];
x[j + 1] = temp;
}
}
}
}
11. Write a program for Insertion Sort
#include <stdio.h>
#include <conio.h>

void carray(int[10]);
void darray(int[10]);
void isort(int[10]); int
n;

void main()
{
int a[10];
clrscr();

printf("\nEnter the number of elements in an array:");

scanf("%d", &n);

carray(a);

printf("\nThe array is:"); darray(a);

isort(a);

printf("\nSorted array:"); darray(a);

getch();
}

void carray(int x[10])

{
int i;
printf("\nEnter elements in array:"); for (i
= 0; i < n; i++)
scanf("%d", &x[i]);
}

void darray(int x[10])

{
int i;
for (i = 0; i < n; i++) printf("\na[%d] =
%d", i, x[i]);
}
for (j = i - 1; j >= k; j--)
{
x[j + 1] = x[j];
}
x[k] = temp;

}
}
}
}
12. Write a Program for Selection Sort
#include <stdio.h>
#include <conio.h>

void carray(int[10]);
void darray(int[10]);
void ssort(int[10]); int
min(int[10], int);

int n;

void main()
{
int a[10];
clrscr();

printf("\nEnter the number of elements in an array: ");

scanf("%d", &n);

carray(a);

printf("\nThe array is:"); darray(a);

ssort(a);

printf("\nSorted array:"); darray(a);

getch();
}

void carray(int x[10])

{
int i;
printf("\nEnter elements in array:\n"); for
(i = 0; i < n; i++)
scanf("%d", &x[i]);
}

void darray(int x[10])

{
int i;
for (i = 0; i < n; i++) printf("\na[%d] =
%d", i, x[i]);
}

void ssort(int x[10])

{

int k, loc, temp;

for (k = 0; k < n; k++)
{
loc = min(x, k);
temp = x[k];
x[k] = x[loc];
x[loc] = temp;
}
}
int min(int x[10], int k)
{
int j, m, loc; m
= x[k];
loc = k;

for (j = k + 1; j < n; j++)

{
if (m > x[j])
{
m = x[j];
loc = j;
}
}
return loc;
}
13. Write a Program for Quick Sort
#include <stdio.h>
#include <conio.h>

void carray(int[10]); void

darray(int[10]);
void qsort(int[15], int, int); int
partition(int[15], int, int);

int n;

void main()
{
int a[10], lb, ub; clrscr();

printf("\nEnter the number of elements: ");

scanf("%d", &n);

carray(a);

lb = 0;
ub = n - 1; qsort(a,
lb, ub);
printf("\nThe array is:\n");
darray(a);

printf("\nSorted array:\n");
darray(a);

getch();
}
void carray(int x[10])
{
int i;
printf("\nEnter elements in array:\n"); for
(i = 0; i < n; i++)
scanf("%d", &x[i]);
}

void darray(int x[10])

{
int i;
for (i = 0; i < n; i++) printf("\na[%d] =
%d", i, x[i]);
}
Void qsort(int x[0],int ib,int ub)
{
Int split;
If(ib,ub)
{
Split=partition(x,ib,ub);
Qsort(x,ib,ub,split-1);
Qsort(x,split+1,ub);
}
}
int partition(int x[10], int lb, int ub)
{
int first, last, temp, key; first
= lb;
last = ub;
key = x[lb];

while (first < last)

{
while (x[first] < key) first++;

while (x[last] > key)

last--;

if (first < last)

{
temp = x[first];
x[first] = x[last];
x[last] = temp;
}
}

if (first > last)

{
temp = x[lb];
x[lb] = x[last];
x[last] = temp;
}

return last;
}
14. Write a Program for Stack using Array
#include <stdio.h>
#include <conio.h>

void push(int [10], int); void

pop(int [10]);
void display(int [10]); int
n = 10, top = -1;
void main()
{
int a[10], ch, item;

do { clrscr();
printf("Menu\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: "); scanf("%d",
&ch);
switch (ch)
{
case 1:
printf("Enter element to push: ");
scanf("%d", &item);
push(a, item);
break;
case 2:
pop(a);
break;
case 3:
display(a);
break;
case 4:
printf("Thanks for using my window");
getch();
exit(0);
default:
printf("Wrong choice");
}
} while (ch <= 4);

getch();
}
void push(int x[10], int item)
{
if (top == n - 1)
printf("Overflow");
else {
top++;
x[top] = item;
}

getch();
}

void pop(int x[10])

{
int item;

if (top == -1) printf("Underflow");

else {
item = x[top];
top--;
printf("Deleted item = %d", item);
}

getch();
}

void display(int x[10])

{
int i;

if (top == -1)
printf("Stack is empty");
else {
printf("Stack is:");
for (i = 0; i <= top; i++) printf("x[%d] =
%d\n", i, x[i]);
}

getch();
}
15. Write a Program for Queue using Array

#include <stdio.h>
#include <conio.h>

void insert(int[10], int); void

delete(int[10]);
void display(int[10]);
int n = 10, front = -1, rear = -1; void
main()
{
int a[10], ch, item;

do { clrscr();
printf("Menu\n");
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: "); scanf("%d",
&ch);

switch (ch)
{
case 1:
printf("\nEnter element in queue: ");
scanf("%d", &item);
insert(a, item); break;

case 2:
delete(a);
break;
case 3:
display(a);
break;
case 4:
printf("\nThanks for using my window");
getch();
exit(0);
default:
printf("Wrong choice");

} while (ch <= 4);

 getch();
}
void insert(int x[10], int item)
{
if (rear == n - 1) printf("\
nOverflow");
else {
if (front == -1)
front++;

rear++;
x[rear] = item;
}

getch();
}
void delete(int x[10])
{
int item;
if (front == -1) printf("\
nUnderflow");
else {
item = x[front];
if (front == rear) {
front--;
rear--;
} else {
front++;
}
printf("Deleted item = %d", item);
}

getch();
}

void display(int x[10])

{
int i;

if (front == -1) printf("\nQueue

is empty");
else {
printf("Queue is:\n");
for (i = front; i <= rear; i++) printf("q[%d]
= %d\n", i, x[i]);
}
Getch():
}
16. Write a Program for Circular Queue

#include <stdio.h>
#include <conio.h>

void insert(int[10], int); void

delete(int[10]);
void display(int[10]);
int n = 10, front = -1, rear = -1; void
main()
{
int a[10], ch, item;

do { clrscr();
printf("Menu\n");
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: "); scanf("%d",
&ch);

switch (ch)
{
case 1:
printf("\nEnter element in circular queue: ");
scanf("%d", &item);
insert(a, item); break;

case 2:
delete(a);
break;

case 3:
display(a);
break;

case 4:
printf("\nThanks for using my window");
getch();
exit(0);

default:
printf("Wrong choice");
}

} while (ch <= 4);

 getch();
}
void insert(int x[10], int item)
{
if ((front == 0 && rear == n - 1) || (front == rear + 1)) printf("\nOverflow");
else {
if (front == -1) front
= 0;
if (rear == n - 1 && front != 0) rear =
0;
else
rear++;

x[rear] = item;
}
getch();
}

void delete(int x[10])

{
int item;

if (front == -1) printf("\

nUnderflow");
else {
item = x[front];
if (front == rear) { front
= -1;
rear = -1;
} else if (front == n - 1) front =
0;
else
front++;

printf("Deleted item = %d", item);

}

getch();
}
void display(int x[10])
{
int i;

if (rear == -1)
printf("\nQueue is empty");
else {
printf("Queue is:\n"); if
(front > rear) {
 for (i = front; i < n; i++) printf("x[%d]
= %d\n", i, x[i]);
for (i = 0; i <= rear; i++)

printf("x[%d] = %d\n", i, x[i]);

} else {
for (i = front; i <= rear; i++)
printf("x[%d] = %d\n", i, x[i]);
}
}

getch();
}
17. Write a Program for Traversing in Linked List
#include <stdio.h>
#include <conio.h>
int list[20], link[20], start;
void process(int p1)
{
list[p1] = list[p1] / 10;
}
void main()
{
int ptr;
clrscr();
list[1] = 11; list[2] = 22; list[3] = 33; list[4] = 44;
list[5] = 55; list[6] = 66; list[7] = 77; list[8] = 88;
link[1] = 2; link[2] = 3; link[3] = 4; link[4] = 5;
link[5] = 6; link[6] = 7; link[7] = 8; link[8] = 0;
start = 1; ptr
= start;
printf("\nInitial list:\n");
while (ptr != 0)
{
printf("\t%d", list[ptr]); ptr =
link[ptr];
}

ptr = start; while

(ptr != 0)
{
process(ptr); ptr
= link[ptr];
}

ptr = start;
printf("\nList after traversal:\n"); while
(ptr != 0)
{
printf("\t%d", list[ptr]); ptr =
link[ptr];
}

getch();
}
18. Write a Program for Insertion in Linked List
#include <stdio.h>
#include <conio.h>
int list[20], link[20], start; void
process(int, int[], int[]);
void main()
{
int ptr;
clrscr();
list[1] = 11; list[2] = 22; list[3] = 33; list[4] = 44;
list[5] = 55; list[6] = 66; list[7] = 77; list[8] = 88; list[9] = 99;
link[1] = 2; link[2] = 3; link[3] = 4; link[4] = 5;
link[5] = 6; link[6] = 7; link[7] = 8; link[8] = 9; link[9] = 0;
start = 1; ptr
= start;
printf("\nInitial list:\n");
while (ptr != 0)
{
printf("\t%d", list[ptr]); ptr =
link[ptr];
}
ptr = start;
process(ptr, list, link);

ptr = start;
printf("\nList after insert a new node:\n");
while (ptr != 0)
{
printf("\t%d", list[ptr]); ptr =
link[ptr];
}

getch();
}

void process(int p1, int list[20], int link[20])

{
start = 100;
list[100] = 110;
link[100] = p1;
}
19. Write a Program for Deletion in Linked List
#include <stdio.h>
#include <conio.h>

int list[20];
int link[20];
int start;

void process(int, int[], int[]);

void main()
{
int ptr;
clrscr();

list[1] = 11; list[2] = 22; list[3] = 33; list[4] = 44;

list[5] = 55; list[6] = 66; list[7] = 77; list[8] = 88; list[9] = 99;

link[1] = 2; link[2] = 3; link[3] = 4; link[4] = 5;

link[5] = 6; link[6] = 7; link[7] = 8; link[8] = 9; link[9] = 0;

start = 1; ptr
= start;

printf("\nInitial list:\n");
while (ptr != 0)
{
printf("\t%d", list[ptr]); ptr =
link[ptr];
}

ptr = start;
process(ptr, list, link);

ptr = start;
printf("\nList after delete a node:\n"); while
(ptr != 0)
{
printf("\t%d", list[ptr]); ptr =
link[ptr];
}

getch();
}

void process(int p1, int list[20], int link[20])

{
start = link[start]; // deletes the first node by skipping it
}
20. Write a Program for Binary Search Tree

#include <iostream.h>
#include <conio.h>

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

Node* createNode(int key) {

Node* newNode = new Node;
newNode->data = key;
newNode->left = newNode->right = NULL;
return newNode;
}

Node* insert(Node* root, int key) {

if (root == NULL) return createNode(key);
if (key < root->data)
root->left = insert(root->left, key);
else
root->right = insert(root->right, key);
return root;
}

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

if (root == NULL || root->data == key)
return root;
if (key < root->data)
return search(root->left, key);
return search(root->right, key);
}

void inorder(Node* root) {

if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
 }
}

void main() {
clrscr();

Node* root = NULL;

root = insert(root, 8);
insert(root, 3);
insert(root, 10);
insert(root, 1);
insert(root, 6);
insert(root, 14);
insert(root, 4);
insert(root, 7);

cout << "Inorder traversal: ";

inorder(root);

int key = 6;
if (search(root, key))
cout << "\nElement " << key << " found!";
else
cout << "\nElement " << key << " not found!";

getch();
}
21. Write a Program for BST Traversal

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>

// Define node structure

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

// Create a new node

Node* createNode(char value) {
Node* newNode = new Node;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Pre-order traversal: Root → Left → Right

void preorder(Node* root) {
if (root != NULL) {
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
}

// In-order traversal: Left → Root → Right

void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
// Post-order traversal: Left → Right → Root
void postorder(Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
}

void main() {
clrscr();

// Manually building the tree structure

/*
A
/\
B C
/\ \
D E F
*/

Node* root = createNode('A');

root->left = createNode('B');
root->right = createNode('C');
root->left->left = createNode('D');
root->left->right = createNode('E');
root->right->right = createNode('F');

// Perform all traversals

cout << "Pre-order Traversal: ";
preorder(root);

cout << "\nIn-order Traversal: ";

inorder(root);

cout << "\nPost-order Traversal: ";

postorder(root);

getch();
}
22. Write a Program for BST Insertion

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>

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

// Create a new node

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

// Insert into BST

Node* insert(Node* root, int value) {
if (root == NULL)
return createNode(value);

if (value < root->data)

root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);

return root;
}

// Inorder traversal
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
 }
}

void main() {
clrscr();

Node* root = NULL;

int value;

cout << "=== Build Initial BST ===\n";

cout << "Enter values (-1 to stop):\n";

// Initial insertion loop

while (1) {
cout << "Enter value: ";
cin >> value;
if (value == -1)
break;
root = insert(root, value);
}

cout << "\nIn-order Traversal of Initial Tree:\n";

inorder(root);

// Separate insertion
cout << "\n\n=== Insert a New Value ===\n";
cout << "Enter a value to insert: ";
cin >> value;
root = insert(root, value);

cout << "\nIn-order Traversal After Inserting New Value:\n";

inorder(root);

getch();
}
23. Write a Program for BST Deletion

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>

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

// Create a new node

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

// Insert node in BST

Node* insert(Node* root, int value) {
if (root == NULL)
return createNode(value);

if (value < root->data)

root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);

return root;
}

// In-order traversal
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
 }
}

// Find node with minimum value

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

// Delete node from BST

Node* deleteNode(Node* root, int key) {
if (root == NULL)
return root;

if (key < root->data)

root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
// Case 1: one or no child
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}

// Case 2: two children

Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}

// Main function
void main() {
clrscr();
Node* root = NULL;
int value;

cout << "Enter values to insert in BST (-1 to stop):" << endl;
while (1) {
cout << "Enter value: ";
cin >> value;
if (value == -1)
break;
root = insert(root, value);
}

cout << "\nIn-order Traversal before deletion:\n";

inorder(root);

cout << "\n\nEnter value to delete from BST: ";

cin >> value;
root = deleteNode(root, value);

cout << "\nIn-order Traversal after deletion:\n";

inorder(root);

getch();
}