#include #include<stdlib.h>

using namespace std;

struct treeNode { int data; treeNode *left; treeNode right; }; treeNode FindMin(treeNode node) { if(node==NULL) { / There is no element in the tree / return NULL; } if(node->left) / Go to the left sub tree to find the min element / return FindMin(node->left); else return node; } treeNode FindMax(treeNode node) { if(node==NULL) { / There is no element in the tree / return NULL; } if(node->right) / Go to the left sub tree to find the min element */ return(FindMax(node->right)); else return node; } treeNode *Insert(treeNode *node,int data) { if(node==NULL) { treeNode *temp; temp=new treeNode; //temp = (treeNode )malloc(sizeof(treeNode)); temp -> data = data; temp -> left = temp -> right = NULL; return temp; } if(data >(node->data)) { node->right = Insert(node->right,data); } else if(data < (node->data)) { node->left = Insert(node->left,data); } / Else there is nothing to do as the data is already in the tree. */ return node; } treeNode * Delet(treeNode *node, int data) { treeNode temp; if(node==NULL) { cout<<"Element Not Found"; } else if(data < node->data) { node->left = Delet(node->left, data); } else if(data > node->data) { node->right = Delet(node->right, data); } else { / Now We can delete this node and replace with either minimum element in the right sub tree or maximum element in the left subtree / if(node->right && node->left) { / Here we will replace with minimum element in the right sub tree / temp = FindMin(node->right); node -> data = temp->data; / As we replaced it with some other node, we have to delete that node / node -> right = Delet(node->right,temp->data); } else { / If there is only one or zero children then we can directly remove it from the tree and connect its parent to its child / temp = node; if(node->left == NULL) node = node->right; else if(node->right == NULL) node = node->left; free(temp); / temp is longer required */ } } return node; } treeNode * Find(treeNode node, int data) { if(node==NULL) { / Element is not found / return NULL; } if(data > node->data) { / Search in the right sub tree. / return Find(node->right,data); } else if(data < node->data) { / Search in the left sub tree. / return Find(node->left,data); } else { / Element Found */ return node; } } void Inorder(treeNode *node) { if(node==NULL) { return; } Inorder(node->left); cout<data<<" "; Inorder(node->right); } void Preorder(treeNode *node) { if(node==NULL) { return; } cout<data<<" "; Preorder(node->left); Preorder(node->right); } void Postorder(treeNode *node) { if(node==NULL) { return; } Postorder(node->left); Postorder(node->right); cout<data<<" "; } int main() { treeNode *root = NULL,*temp; int ch; //clrscr(); while(1) { cout<<"\n1.Insert\n2.Delete\n3.Inorder\n4.Preorder\n5.Postorder\n6.FindMin\n7.FindMax\n8.Search\n9.Exit\n"; cout<<"Enter ur choice:"; cin>>ch; switch(ch) { case 1: cout<<"\nEnter element to be insert:"; cin>>ch; root = Insert(root, ch); cout<<"\nElements in BST are:"; Inorder(root); break; case 2: cout<<"\nEnter element to be deleted:"; cin>>ch; root = Delet(root,ch); cout<<"\nAfter deletion elements in BST are:"; Inorder(root); break; case 3: cout<<"\nInorder Travesals is:"; Inorder(root); break; case 4: cout<<"\nPreorder Traversals is:"; Preorder(root); break; case 5: cout<<"\nPostorder Traversals is:"; Postorder(root); break; case 6: temp = FindMin(root); cout<<"\nMinimum element is :"<data; break; case 7: temp = FindMax(root); cout<<"\nMaximum element is :"<data; break; case 8: cout<<"\nEnter element to be searched:"; cin>>ch; temp = Find(root,ch); if(temp==NULL) { cout<<"Element is not foundn"; } else { cout<<"Element "<data<<" is Found\n"; } break; case 9: exit(0); break; default: cout<<"\nEnter correct choice:"; break; } } return 0; } /*OUTPUT:

1.Insert 2.Delete 3.Inorder 4.Preorder 5.Postorder 6.FindMin 7.FindMax 8.Search 9.Exit Enter ur choice:1

Enter element to be insert:2

Elements in BST are:2 1.Insert 2.Delete 3.Inorder 4.Preorder 5.Postorder 6.FindMin 7.FindMax 8.Search 9.Exit Enter ur choice:1

Enter element to be insert:5

Elements in BST are:2 5 1.Insert 2.Delete 3.Inorder 4.Preorder 5.Postorder 6.FindMin 7.FindMax 8.Search 9.Exit Enter ur choice:8

Enter element to be searched:2 Element 2 is Found 1.Insert 2.Delete 3.Inorder 4.Preorder 5.Postorder 6.FindMin 7.FindMax 8.Search 9.Exit Enter ur choice:9*/