// Arup Guha
// 7/27/2020
// Solution to 2020 Summer COP 3502 Final Exam Part B Q3

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

typedef struct trienode {
    int isWord;
    struct trienode* next[26];
} trienode;

int maxWordLength(trienode* root);
trienode* init();
void insert(trienode* root, char word[]);

int main(void) {

    // Our test.
    trienode* root = init();
    insert(root, "apple");
    insert(root, "banana");
    insert(root, "can");
    insert(root, "cantaloupe");
    insert(root, "dragon");
    insert(root, "antidisestablishmentarianism");
    insert(root, "antique");
    insert(root, "ant");
    printf("%d\n", maxWordLength(root));
    return 0;
}

int maxWordLength(trienode* root) {

    // Weird base case, but when you test this is what you see works.
	if (root == NULL) return -1;

    // Empty case.
	int bestkid = -1;

	// Now, try each child.
    for (int i=0; i<26; i++) {

        // Basically just store the max of all possible paths.
        int thiskid = maxWordLength(root->next[i]);
        if (thiskid > bestkid) bestkid = thiskid;
    }

    // Add 1 to the best you see.
    return bestkid+1;
}

// Returns a single trie node.
trienode* init() {
    trienode* tmp = malloc(sizeof(trienode));
    tmp->isWord = 0;
    for (int i=0; i<26; i++) tmp->next[i] = NULL;
    return tmp;
}

// Iteratively inserts word into the trie pointed to by root.
void insert(trienode* root, char word[]) {

    int n = strlen(word);

    for (int i=0; i<n; i++) {
        if (root->next[word[i]-'a'] == NULL)
            root->next[word[i]-'a'] = init();
        root = root->next[word[i]-'a'];
    }
    root->isWord = 1;
}