# 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.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://cs61b-2.gitbook.io/cs61b-textbook/26.-prefix-operations-and-tries/26.5-exercises.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.