#include <stdio.h>
#include <stdlib.h>
 
// Structure for a binary tree node
struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};
 
// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
 
// Function to insert nodes manually (for demonstration)
struct Node* createBinaryTree() {
    int value;
    struct Node *root = NULL;
    struct Node *temp, *newNode;
    int choice;
 
    printf("Enter data for root node: ");
    scanf("%d", &value);
    root = createNode(value);
 
    while (1) {
        printf("\nEnter data for new node (-1 to stop): ");
        scanf("%d", &value);
        if (value == -1)
            break;
 
        newNode = createNode(value);
        temp = root;
 
        while (1) {
            printf("Insert %d to the Left(1) or Right(2) of %d? ", value, temp->data);
            scanf("%d", &choice);
 
            if (choice == 1) {
                if (temp->left == NULL) {
                    temp->left = newNode;
                    break;
                } else {
                    temp = temp->left;
                }
            } else if (choice == 2) {
                if (temp->right == NULL) {
                    temp->right = newNode;
                    break;
                } else {
                    temp = temp->right;
                }
            } else {
                printf("Invalid choice! Enter 1 or 2.\n");
            }
        }
    }
 
    return root;
}
 
// Recursive 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);
    }
}
 
// Main Function
int main() {
    struct Node* root = NULL;
 
    printf("\n=== Binary Tree Creation ===\n");
    root = createBinaryTree();
 
    printf("\nInorder Traversal: ");
    inorder(root);
 
    printf("\nPreorder Traversal: ");
    preorder(root);
 
    printf("\nPostorder Traversal: ");
    postorder(root);
 
    printf("\n");
    return 0;
}