BST

#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;
}