DSA LAB TEST
UNIT -4
Q1. Implementation of Binary Trees
ALGORITHM:
1. Start
2. Define a node structure with data, left, and right pointers
3. Create a function to allocate memory and initialize a new node
4. If root is NULL, assign new node as root
5. If data < root->data, recursively insert into left subtree
6. Else, recursively insert into right subtree
7. Repeat insertion for all input values
8. Define an inorder traversal function (Left → Root → Right)
9. Traverse the tree using inorder() to display sorted data
10. Stop
CODE:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
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 root->right = insert(root->right, data);
return root;
}
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
inorder(root);
return 0;
}
OUTPUT
20 30 40 50 60 70 80
Q2. Implementation of BST using Linked List
ALGORITHM:
1. Start
2. Define a node structure with data, left, and right pointers
3. Create a function to allocate and initialize a new node
4. If root is NULL, set new node as root
5. If data < root data, insert into left subtree
6. Else insert into right subtree
7. Repeat insertion for all input data values
8. Traverse the tree using inorder (Left → Root → Right)
9. Display the nodes in sorted order
10. Stop
CODE:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
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
root->right = insert(root->right, data);
return root;
}
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
printf("Inorder traversal of BST: ");
inorder(root);
return 0;
}
OUTPUT:
Inorder traversal of BST: 20 30 40 50 60 70 80
UNIT 5
Q1. Implementation of graph using arrays
ALGORITHM:
1. Start
2. Declare a 2D array (adjacency matrix) to store connections between vertices
3. Initialize all elements of the matrix to 0
4. Input number of vertices and edges
5. For each edge (u, v), set matrix[u][v] = 1
6. If undirected, also set matrix[v][u] = 1
7. Repeat until all edges are added
8. Display the adjacency matrix
9. Stop
CODE:
#include <stdio.h>
int main() {
int n, e;
printf("Enter number of vertices: ");
scanf("%d", &n);
int graph[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
graph[i][j] = 0;
printf("Enter number of edges: ");
scanf("%d", &e);
printf("Enter edges (u v):\n");
for (int i = 0; i < e; i++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u][v] = 1;
graph[v][u] = 1;
}
printf("Adjacency Matrix Representation:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
return 0;
}
SAMPLE INPUT:
Enter number of vertices: 4
Enter number of edges: 5
Enter edges (u v):
01
02
12
23
33
OUTPUT:
Adjacency Matrix Representation:
0110
1010
1101
0011
Q2. Implementation of Shortest Path Algorithm – DIJKSTRA’S ALGORITHM
ALGORITHM:
1. Start
2. Input number of vertices and adjacency matrix
3. Initialize distance of all vertices as infinity except source (0)
4. Mark all vertices as unvisited
5. Select the unvisited vertex with minimum distance
6. Update the distance of its neighbouring vertices
7. Mark the current vertex as visited
8. Repeat until all vertices are visited
9. Print the shortest distance from the source to every vertex
10. Stop
CODE:
#include <stdio.h>
#define INF 9999
#define MAX 10
void dijkstra(int graph[MAX][MAX], int n, int start) {
int cost[MAX][MAX], dist[MAX], visited[MAX], count, mindist, nextnode, i, j;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cost[i][j] = (graph[i][j] == 0) ? INF : graph[i][j];
for (i = 0; i < n; i++) {
dist[i] = cost[start][i];
visited[i] = 0;
}
dist[start] = 0;
visited[start] = 1;
count = 1;
while (count < n - 1) {
mindist = INF;
for (i = 0; i < n; i++)
if (dist[i] < mindist && !visited[i]) {
mindist = dist[i];
nextnode = i;
}
visited[nextnode] = 1;
for (i = 0; i < n; i++)
if (!visited[i])
if (mindist + cost[nextnode][i] < dist[i])
dist[i] = mindist + cost[nextnode][i];
count++;
}
printf("Vertex\tDistance from Source\n");
for (i = 0; i < n; i++)
printf("%d\t%d\n", i, dist[i]);
}
int main() {
int n, start, graph[MAX][MAX];
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &graph[i][j]);
printf("Enter the starting node: ");
scanf("%d", &start);
dijkstra(graph, n, start);
return 0;
}
SAMPLE INPUT:
Enter number of vertices: 5
Enter the adjacency matrix:
0 10 0 5 0
00120
00004
03902
70600
Enter the starting node: 0
OUTPUT:
Vertex Distance from Source
0 0
1 8
2 9
3 5
4 7