BinarySearchTree

#include <iostream>
#include <cstdlib>
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 << " ";
    }
}

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 << "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 0: {
                exit(0);
            }
            default: {
                cout << "Invalid Choice" << endl;
            }
        }
        cout << endl << endl;
    }
    return 0;
}