Language: C99

You must complete the implementation of a trie data structure (pronounced "try"), a tree where each node has 26 children (corresponding to the 26 letters of the alphabet).

To understand a trie, it is best to see a concrete example. Note that empty boxes are either false or NULL.

The following trie stores the words "a", "ace" and "zoo".

To see how the word "ace" is stored, consider that the first letter of the word is 'a', which is also the first letter of the alphabet. From the root node, we follow the first child link to the next node. This node is part of words that start with the letter 'a'. Because the string "a" is contained in the trie, the value of end_word at this node is TRUE (filled in). You can think of this as corresponding to the null terminator for the word "a". The next letter in the word "ace" is 'c' (third letter of the alphabet) and so we follow the third child to the next node. The word "ac" is not a valid word, so the value of end_word here is false. Because the next letter 'e' is the fifth letter of the alphabet, we follow the fifth child. There are no additional letters in the word "ace", so the end_word at this node is TRUE to indicate that word "ace" ends there.

As an exercise, review how "zoo" is similarly stored.

We can now make a few observations about the structure of the tree. Each leaf in the tree must have end_word be true, and all of its children must be NULL, otherwise it would not be a valid leaf. Also, if the value of end_word is true at the root, then the empty string ""is contained in the trie. If there are no words in the trie, then the value of root would be NULL.

Write the following functions:

// A word only contains lowercase letters ('a'...'z') // an empty string ("") is also considered a word

// requirements: ALL string and trie parameters are valid (non-NULL) // string parameters are words

struct trienode { bool word_end; struct trienode *children[26]; };

struct trie { struct trienode *root; };

// trie_create() creates a new empty trie // effects: allocates memory (must call trie_destroy) struct trie *trie_create(void);

// trie_add(s, t) adds the word s to trie t // effects: modifies t // time: O(n), n is the length of s void trie_add(const char *s, struct trie *t);

// trie_remove(s, t) removes the word s from trie t (if it exists) // and removes any trienodes that are no longer needed // effects: may modify t // time: O(n), n is the length of s void trie_remove(const char *s, struct trie *t);

// trie_lookup(s, t) determines if t contains the word s // time: O(n), n is the length of s bool trie_lookup(const char *s, const struct trie *t);

// trie_destroy(t) frees all memory for t // effects: t is no longer valid // time: O(n), n is the number of characters in all of the words in t void trie_destroy(struct trie *t);

// trie_print(t) prints each word in trie t in alphabetical order, // with each word on a newline // effects: displays output (if t is not empty) // time: O(n), n is the number of characters in all of the words in t void trie_print(const struct trie *t);

// trie_to_aos(t) generates a new array containing all of the words // in trie t in alphabetical order, each word is a new string // notes: returns NULL if t is empty // use trie_count(t) to determine the length of the array // effects: allocates memory (caller must free all strings and the array) // time: O(n), n is the number of characters in all of the words in t char **trie_to_aos(const struct trie *t);

// trie_count(t) determines how many words are in t // time: O(n), n is the number of characters in all of the words in t int trie_count(const struct trie *t);

root endword - end word end word end word end word end word end word