Binary search tree (BST)

Set A)
a) Implement a Binary search tree (BST) library (btree.h)
with operations – create, search, insert, inorder,
preorder and postorder. Write a menu driven program
that performs the above operations.
#include<stdio.h>
#include "btree.h"
void main()
{
int op,n,r;
struct node *root;
while (1)
{
x=0;
printf("\n***OPERATIONS ON A BST***");
printf("\n1 : CRAETE A BST.");
printf("\n2 : SEARCH A ELEMENT IN A BST.");
printf("\n3 : INSERT A ELEMENT IN A BST.");
printf("\n4 : TRAVERSAL OF A BST.");
printf("\n5 : TOTAL NO. OF NODES IN A BST.");
printf("\n6 : TOTAL NO. OF LEAF NODES IN A
BST.");
printf("\n7 : DELETE A NODE.");
printf("\n8 : EXIT.");
 printf("\nEnter Operation You Want To Perform :
");
scanf("%d",&op);
switch (op)
{

case 1 : if (root!=NULL)
printf("\nBST ALREADY EXITS.");
else
{
printf("\nHOW MANY ELEMENTS YOU
WANT TO ENTER IN A BST : ");
scanf("%d",&n);
root=create(root,n);
}
break;
case 2 : if (root==NULL)
printf("\nBST NOT EXITS.");
else
{
printf("\nENTER A ELEMENT YOU WANT
TO SEARCH IN A BST : ");
scanf("%d",&n);
r=search(root,n);
if (r==1)
printf("%d PRESENET IN A BST.",n);
else
 printf("%d NOT PRESENET IN A
BST.",n);
}
break;
case 3 : printf("\nINSERT A ELEMENT IN A
BST");
root=create(root,1);
break;
case 4 : if (root==NULL)
printf("\nBST NOT EXITS.");
else
{
printf("\nINORDER OF A BST : ");
inorder(root);
printf("\nPREORDER OF A BST : ");
preorder(root);
printf("\nPOSTORDER OF A BST : ");
postorder(root);
}
break;
case 5 : if (root==NULL)
printf("\nBST NOT EXITS.");
else
{
r=countnode(root);
printf("\nTOTAL NO. OF NODES IN A
BST : %d",r);
 }
break;
case 6 : if (root==NULL)
printf("\nBST NOT EXITS.");
else
{
r=countleaf(root);
printf("\nTOTAL NO. OF LEAF NODES IN
A BST : %d",r);
}
break;
case 7 : if (root==NULL)
printf("\nBST NOT EXITS.");
else
{
printf("\nENTER A ELEMENT YOU WANT
TO DELETE IN A BST : ");
scanf("%d",&n);
r=search(root,n);
if(r==0)
printf("%d NOT PRESENT IN A BST.");
else
root=dlt(root,n);
}
break;
case 8 : exit(0);
break;
 default : printf("\nERROR.....INVALID
OPERATION.\n");
}

}
}

/*
struct node * create(struct node *t,int n)
{
struct node *temp,*t1,*nw;
int i;
for (i=1;i<=n;i++)
{
nw=malloc(sizeof(struct node));
nw->left=nw->right=NULL;
printf("\n ENTER DATA : ");
scanf("%d",&nw->data);
if (t==NULL)
t=nw;
else
{
temp=t;
while(temp!=NULL)
{
t1=temp;
if(temp->data > nw->data)
temp=temp->left;
 else
temp=temp->right;
}
if(t1->data > nw->data)
t1->left=nw;
else
t1->right=nw;
}

}
return t;
}
int search(struct node *t,int n)
{
while(t)
{
if(t->data==n)
return 1;
else if (t->data > n)
t=t->left;
else
t=t->right;
}
return 0;
}
void inorder(struct node*t)
{
if(t==NULL)
 return;
inorder(t->left);
printf(" %d ",t->data);
inorder(t->right);
}
void preorder(struct node* t)
{
if(t==NULL)
return;
printf(" %d ",t->data);
preorder(t->left);
preorder(t->right);
}
void postorder(struct node*t)
{
if(t==NULL)
return;
postorder(t->left);
postorder(t->right);
printf(" %d ",t->data);
}
int countnode(struct node* t)
{
if (t!=NULL)
return (1+countnode(t->left)+countnode(t->right));
}
int countleaf(struct node* t)
 {
if (t!=NULL)
{
if(t->left==NULL && t->right==NULL)
x++;
countleaf(t->left);
countleaf(t->right);
}
return x;
}*/
OR
#include<stdio.h>
#include<stdlib.h>
#include "btree.h"
int menu()
{
int ch;
system("clear");
printf("\n\t0.Exit\n\t1.Create BST\n\t2.Insert Node\n\
t3.Search a node\n\t4.Display tree\n\tEnter you choice :");
scanf("%d",&ch);
return ch;
}
int main()
{
struct node *root= NULL;
int ch;
while((ch=menu())!=0)
{
if(ch==1)
{
createbst(&root);
}
else
if(ch==2)
{
int node;
printf("\n\tEnter data : ");
scanf("%d",&node);
insert(&root,node);
}
else
if(ch==3)
{
int node;
printf("\n\tEnter node to be searched : ");
scanf("%d",&node);
search(root,node);
getchar();getchar();
}

else
if(ch==4)
{
display(root);
getchar();getchar();
}
}
}

Library Function ( .h file )

NOTE: save file name as ' btree.h'

struct node
{
int data;
struct node *left,*right;
};
struct node * createnode(struct node *newnode,int data)
{
newnode=malloc(sizeof(struct node));
newnode->data=data;
newnode->left= newnode->right = NULL;
return newnode;
}
void insert(struct node **root,int data)
{
struct node *newnode;
newnode=createnode(newnode,data);
if(*root==NULL)
*root=newnode;
else
{
struct node *temp=*root;
while(1)
{
if(data <= temp->data)
{
if(temp->left==NULL)
{
temp->left=newnode;
break;
}
temp=temp->left;
}
else
{
if(temp->right==NULL)
{
temp->right=newnode;
break;
}
temp=temp->right;
}
}
}
}
void createbst(struct node **root)
{
int n,i;
int data;
printf("\n\tENter the how many nodes ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n\tEnter data : ");
scanf("%d",&data);
insert(root,data);
}
}
void display(struct node *temp)
{
if(temp)
{
printf("%d\t",temp->data);
display(temp->left);
display(temp->right);
}
}
int search(struct node *temp,int data)
{
if(temp)
{
if(temp->data == data)
{
printf("data found");
return;
}
search(temp->left,data);
search(temp->right,data);
}
}
b) Write a program which uses binary search tree library and
counts the total nodes and total leaf nodes in the tree. int
count(T) – returns the total number of nodes from BST int
countLeaf(T) – returns the total number of leaf nodes from
BST.
// C implementation to find leaf count of a given Binary tree
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child

and a pointer to right child */
struct node
{
int data;
struct node* left;
 struct node* right;
};

/* Function to get the count of leaf nodes in a binary tree*/

unsigned int getLeafCount(struct node* node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
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);
}
/*Driver program to test above functions*/
int main()
{
/*create a tree*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/*get leaf count of the above created tree*/
printf("Leaf count of the tree is %d", getLeafCount(root));
getchar();
return 0;
}
“btree.h”
// C# implementation to find leaf
// count of a given Binary tree
using System;
using System.Collections.Generic;

// class to represent tree node

public class Node{
public int data;
public Node left, right;

public Node(int data){

this.data = data;
this.left = null;
this.right = null;
}
}

public class BinaryTree{

// utility function to get the new node
static Node newNode(int data){
return new Node(data);
}
// function to get count of leaf nodes
static int getLeafCount(Node root){
// initializing queue for level order traversal
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
int count = 0;
while(q.Count > 0){
Node temp = q.Dequeue();
if(temp.left == null && temp.right == null) count++;
if(temp.left != null) q.Enqueue(temp.left);
if(temp.right != null) q.Enqueue(temp.right);
}
return count;
}
// driver program to test above function
public static void Main(){
Node root = newNode(1);
 root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
// function call
Console.WriteLine("Leaf Count of the tree is : " +
getLeafCount(root));
}
}
Set B )
a) Write a C program which uses Binary search tree library
and implements following function with recursion: T copy(T)
– create another BST which is exact copy of BST which is
passed as parameter. int compare(T1, T2) – compares two
binary search trees and returns 1 if they are equal and 0
otherwise.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
 struct node *left,*right;
};
int x;
struct node * create(struct node *,int);
int search(struct node*,int);
void inorder(struct node*);
void preorder(struct node*);
void postorder(struct node*);
int countnode(struct node*);
int countleaf(struct node*);
struct node * dlt(struct node*,int);
struct node* succ (struct node *);
struct node * create(struct node *t,int n)
{
struct node *temp,*t1,*nw;
int i;
for (i=1;i<=n;i++)
{
nw=malloc(sizeof(struct node));
nw->left=nw->right=NULL;
printf("\n ENTER DATA : ");
scanf("%d",&nw->data);
if (t==NULL)
t=nw;
else
{
temp=t;
while(temp!=NULL)
{
t1=temp;
if(temp->data > nw->data)
temp=temp->left;
else
temp=temp->right;
}
if(t1->data > nw->data)
t1->left=nw;
else
t1->right=nw;
}
 }
return t;
}
int search(struct node *t,int n)
{
while(t)
{
if(t->data==n)
return 1;
else if (t->data > n)
t=t->left;
else
t=t->right;
}
return 0;
}
void inorder(struct node*t)
{
if(t==NULL)
 return;
inorder(t->left);
printf(" %d ",t->data);
inorder(t->right);
}
void preorder(struct node* t)
{
if(t==NULL)
return;
printf(" %d ",t->data);
preorder(t->left);
preorder(t->right);
}
void postorder(struct node*t)
{
if(t==NULL)
return;
postorder(t->left);
postorder(t->right);
printf(" %d ",t->data);
}
int countnode(struct node* t)
{
if (t!=NULL)
return (1+countnode(t->left)+countnode(t->right));
}
int countleaf(struct node* t)
{

if (t!=NULL)
{
if(t->left==NULL && t->right==NULL)
x++;
countleaf(t->left);
countleaf(t->right);
}
return x;
}
struct node * dlt(struct node * t,int key)
{
struct node * temp;
if (key < t->data)
t->left=dlt(t->left,key);
else if (key > t->data)
t->right=dlt(t->right,key);
else
{
if (t->left==NULL)
{
temp=t->right;
free(t);
return temp;
}
else if (t->right==NULL)
{
temp=t->left;
free(t);
return temp;
}
struct node * t1=succ(t->right);
 t->data=t1->data;
t->right=dlt(t->right,t1->data);

}
return t;
}
struct node* succ (struct node *t)
{
struct node * current=t;
while (current && current->left!=NULL)
current=current->left;
return current;
}
Assignment 2: Binary Tree Applications
Set a)
a) Write a C program which uses Binary search tree library
and displays nodes at each level, count of node at each
level and total levels in the tree.

#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *lchild;
int info;
struct node *rchild;
};

struct node *insert(struct node *ptr, int ikey);

void display(struct node *ptr,int level);
int NodesAtLevel(struct node *ptr, int level) ;

int main()
{
struct node *root=NULL,*root1=NULL,*ptr;
int choice,k,item,level;

while(1)
{
printf("\n");
printf("1.Insert Tree \n");
printf("2.Display Tree \n");
printf("3.Number of Nodes \n");
printf("4.Quit\n");
printf("\nEnter your choice : ");
scanf("%d",&choice);

switch(choice)
 {

case 1:
printf("\nEnter the key to be inserted : ");
scanf("%d",&k);
root = insert(root, k);
break;

case 2:
printf("\n");
display(root,0);
printf("\n");
break;

case 3:
printf("\n");
printf("Enter any level :: ");
scanf("%d",&level);
printf("\nNumber of nodes at [ %d ] Level :: %d\
n",level,NodesAtLevel(root,level));
break;

case 4:
exit(1);

default:
printf("\nWrong choice\n");
 }/*End of switch */
}/*End of while */

return 0;

}/*End of main( )*/

.h
struct node *insert(struct node *ptr, int ikey )
{
if(ptr==NULL)
{
ptr = (struct node *) malloc(sizeof(struct
node));
ptr->info = ikey;
ptr->lchild = NULL;
ptr->rchild = NULL;
}
else if(ikey < ptr->info) /*Insertion in left subtree*/
ptr->lchild = insert(ptr->lchild, ikey);
else if(ikey > ptr->info) /*Insertion in right subtree
*/
ptr->rchild = insert(ptr->rchild, ikey);
else
printf("\nDuplicate key\n");
return(ptr);
}/*End of insert( )*/

void display(struct node *ptr,int level)

{
int i;
if(ptr == NULL )/*Base Case*/
return;
else
{
display(ptr->rchild, level+1);
printf("\n");
for (i=0; i<level; i++)
printf(" ");
printf("%d", ptr->info);
display(ptr->lchild, level+1);
}
}/*End of display()*/

int NodesAtLevel(struct node *ptr, int level)

{
if(ptr==NULL)
return 0;
if(level==0)
return 1;
return NodesAtLevel(ptr->lchild,level-1) +
NodesAtLevel(ptr->rchild,level-1);
 }/*End of NodesAtLevel()*/

a) Write a program to sort n randomly generated elements

