Given the input string abcdefghij, construct a binary tree by inserting characters level by level — that is, fill nodes row-wise from left to right. The resulting tree must yield the following traversal outputs:

• In-order: hdibjeafcg
• Post-order: hidjebfgca
• Level-order: abcdefghij

The construction follows breadth-first insertion: the first character becomes the root; subsequent characters are asigned as left or right children in order, moving to the next node in the queue once both children are filled.

Below is an implementation that reads the input string, builds the tree using a queue-based insertion strategy, and prints the three required traevrsals — each on a separate line.

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

typedef char TreeNodeData;

typedef struct TreeNode {
    TreeNodeData value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

typedef struct QueueNode {
    TreeNode *node;
    struct QueueNode *next;
} QueueNode;

typedef struct {
    QueueNode *front;
    QueueNode *rear;
} Queue;

void enqueue(Queue *q, TreeNode *node) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

TreeNode *dequeue(Queue *q) {
    if (q->front == NULL) return NULL;
    QueueNode *temp = q->front;
    TreeNode *node = temp->node;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return node;
}

void inorder(TreeNode *root) {
    if (!root) return;
    inorder(root->left);
    printf("%c", root->value);
    inorder(root->right);
}

void postorder(TreeNode *root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    printf("%c", root->value);
}

void levelorder(TreeNode *root) {
    if (!root) return;
    Queue q = {NULL, NULL};
    enqueue(&q, root);
    while (q.front != NULL) {
        TreeNode *current = dequeue(&q);
        printf("%c", current->value);
        if (current->left) enqueue(&q, current->left);
        if (current->right) enqueue(&q, current->right);
    }
}

int main() {
    char input[12];
    scanf("%11s", input);

    if (input[0] == '\0') return 1;

    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->value = input[0];
    root->left = root->right = NULL;

    Queue buildQueue = {NULL, NULL};
    enqueue(&buildQueue, root);

    int idx = 1;
    while (input[idx] && buildQueue.front) {
        TreeNode *parent = dequeue(&buildQueue);

        if (input[idx]) {
            TreeNode *leftChild = (TreeNode *)malloc(sizeof(TreeNode));
            leftChild->value = input[idx];
            leftChild->left = leftChild->right = NULL;
            parent->left = leftChild;
            enqueue(&buildQueue, leftChild);
            idx++;
        }

        if (input[idx]) {
            TreeNode *rightChild = (TreeNode *)malloc(sizeof(TreeNode));
            rightChild->value = input[idx];
            rightChild->left = rightChild->right = NULL;
            parent->right = rightChild;
            enqueue(&buildQueue, rightChild);
            idx++;
        }
    }

    inorder(root);
    printf("\n");
    postorder(root);
    printf("\n");
    levelorder(root);
    printf("\n");

    return 0;
}