Scribd
Upload
10 views7 pages

DS Lab Program 10

The document outlines a C program for a menu-driven Binary Search Tree (BST) implementation that allows users to create a BST with a predefined set of integers, traverse it in different orders (inorder, preorder, postorder), search for elements, and delete elements. It includes the necessary functions for creating the tree, searching, deleting, and traversing the nodes. The program runs in a loop until the user chooses to exit.

Uploaded by

shwetha.csefac
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
10 views7 pages

DS Lab Program 10

The document outlines a C program for a menu-driven Binary Search Tree (BST) implementation that allows users to create a BST with a predefined set of integers, traverse it in different orders (inorder, preorder, postorder), search for elements, and delete elements. It includes the necessary functions for creating the tree, searching, deleting, and traversing the nodes. The program runs in a loop until the user chooses to exit.

Uploaded by

shwetha.csefac
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 7

Program 10 : Binary Search Tree

Develop a menu driven Program in C for the following operations on Binary Search
Tree (BST) of Integers .
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate message
d. Exit

#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;
}
NODE* search(NODE *node, int data)
{
if(node == NULL)
printf("\nElement not found");
else if(data < node->data)
{
node->left=search(node->left, data);
}
else if(data > node->data)
{
node->right=search(node->right, data);
}
else
printf("\nElement found is: %d", node->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;
}
NODE* del(NODE *node, int data)
{
NODE *temp;
if(node == NULL)
{
printf("\nElement not found");
}
else if(data < node->data)
{
node->left = del(node->left, data);
}
else if(data > node->data)
{
node->right = del(node->right, data);
}
else
{
if(node->right && node->left)
{
temp = findMin(node->right);
node -> data = temp->data;
node -> right = del(node->right,temp->data);
}
else
{
temp = node;
if(node->left == NULL)
node = node->right;
else if(node->right == NULL)
node = node->left;
free(temp);
}
}
return node;
}
void main()
{
int data, ch, i, n;
NODE *root=NULL;

while (1)
{
printf("\n1.Insertion in Binary Search Tree"); printf("\n2.Search Element in Binary Search
Tree");
printf("\n3.Delete Element in Binary Search Tree");
printf("\n4.Inorder\n5.Preorder\n6.Postorder\n7.Exit");
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 like(6,9,5,2,8,15,24,14,7,8,5,2)\n");
for(i=0; i<n; i++)
{
scanf("%d", &data);
root=createtree(root, data);
}
break;
case 2:printf("\nEnter the element to search: ");
scanf("%d", &data);
root=search(root, data);
break;
case 3:printf("\nEnter the element to delete: ");
scanf("%d", &data);
root=del(root, data);
break;
case 4:printf("\nInorder Traversal: \n");
inorder(root);
break;
case 5:printf("\nPreorder Traversal: \n");
preorder(root);
break;
case 6:printf("\nPostorder Traversal: \n");
postorder(root);
break;
case 7:exit(0);
default : printf("\nWrong option");
break;
}
}
}

OUTPUT –

You might also like