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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* newNode(int val) {
    struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* buildTree(char* str) {
    int len = strlen(str);
    if (len == 0 || str[0] == 'N') {
        return NULL;
    }
    int i = 0, j = 0, numTokens = 0;
    char* tokens[1000];
    while (i < len) {
        j = i;
        while (j < len && str[j] != ' ') {
            j++;
        }
        tokens[numTokens] = (char*) malloc(sizeof(char) * (j - i + 1));
        strncpy(tokens[numTokens], str + i, j - i);
        tokens[numTokens][j - i] = '\0';
        numTokens++;
        i = j + 1;
    }
    struct TreeNode* root = newNode(atoi(tokens[0]));
    struct TreeNode** queue = (struct TreeNode**) malloc(sizeof(struct TreeNode*) * numTokens);
    int front = 0, rear = 0;
    queue[rear++] = root;
    i = 1;
    while (front != rear && i < numTokens) {
        struct TreeNode* parent = queue[front++];
        char* currVal = tokens[i++];
        if (currVal[0] != 'N') {
            int val = atoi(currVal);
            struct TreeNode* leftChild = newNode(val);
            parent->left = leftChild;
            queue[rear++] = leftChild;
        }
        if (i >= numTokens) {
            break;
        }
        currVal = tokens[i++];
        if (currVal[0] != 'N') {
            int val = atoi(currVal);
            struct TreeNode* rightChild = newNode(val);
            parent->right = rightChild;
            queue[rear++] = rightChild;
        }
    }
    free(queue);
    for (i = 0; i < numTokens; i++) {
        free(tokens[i]);
    }
    return root;
}
void inorderTraversal(struct TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        printf("%d ", root->val);
        inorderTraversal(root->right);
    }
}
int main() {
    //char str[] = "1 2 3 N N 4 5";
    char str[1000];
    //printf("Enter a string: ");
    fgets(str, sizeof(str), stdin);
    struct TreeNode* root = buildTree(str);
    inorderTraversal(root);
    // do something with the tree...
    return 0;
}