using Heapsort method
#include<stdio.h>

// function prototyping
void heapify(int*,int, int);
void heapsort(int*, int);
void print_array(int*, int);

int main()
{
int arr[] = { 10, 30, 5, 63, 22, 12, 56, 33 };
int n = sizeof(arr) / sizeof(arr[0]);

printf("\nArray before sorting:\n");

print_array(arr, n);

heapsort(arr, n);

printf("\n\nArray after sorting:\n");

print_array(arr, n);

return 0;
}

/* sorts the given array of n size */

void heapsort(int* arr, int n)
{
 // build the binary max heap
for (int i = n / 2 - 1; i >= 0; i--)
{
heapify(arr, n, i);
}

// sort the max heap

for (int i = n - 1; i >= 0; i--)
{
// swap the root node and the last leaf node
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;

// again heapify the max heap from the root

heapify(arr, i, 0);
}
}

/* heapify the subtree with root i */

void heapify(int* arr, int n, int i)
{
// store largest as the root element
int largest = i;

int left = 2 * i + 1;
int right = 2 * i + 2;
 // now check whether the right and left right is larger
than the root or not
if (left < n && arr[left] > arr[largest])
{
largest = left;
}

if (right < n && arr[right] > arr[largest])

{
largest = right;
}

// if the root is smaller than the children then swap it

with the largest children's value
if (largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;

// again heapify that side of the heap where the

root has gone
heapify(arr, n, largest);
}
}

