#include <stdio.h>
#include <stdlib.h>

// Structure for a BST Node
struct Node {
    int data;
    struct Node *left, *right;
};

// Function to create a new node
struct Node* createNode(int item) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = item;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function to insert an element into BST
struct Node* insert(struct Node* node, int data) {
    if (node == NULL) return createNode(data);

    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    
    // Returns the unchanged node pointer
    return node;
}

// Traversal Functions
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

void preorder(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(struct Node* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

// Search Function
struct Node* search(struct Node* root, int key) {
    if (root == NULL || root->data == key)
        return root;
    
    if (root->data < key)
        return search(root->right, key);

    return search(root->left, key);
}

int main() {
    struct Node* root = NULL;
    int choice, n, key, i;
    int init_data[] = {6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2};
    int size = sizeof(init_data) / sizeof(init_data[0]);

    while (1) {
        printf("\n--- BST Operations Menu ---");
        printf("\n1. Create BST (using provided dataset)");
        printf("\n2. Traverse (Inorder, Preorder, Postorder)");
        printf("\n3. Search for a KEY");
        printf("\n4. Exit");
        printf("\nEnter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                for (i = 0; i < size; i++) {
                    root = insert(root, init_data[i]);
                }
                printf("\nBST Created with elements: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2\n");
                break;

            case 2:
                if (root == NULL) {
                    printf("\nTree is empty! Create it first.");
                } else {
                    printf("\nInorder Traversal: "); inorder(root);
                    printf("\nPreorder Traversal: "); preorder(root);
                    printf("\nPostorder Traversal: "); postorder(root);
                    printf("\n");
                }
                break;

            case 3:
                printf("\nEnter element to search: ");
                scanf("%d", &key);
                if (search(root, key))
                    printf("Element %d found in the BST.\n", key);
                else
                    printf("Element %d NOT found.\n", key);
                break;

            case 4:
                exit(0);

            default:
                printf("\nInvalid Choice!");
        }
    }
    return 0;
}