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

// Definition of a binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

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

// Inorder traversal
void inorderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

// Preorder traversal
void preorderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// Postorder traversal
void postorderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->data);
}

// Test the tree traversal algorithms
int main() {
    // Create a sample binary tree
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    int choice;
    printf("Choose the type of traversal:\n");
    printf("1. Inorder traversal\n");
    printf("2. Preorder traversal\n");
    printf("3. Postorder traversal\n");
    scanf("%d", &choice);

    switch (choice) {
        case 1:
            printf("Inorder traversal: ");
            inorderTraversal(root);
            printf("\n");
            break;
        case 2:
            printf("Preorder traversal: ");
            preorderTraversal(root);
            printf("\n");
            break;
        case 3:
            printf("Postorder traversal: ");
            postorderTraversal(root);
            printf("\n");
            break;
        default:
            printf("Invalid choice\n");
            break;
    }

    return 0;
}