1. Suppose you insert the following strings into a trie that is initially empty. After inserting all four strings, how many nodes will the trie contain?

beverage benediction benevolence benign

2. Consider the trie you constructed in the previous question. How many unique three-letter strings could you insert into that trie without creating any new nodes? (By "unique," I mean that you should not account for the insertion of multiple instances of some string.)

3. What is the best-case runtime for checking whether a trie contains a particular string? Select all that apply.

A) O(n), where n is the number of nodes in the trie

B) O(n), where n is the number of strings that have been inserted into the trie

C) O(n), where n is the length of the string we're searching for

D) O(1), because it's possible for the trie to have just one node (the root node)

E) O(1), because the string we're searching for could have a single character

F) O(1), because the trie could be empty

G) O(1), because the string we're searching for could be the empty string (i.e., it has zero characters)

H) O(1), because the first letter in the string we're searching for might not be represented in the trie

I) O(1), because the string we're searching for might be the prefix of a much longer string (i.e., searching for "be" when the trie contains "benevolent")