// Arup Guha
// 12/5/2023
// Code for 2023 COP 3502 Final Exam Part B Question 10 - Both Versions

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

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

void printfirst(trienode* root);
void printlast(trienode* root);
void insert(trienode* root, char* word);
trienode* makeNode() ;
void freetrie(trienode* root);

int main() {

    // A solid test case...
    trienode* root = makeNode();
    insert(root, "cat");
    insert(root, "dog");
    insert(root, "elephant");
    insert(root, "barrier");
    insert(root, "bar");
    insert(root, "bartow");
    insert(root, "ele");

    // Test both.
    printfirst(root);
    printf("\n");
    printlast(root);
    printf("\n");

    // Clean up.
    freetrie(root);

    return 0;
}

// If we asuume root is not NULL this works.
void printfirst(trienode* root) {

    // We stop the first time we get to a word because am comes before amber.
    if (root->isWord) return;

    // Must go left to right, from a to z.
    for (int i=0; i<26; i++) {

        // Get the firt non-null link!
        if (root->next[i] != NULL) {

            // This is the letter we want.
            printf("%c", (char)('a'+i));

            // Recurse.
            printfirst(root->next[i]);

            // We must break or return so we don't print too much.
            break;
        }
    }
}

void printlast(trienode* root) {

    // We need this now.
    if (root == NULL) return;

    /*** Don't stop if this node is a word because zoology comes AFTER zoo. ***/

    // Must go backwards, from z to a.
    for (int i=25; i>=0; i--) {

        // Go to the last alpha letter for which a word exists.
        if (root->next[i] != NULL) {

            // Print it.
            printf("%c", (char)('a'+i));

            // Recurse.
            printlast(root->next[i]);

            // Get out.
            break;
        }
    }
}

// Inserts word into the trie pointed to by root, iteratively.
void insert(trienode* root, char* word) {
    int len = strlen(word);
    for (int i=0; i<len; i++) {
        if (root->next[word[i]-'a'] == NULL)
            root->next[word[i]-'a'] = makeNode();
        root = root->next[word[i]-'a'];
    }
    root->isWord = 1;
}

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

// Frees the memory pointed to by root in this trie.
void freetrie(trienode* root) {
    if (root == NULL) return;
    for (int i=0; i<26; i++)
        freetrie(root->next[i]);
    free(root);
}