> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/26.-prefix-operations-and-tries/26.5-exercises.md).

# 26.5 Exercises

## Factual

1. Suppose we use the following trie to represent a map. What would `get("sea")` return? What about `get("sell")`?

<figure><img src="/files/BY4Ypd4wNBxd7GZge6uz" alt=""><figcaption></figcaption></figure>

2. Consider the Trie-based set below. What does `keysWithPrefix("sp")` return? What nodes does it visit during this call?

![](/files/xv47iwVJ0RDMFfWbbz42)

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.

<details>

<summary>Problem 1</summary>

`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.

</details>

<details>

<summary>Problem 2</summary>

`keysWithPrefix` follows the prefix to the final letter of the prefix, then performs DFS from that node to get all children.&#x20;

During this procedure, it traverses the nodes `s, p, i, t, e, y`. The final return value is `spit, spite, spy`.

</details>

<details>

<summary>Problem 3</summary>

$$\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.

</details>

## 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.

<details>

<summary>Problem 1</summary>

**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.

</details>