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

// Node structure for BST
typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} NODE;

// Function to create a new node
NODE* createNode(int value) {
    NODE *newNode = (NODE*)malloc(sizeof(NODE));
    if (!newNode) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Insert a value into BST
NODE* insertBST(NODE *root, int value) {
    if (root == NULL) {
        root = createNode(value);
    } else if (value < root->data) {
        root->left = insertBST(root->left, value);
    } else if (value > root->data) {
        root->right = insertBST(root->right, value);
    } else {
        // duplicate values are ignored (you can change this if needed)
        printf("Duplicate value %d ignored.\n", value);
    }
    return root;
}

// In-order traversal (Left, Root, Right)
void inorder(NODE *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

// Pre-order traversal (Root, Left, Right)
void preorder(NODE *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// Post-order traversal (Left, Right, Root)
void postorder(NODE *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    NODE *root = NULL;
    int n, i, value;

    printf("=== BINARY SEARCH TREE CONSTRUCTION & TRAVERSAL ===\n");

    printf("Enter number of nodes to insert: ");
    scanf("%d", &n);

    printf("Enter %d values:\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &value);
        root = insertBST(root, value);
    }

    printf("\nIn-order Traversal   : ");
    inorder(root);

    printf("\nPre-order Traversal  : ");
    preorder(root);

    printf("\nPost-order Traversal : ");
    postorder(root);

    printf("\n");

    return 0;
}