Binary Search Tree

#include <iostream> using namespace std; struct Node { int Data; struct Node *Left; struct Node *Right; }; struct Node *insert(struct Node *Root, int X) { if (Root == NULL) { Root = new Node; //(struct Node *) malloc(sizeof(struct Node)) Root -> Data = X; Root -> Left = NULL; Root -> Right = NULL; } else { if (Root -> Data > X) Root -> Left = insert(Root -> Left, X); else if (Root -> Data < X) Root -> Right = insert(Root -> Right, X); } return Root; } void preOrder(struct Node *Root) { if (Root != NULL) { cout << Root -> Data << " "; preOrder(Root -> Left); preOrder(Root -> Right); } } void inOrder(struct Node *Root) { if (Root != NULL) { inOrder(Root -> Left); cout << Root -> Data << " "; inOrder(Root -> Right); } } void postOrder(struct Node *Root) { if (Root != NULL) { postOrder(Root -> Left); postOrder(Root -> Right); cout << Root -> Data << " "; } } bool Search(struct Node *Root, int X) { if (Root != NULL) { if (Root -> Data == X) return true; else { if (Root -> Data > X) return Search(Root -> Left, X); else return Search(Root -> Right, X); } } else return false; } struct Node *DeleteNodeLeft(struct Node *Root) { if (Root -> Right != NULL) { int temp = Root -> Data; Root -> Data = Root -> Right -> Data; Root -> Right -> Data = temp; Root -> Right = DeleteNodeLeft(Root -> Right); } else if (Root -> Left != NULL) { int temp = Root -> Data; Root -> Data = Root -> Left -> Data; Root -> Left -> Data = temp; Root -> Left = DeleteNodeLeft(Root -> Left); } else { delete Root; return NULL; } } struct Node *DeleteNodeRight(struct Node *Root) { if (Root -> Left != NULL) { int temp = Root -> Data; Root -> Data = Root -> Left -> Data; Root -> Left -> Data = temp; Root -> Left = DeleteNodeRight(Root -> Left); } else if (Root -> Right != NULL) { int temp = Root -> Data; Root -> Data = Root -> Right -> Data; Root -> Right -> Data = temp; Root -> Right = DeleteNodeRight(Root -> Right); } else { delete Root; return NULL; } } struct Node *Delete(struct Node *Root, int X) { for (struct Node *Parent = NULL, *Current = Root; Current; Parent = Current, Current = Current -> Data < X ? Current -> Right: Current -> Left) { if (Current -> Data == X) { if (Current == Root) { if (Root -> Left != NULL) Root = DeleteNodeLeft(Root); else if (Root -> Right != NULL) Root = DeleteNodeRight(Root); else { Root = NULL; delete Current; } } else { if (Parent -> Left == Current) Parent -> Left = DeleteNodeLeft(Current); else Parent -> Right = DeleteNodeRight(Current); } } } return Root; } int main() { int num, choice; struct Node *Root = NULL; while (true) { cout << "Tree Operations" << endl; cout << "---------------" << endl; cout << "1. Insert" << endl; cout << "2. PreOrder Travarse" << endl; cout << "3. InOrder Travarse" << endl; cout << "4. PostOrder Travarse" << endl; cout << "5. Delete" << endl; cout << "6. Search" << endl; cout << "0. Exit" << endl; cout << "Enter Your Choice: "; cin >> choice; switch (choice) { case 1: cout << "Enter the Number to Insert: "; cin >> num; Root = insert(Root, num); break; case 2: if (Root == NULL) cout << "Tree is Empty"; else preOrder(Root); cout << endl; break; case 3: if (Root == NULL) cout << "Tree is Empty"; else inOrder(Root); cout << endl; break; case 4: if (Root == NULL) cout << "Tree is Empty"; else postOrder(Root); cout << endl; break; case 5: if (Root == NULL) cout << "Tree is Empty"; else { cout << "Enter Number to Delete: "; cin >> num; if (Search(Root, num) == false) cout << num << " Not Found" << endl; else Root = Delete(Root, num); } break; case 6: cout << "Enter Number to Search: "; cin >> num; if (Search(Root, num) == true) cout << num << " Found" << endl; else cout << num << " Not Found" << endl; break; case 0: return 0; default: cout << "Invalid Choice" << endl; } cout << endl << endl; } return 0; }