In: Computer Science
You are given a trie that was built from a list of n (potentially non-unique) words, in which the longest word has length m. What is the best-case memory requirement for the trie (as a function of m and/or n)? What is the worst-case memory requirement? Draw a small example trie showing the data in both of the cases, and describe the dictionary inputs.