Write down code for BST with following
operations 1) Create function 2) Insertion function
3) Search function 4) Delete function 5) Display
with all options: Preorder,Inorder and Postorder
Source code
#include <iostream>
using namespace std;
struct node {
int key;
struct node *left, *right;
};
//creation
struct node *newNode(int item)
{
struct node *temp = new node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
//traversal
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
}
void preorder(struct node* root)
{
if(root!=NULL)
{
cout<<root->key<<" ";
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct node* root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
cout<<root->key<<" ";
}
}
//insertion
struct node *insert(struct node *node, int key) {
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
// inorder successor
struct node *minValueNode(struct node *node)
{
struct node *current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
// Deleting a node
struct node *deleteNode(struct node *root, int key)
{
if (root == NULL)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else
{
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
struct node *temp = minValueNode(root-
>right);
root->key = temp->key;
root->right = deleteNode(root->right, temp-
>key);
}
return root;
}
int main()
{
struct node *root = NULL;
int choice;
cout<<"enter 1 to insert"<<endl;
cout<<"enter 2 to delete"<<endl;
cout<<"enter 3 to display"<<endl;
cin>>choice;
while(choice>=1 && choice <=3)
{
if(choice==1)
{
int item;
cout<<"enter the element to be
inserted"<<endl;
cin>>item;
root=insert(root,item);
}
else if(choice==2)
{
int element;
cout<<"enter element to be
deleted"<<endl;
cin>>element;
root = deleteNode(root, element);
}
else if(choice==3)
{
int x;
cout<<"enter 1 for inorder
traversal"<<endl;
cout<<"enter 2 for preorder
traversal"<<endl;
cout<<"enter 3 for postorder
traversal"<<endl;
cin>>x;
if(x==1)
inorder(root);
else if(x==2)
preorder(root);
else if(x==3)
postorder(root);
}
cout<<endl;
cout<<"enter 1 to insert"<<endl;
cout<<"enter 2 to delete"<<endl;
cout<<"enter 3 to display"<<endl;
cin>>choice;
}
}
Output