/* printf the array */

void print_array(int* arr, int n)
{
 for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}

Assignment 3: Graph as Adjacency Matrix

a) Write program that accepts the vertices and edges of a
graph and stores it as an adjacency matrix. Display the
adjacency matrix.
// C program for the above approach
#include <stdio.h>
// N vertices and M Edges
int N, M;

// Function to create Adjacency Matrix

void createAdjMatrix(int Adj[][N + 1],
int arr[][2])
{
// Initialise all value to this
// Adjacency list to zero
for (int i = 0; i < N + 1; i++) {
 for (int j = 0; j < N + 1; j++) {
Adj[i][j] = 0;
}
}
// Traverse the array of Edges
for (int i = 0; i < M; i++)
{
// Find X and Y of Edges
int x = arr[i][0];
int y = arr[i][1];

// Update value to 1
Adj[x][y] = 1;
Adj[y][x] = 1;
}
}
// Function to print the created
// Adjacency Matrix
void printAdjMatrix(int Adj[][N + 1])
{
// Traverse the Adj[][]
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
// Print the value at Adj[i][j]
printf("%d ", Adj[i][j]);
}
printf("\n");
}
}
// Driver Code
int main()
{
// Number of vertices
N = 5;
// Given Edges
int arr[][2]
= { { 1, 2 }, { 2, 3 },
{ 4, 5 }, { 1, 5 } };
// Number of Edges
 M = sizeof(arr) / sizeof(arr[0]);
// For Adjacency Matrix
int Adj[N + 1][N + 1];
// Function call to create
// Adjacency Matrix
createAdjMatrix(Adj, arr);
// Print Adjacency Matrix
printAdjMatrix(Adj);
return 0;
}
b)Write a C program that accepts the vertices and edges of a
graph and store it as an adjacency matrix. Implement
functions to print indegree, outdegree and total degree of all
vertices of graph.
#include<stdio.h>
#include<conio.h>
#define MAX 10
void accept_graph(int G[][MAX], int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("Edge (V%d,V%d) exists? (Yes=1, No=0):",i,j);
scanf("%d",&G[i][j]);
}
}
}
void disp_adj_mat(int G[][MAX], int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%4d",G[i][j]);
}
printf("\n");
}
}
void calc_out_degree(int G[][MAX], int n)
{
int i,j,sum;
for(i=0;i<n;i++)
{
sum=0;
for(j=0;j<n;j++)
{
sum += G[i][j];
}
printf("out-deg(V%d)=%d\n",i,sum);
}
}
void calc_in_degree(int G[][MAX], int n)
{
int i,j,sum;
for(i=0;i<n;i++)
{
sum=0;
for(j=0;j<n;j++)
{
sum += G[j][i];
}
printf("in-deg(V%d)=%d\n",i,sum);
}
}
void main()
{
int G[MAX][MAX],n; clrscr();
printf("Enter no.of vertices:");
scanf("%d",&n);
accept_graph(G,n);
printf("Adjacency Matrix:\n");
disp_adj_mat(G,n);
printf("Out degree:\n");
calc_out_degree(G,n);
printf("In degree:\n");
calc_in_degree(G,n);
}