/* TODO:
1) Width
2) WidthTraversal
*/

#include <stdio.h>
#include <mm_malloc.h>
#include <stdbool.h>

typedef struct _node Node;

struct _node {
    int value;
    Node* left;
    Node* right;
};

size_t sizeOfTree = 0;
size_t maxHeight = 0;

void findHeight(Node* root, size_t curHeight) {
    if (root -> left) {
        findHeight(root -> left, curHeight + 1);
    }
    if (root -> right) {
        findHeight(root -> right, curHeight + 1);
    }
    if (curHeight > maxHeight) {
        maxHeight = curHeight;
    }
}

void infixTraversal(Node *root) {
    if (root -> left) {
        infixTraversal(root->left);
    }
    printf("%d ", root -> value);
    if (root -> right) {
        infixTraversal(root->right);
    }
}
void prefixTraversal(Node *root) {
    printf("%d ", root -> value);
    if (root -> left) {
        prefixTraversal(root->left);
    }
    if (root -> right) {
        prefixTraversal(root->right);
    }
}
void postfixTraversal(Node *root) {
    if (root -> left) {
        postfixTraversal(root->left);
    }
    if (root -> right) {
        postfixTraversal(root->right);
    }
    printf("%d ", root -> value);
}

bool exist(int value, Node* root) {
    if (!root) {
        return false;
    } else if (value == root -> value) {
        return true;
    }

    return exist(value, root -> left) || exist(value, root -> right);
}

void insert(int value, Node* root) {
    if (exist(value, root)) {
        return;
    }

    if (sizeOfTree == 0) {
        root -> value = value;
        sizeOfTree++;
        return;
    }

    if (value < root -> value) {
        if (root -> left) {
            insert(value, root -> left);
        } else {
            root -> left = calloc(1, sizeof(Node));
            root -> left -> value = value;
            sizeOfTree++;
            return;
        }
    } else {
        if (root -> right) {
            insert(value, root -> right);
        } else {
            root -> right = calloc(1, sizeof(Node));
            root -> right -> value = value;
            sizeOfTree++;
            return;
        }
    }
}

void run() {
    Node* root = calloc(1, sizeof(Node));
    int element;
    FILE* fileIn = fopen("in.txt", "r");
    while (!feof(fileIn)) {
        if (fscanf(fileIn, "%d", &element) != 0) {
            insert(element, root);
        }
    }
    findHeight(root, 0);
    printf("%zu\n", maxHeight);
    infixTraversal(root);
    printf("\n");
    prefixTraversal(root);
    printf("\n");
    postfixTraversal(root);
}

int main() {
    run();
    return 0;
}