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

#define SIZE 256

struct tree
{
    char value[SIZE];
    struct tree *left;
    struct tree *right;
};

struct tree* read_tree()
{
    char buffer[SIZE];
    if (!fgets(buffer, SIZE, stdin) || buffer[0] == '\n' || buffer[0] == '\0')
    {
        return NULL;
    }

    buffer[strcspn(buffer, "\n")] = 0;

    struct tree *node = (struct tree*)malloc(sizeof(struct tree));
    assert(node != NULL);
    strcpy(node->value, buffer);

    if (buffer[0] != '*')
    {
        node->left = read_tree();
        node->right = read_tree();
    } 
    else
    {
        node->left = NULL;
        node->right = NULL;
    }

    return node;
};

void free_tree(struct tree *tree)
{
    if (tree == NULL)
    {
        return;
    }
    free_tree(tree->left);
    free_tree(tree->right);
    free(tree);
}

int count_leaf_nodes(struct tree *node)
{
    if (node == NULL)
    {
        return 0;
    }
    if (node->left == NULL && node->right == NULL)
    {
        return 1;
    }
    return count_leaf_nodes(node->left) + count_leaf_nodes(node->right);
}

int count_non_leaf_nodes(struct tree *node)
{
    if (node == NULL || (node->left == NULL && node->right == NULL))
    {
        return 0;
    }
    return 1 + count_non_leaf_nodes(node->left) + count_non_leaf_nodes(node->right);
}

void interact(struct tree *node, int fstenter)
{
    if (node == NULL)
    {
        return;
    }

    printf("%s\n", node->value);

    if (node->left == NULL && node->right == NULL)
    {
        printf("Koniec\n");
        return;
    }

    //while (scanf(" %c", &answer) == 1)
    char answer[SIZE];
    while (1) 
    {
        if (fgets(answer, sizeof(answer), stdin) == NULL)
        {
            printf("Koniec vstupu\n");
            break;
        }

        size_t len = strlen(answer);

        if (answer[len - 1] == '\n')
        {
            answer[len - 1] = '\0';
        }

        if (strlen(answer) != 1 || (answer[0] != 'a' && answer[0] != 'n'))
        {
            if(fstenter == 0)
            {
                fstenter = 1;
                continue;
            }
            else
            {
                printf("Nerozumiem\n");
                return;
            }
        }

        if (answer[0] == 'a')
        {
            interact(node->left, fstenter);
            return;
        }
        else if (answer[0] == 'n')
        {
            interact(node->right, fstenter);
            return;
        }

    }
}

int main()
{
    struct tree *root = read_tree();
    printf("Expert z bufetu to vie.\n");
    if(root == NULL)
    {
        printf("Chybna databaza\n");
        return 0;
    }
    //getchar();
    int leafs = count_leaf_nodes(root);
    if(leafs == 0)
    {
        printf("Chybna databaza\n");
        return 0;
    }
    printf("Pozna %d druhov ovocia a zeleniny.\n", leafs);
    printf("Odpovedajte 'a' pre prvu moznost alebo 'n' pre druhu moznost.\n");
    if (root == NULL)
    {
        printf("Chyba pri nacitani databazy pravidiel.\n");
        return 1;
    }
    int fstenter = 0;
    interact(root, fstenter);
    free_tree(root);

    return 0;
}