# 26.5 Exercises
## Factual
1. Suppose we use the following trie to represent a map. What would `get("sea")` return? What about `get("sell")`?
2. Consider the Trie-based set below. What does `keysWithPrefix("sp")` return? What nodes does it visit during this call?
3. What is the worst-case runtime when searching for a single word in a trie? Let $$R$$ be the size of the alphabet, and $$N$$ be the number of items in the trie, and $$L$$ be the length of the word being operated on.
Problem 1
`sea` terminates at the node with value 6. `sell` does not exist in the trie (since it does not terminate at the node with `l`, so the `get` operation returns null.
Problem 2
`keysWithPrefix` follows the prefix to the final letter of the prefix, then performs DFS from that node to get all children.
During this procedure, it traverses the nodes `s, p, i, t, e, y`. The final return value is `spit, spite, spy`.
Problem 3
$$\Theta(L)$$. In the worst case, the word is a prefix of some other word in the trie, but is not present in the trie itself. In this case, we go through all the letters of the word.
## Metacognitive
1. Compare the worst-case number of character comparisons required to insert a word into an LLRB, hash table, and R-way trie. Let $$R$$ be the size of the alphabet, and $$N$$ be the number of items in the trie, and $$L$$ be the maximum length of any word.
Problem 1
**LLRB**: We always insert at the bottom of the LLRB, so there are $$\Theta(\log N)$$comparisons to figure out where the new node goes. Each word comparison takes up to $$L$$ character comparisons. Thus, there are $$\Theta(L \log N)$$ comparisons.
**Hash table**: In the worst case, all items hash to the same bucket. On an insertion, we must compare a word to all other words in the bucket for equality. Assuming this bucket has $$N$$ items, this takes $$\Theta(LN)$$ comparisons.
**R-way trie**: In the worst case, we follow or create $$L$$ nodes to the end of the word. Thus, there are at most $$\Theta(L)$$ comparisons.
