PRACTICAL-1

Aim: Program to find the given elements in binary Search Tree.

Code:-
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left;
Node *right;
};
Node* createNode(int item) {
Node* newNode = new Node;
newNode->data = item;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
bool search(Node *root, int key) {
if (root == NULL)
return false;
if (root->data == key)
return true;
if (key > root->data)
return search(root->right, key);
else
return search(root->left, key);
}
 int main() {
int key;
Node *root = createNode(6);
root->left = createNode(2);
root->right = createNode(8);
root->right->left = createNode(7);
root->right->right = createNode(9);
cout<<"Enter the element you want to search \n";
cin>>key;
if (search(root, key))
cout << "Element is found" << endl;
else
cout << "Element is not found" << endl;
return 0;
}

Output:-
 PRACTICAL-2
Aim: Program to implement Binary Search Tree.
Code:-
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* createNode(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
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;
}
Node* findMin(Node* root) {
while (root->left != NULL)
root = root->left;
return root;
}
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 {
if (root->left == NULL && root->right == NULL) {
delete root;
return NULL;
}
else if (root->left == NULL) {
Node* temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL) {
Node* temp = root->left;
delete root;
return temp;
}
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
bool search(Node* root, int key) {
if (root == NULL)
return false;

if (root->data == key)
return true;
else if (key < root->data)
return search(root->left, key);
else
return search(root->right, key);
}
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
int main() {
Node* root = NULL;
int choice, value, key;
do {
cout << "\n--- Binary Search Tree Menu ---\n";
cout << "1. Insert\n";
cout << "2. Search\n";
cout << "3. Delete\n";
cout << "4. Inorder Traversal\n";
cout << "5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter value to insert: ";
cin >> value;
root = insert(root, value);
break;
case 2:
cout << "Enter value to search: ";
cin >> key;
if (search(root, key))
cout << "Element found\n";
else
cout << "Element not found\n";
break;
case 3:
cout << "Enter value to delete: ";
cin >> key;
root = deleteNode(root, key);
break;
case 4:
 cout << "Inorder Traversal: ";
inorder(root);
cout << endl;
break;
case 5:
cout << "Exiting...\n";
break;
default:
cout << "Invalid choice!\n";
}
} while (choice != 8);
return 0;
}

Output:-
 PRACTICAL-3
Aim:- Program to implement Activity Selection Problem.
Code:-
#include <iostream>

using namespace std;

int main()
{
int n;
cout << "Enter number of activities: ";
cin >> n;
int s[n], f[n], temp;
cout << "Enter start times:\n";
for(int i = 0; i < n; i++)
cin >> s[i];
cout << "Enter finish times:\n";
for(int i = 0; i < n; i++)
cin >> f[i];
cout << "\nSelected Activities:\n";
int i = 0;
cout << "Activity 1: (" << s[0] << ", " << f[0] << ")\n";
for(int j = 1; j < n; j++)
{
if(s[j] >= f[i])
{
cout << "Activity " << j + 1 << ": (" << s[j] << ", " << f[j] << ")\n";
i = j;
}
}
 return 0;
}

Output:-
 PRACTICAL-4
Aim:- Program to implement Knapsack Problem.
Code:-
#include <iostream>
using namespace std;
int main() {
int n, W;
float profit[100], weight[100], ratio[100];
cout << "Enter number of items: ";
cin >> n;
cout << "Enter profit of items:\n";
for(int i = 0; i < n; i++)
cin >> profit[i];
cout << "Enter weight of items:\n";
for(int i = 0; i < n; i++) {
cin >> weight[i];
ratio[i] = profit[i] / weight[i];
}
cout << "Enter knapsack capacity: ";
cin >> W;
for(int i = 0; i < n-1; i++) {
for(int j = i+1; j < n; j++) {
if(ratio[i] < ratio[j]) {
float temp;
temp = ratio[i];
ratio[i] = ratio[j];
ratio[j] = temp;
temp = profit[i];
 profit[i] = profit[j];
profit[j] = temp;
temp = weight[i];
weight[i] = weight[j];
weight[j] = temp;
}
}
}
float totalProfit = 0;
for(int i = 0; i < n; i++) {
if(weight[i] <= W) {
totalProfit += profit[i];
W -= weight[i];
} else {
totalProfit += ratio[i] * W;
break;
}
}
cout << "Maximum Profit = " << totalProfit;
return 0;
}

Output:-
 PRACTICAL-5
Aim:-Program to implement N queen’s problem.
Code:-
#include <iostream>
using namespace std;
int X[100]; // global array
// Function to check if queen can be placed
bool Place(int k, int i)
{
for (int j = 1; j <= k - 1; j++)
{
// Same column
if (X[j] == i)
return false;
// Diagonal check without abs()
if ((X[j] - i == j - k) || (X[j] - i == k - j))
return false;
}
return true;
}
// N-Queens function
void NQueens(int k, int n)
{
for (int i = 1; i <= n; i++)
{
if (Place(k, i))
{
 X[k] = i;
if (k == n)
{
for (int j = 1; j <= n; j++)
cout << X[j] << " ";
cout << endl;
}
else
{
NQueens(k + 1, n);
}
X[k] = 0; // backtrack
}
}
}
int main()
{
int n;
cout << "Enter number of queens: ";
cin >> n;
NQueens(1, n);

return 0;
}

Output:-
PRACTICAL-6
Aim:-Program to implement graph traversal using Depth First Search.
Code:-
#include <iostream>
using namespace std;
#define V 5
int adj[V][V] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 1, 0}
};
int visited[V] = {0};
// DFS function
void dfs(int node) {
cout << node << " ";
visited[node] = 1;
for (int i = 0; i < V; i++) {
if (adj[node][i] == 1 && visited[i] == 0) {
dfs(i);
}
}
}

int main() {
cout << "DFS Traversal: ";
dfs(0); // start from vertex 0
return 0;
 }

Output:-

PRACTICAL-7
Aim:-Program to implement graph traversal using Breadth First Search.
Code:-
#include <iostream>
using namespace std;
#define V 5
int adj[V][V] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 1, 0}
};
void BFS(int start) {
int visited[V] = {0};
// Manual queue
int queue[V];
int front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int node = queue[front++]; // Dequeue
cout << node << " ";
for (int i = 0; i < V; i++) {
if (adj[node][i] == 1 && visited[i] == 0) {
visited[i] = 1;
queue[rear++] = i; // Enqueue
}
}
 }
}
int main() {
cout << "BFS Traversal: ";
BFS(0); // starting from vertex 0
return 0;
}

Output:-