Module 4 Program 1

Given an array of elements, construct a complete binary tree from this array in level order fashion.
That is, elements from left in the array will be filled in the tree level wise starting from level 0. Ex:
Input : arr[] = {1, 2, 3, 4, 5, 6} Output : Root of the following tree

1
/\
2 3
/ \ /\
4 5 6
#include <stdio.h>

#include<stdlib.h>

struct node {

int data;

struct node *left, *right;

};

struct node* newNode(int data);

struct node* newNode(int data)

struct node* node

= (struct node*)malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return (node);

}
int height(struct node * node)

if (node == NULL)

return 0;

else {

int lheight = height(node -> left);

printf("%d\n",lheight);

return (lheight + 1);

void CurrentLevel(struct node * root, int level)

if (root == NULL)

return;

if (level == 1)

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

else if (level > 1) {

CurrentLevel(root -> left, level - 1);

CurrentLevel(root -> right, level - 1);

}
void LevelOrder(struct node * root)

int h = height(root);

int i;

for (i = 1; i <= h; i++) {

printf("level %d ->",i);

CurrentLevel(root, i);

printf("\n");

int main()

int a[20]= {1,2,3,4,5,6};

struct node* root = newNode(a[0]);

root->left = newNode(a[1]);

root->right = newNode(a[2]);

root->left->left = newNode(a[3]);

root->left->right = newNode(a[4]);

root->left->right = newNode(a[6]);

LevelOrder(root);

return 0; }
Program 2 module 4
Design, Develop and Implement a menu driven Program in C for the following operations on
Binary Search Tree (BST) of Integers .

a. Create a BST of N Integers:

b. Traverse the BST in Inorder, Preorder and Post Order

#include <stdio.h>
#include <stdlib.h>
struct BST
{
int data;
struct BST *left;
struct BST *right;
};
typedef struct BST NODE;
NODE *node;
NODE* createtree(NODE *node, int data)
{
if (node == NULL)
{
NODE *temp;
temp= (NODE*)malloc(sizeof(NODE));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
if (data < (node->data))
{
node->left = createtree(node->left, data);
}
else if (data > node->data)
{
node -> right = createtree(node->right, data);
}
return node;
}

void inorder(NODE *node)

{
if(node != NULL)
{
inorder(node->left);
printf("%d\t", node->data);
inorder(node->right);
}
}
void preorder(NODE *node)
{
if(node != NULL)
{
printf("%d\t", node->data);
preorder(node->left);
preorder(node->right);
}
}
void postorder(NODE *node)
{
if(node != NULL)
{
postorder(node->left);
postorder(node->right);
printf("%d\t", node->data);
}
}
NODE* findMin(NODE *node)
{
if(node==NULL)
{
return NULL;
}
if(node->left)
return findMin(node->left);
else
return node;
}

void main()
{
int data, ch, i, n;
NODE *root=NULL;
while (1)
{
printf("\[Link] ");
printf("\n2. .Inorder ");
printf("\[Link] ");
printf("\n4 .Postorder\[Link]");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch (ch)
{
case 1: printf("\nEnter N value: " );
scanf("%d", &n);
printf("\nEnter the values to create BST");
for(i=0; i<n; i++)
{
scanf("%d", &data);
root=createtree(root, data);
}
break;
case 2: printf("\nInorder Traversal: \n");
inorder(root);
break;
case 3: printf("\nPreorder Traversal: \n");
preorder(root);
break;

case 4: printf("\nPostorder Traversal: \n");

postorder(root);
break;

case 5: exit(0);
default:printf("\nWrong option");
break;
}
}
}

Module 5 Program 1
Design, Develop and Implement a Program in C for the
following operations on Graph(G) of Cities

a. Create a Graph of N cities using Adjacency Matrix.

b. Print all the nodes reachable from a given starting node in a digraph using DFS/BFS
method
#include<stdio.h>
#include<stdlib.h>

int a[50][50], n, visited[50];

int q[20], front = -1,rear = -1;
int s[20], top = -1, count=0;

void bfs(int v)
{
int i, cur;
visited[v] = 1;
q[++rear] = v;
while(front!=rear)
{
cur = q[++front];
 for(i=1;i<=n;i++)
{
if((a[cur][i]==1)&&(visited[i]==0))
{
q[++rear] = i;
visited[i] = 1;
printf("%d ", i);
}
}
}
}

void dfs(int v)
{
int i;
visited[v]=1;
s[++top] = v;
for(i=1;i<=n;i++)
{
if(a[v][i] == 1&& visited[i] == 0 )
{
printf("%d ", i);
dfs(i);
}
}
}
int main()
{

int ch, start, i,j;

printf("\nEnter the number of vertices in graph: ");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}

for(i=1;i<=n;i++)
visited[i]=0;
printf("\nEnter the starting vertex: ");
scanf("%d",&start);
do{

printf("\n==>1. BFS: Print all nodes reachable from a given starting node");
printf("\n==>2. DFS: Print all nodes reachable from a given starting node");
printf("\n==>3:Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: printf("\nNodes reachable from starting vertex %d are: ", start);
 bfs(start);
for(i=1;i<=n;i++)
{
if(visited[i]==0)
printf("\nThe vertex that is not reachable is %d" ,i);
}
break;

case 2: printf("\nNodes reachable from starting vertex %d are:\n",start);

dfs(start);
break;
case 3: exit(0);
default: printf("\nPlease enter valid choice:");

}
}while(1);}

Module 5 program 2

Design and develop a program in C that

uses Hash function H: K → L as H(K)=K mod m (remainder method), and implement
hashing technique to map a given key K to the address space L. Resolve the collision
(if any) using linear probing.

#include <stdio.h>

#include <stdlib.h>

#define MAX 100

/*FUNCTION PROTOTYPE */

int create(int);
void linear_prob(int[], int, int);

void display (int[]);

void main()

int a[MAX],num,key,i;

int ans=1;

printf(" collision handling by linear probing : \n");

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

a[i] = -1;

do

printf("\n Enter the data");

scanf("%4d", &num);

key=create(num);

linear_prob(a,key,num);

printf("\n Do you wish to continue ? (1/0) ");

scanf("%d",&ans);

}while(ans);

display(a);

int create(int num)

{

int key;

key=num%100;

return key;

void linear_prob(int a[MAX], int key, int num)

int flag, i, count=0;

flag=0;

if(a[key]== -1)

a[key] = num;

else

printf("\nCollision Detected...!!!\n");

i=0;

while(i<MAX)

if (a[i]!=-1)

count++;

i++;

}
printf("Collision avoided successfully using LINEAR PROBING\n");

if(count == MAX)

printf("\n Hash table is full");

display(a);

exit(1);

for(i=key+1; i<MAX; i++)

if(a[i] == -1)

a[i] = num;

flag =1;

break;

//for(i=0;i<key;i++)

i=0;

while((i<key) && (flag==0))

if(a[i] == -1)

a[i] = num;

flag=1;

break;
}

i++;

void display(int a[MAX])

int i,choice;

printf("[Link] ALL\n [Link] Display\n");

scanf("%d",&choice);

if(choice==1)

printf("\n the hash table is\n");

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

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

else

printf("\n the hash table is\n");

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

if(a[i]!=-1)

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

continue;