Tries — Chapter Quiz · Data Structures & Algorithms

Question 1

1

What is the time complexity of inserting a word of length m into a trie?

AO(n) where n is the number of words already in the trieBO(m)CO(m log n)DO(m · n)

Insertion follows (or creates) exactly m nodes — one per character. The operation is independent of how many words are already stored, giving O(m) time.

Question 2

2

How does a trie implement startsWith(prefix) efficiently?

AIt iterates all stored words and calls word.startsWith(prefix)BIt traverses the trie following the characters of prefix; if all characters exist, the prefix is presentCIt uses a hash set of all prefixes built at construction timeDIt performs a BFS from the root and counts matching nodes

startsWith is just a search that stops after the prefix — it does not need to reach an end-of-word marker. This is O(m) where m is the prefix length, regardless of how many words share it.

Question 3

3

In which scenario does a trie outperform a hash set of strings?

AChecking exact membership for a single wordBFinding all words that share a given prefix (prefix enumeration)CStoring integers efficientlyDRandom access by numeric index

A hash set checks exact membership in O(m) but can't efficiently enumerate all words with a given prefix. A trie naturally supports prefix queries — you traverse to the prefix node and DFS its subtree to collect all matching words.

Question 4

4

What does the isEndOfWord (or isLeaf) flag on a trie node signify?

AThe node has no childrenBA complete word ends at this nodeCThe node stores a numeric frequency countDThe character at this node is uppercase

Multiple words may share a path prefix. The isEndOfWord flag distinguishes nodes that terminate an actual word (e.g., "car") from intermediate nodes that are only prefixes (e.g., "ca" when only "car" and "card" are stored).

Question 5

5

A suffix trie built from a string of length n stores all suffixes. What is its space complexity?

AO(n)BO(n log n)CO(n²) in the worst case (e.g., for a string of all unique characters)DO(1)

A naive suffix trie inserts all n suffixes, the i-th having length n-i. The total characters across all suffixes is n + (n-1) + … + 1 = O(n²). Suffix arrays and suffix automata reduce this, but the basic trie is O(n²).

Question 6

6

A trie node for an alphabet of size k (e.g., 26 letters) stores exactly k child pointers, but many may be null.

TTrueFFalse

Each trie node has an array (or map) of k child references. In a sparse trie most children are null, wasting memory. A Map-backed children object stores only existing children, reducing space at the cost of slightly slower lookup.

Question 7

7

An autocomplete feature that retrieves all words with a given prefix from a trie performs a DFS (or BFS) over the ___ of the prefix's terminal node.

After locating the node corresponding to the last character of the prefix, a DFS over its subtree collects every isEndOfWord node, each representing one matching word.

Question 8

8

Which of the following are practical applications of tries? (Select all that apply)

Select all that apply.

AAutocomplete and type-ahead searchBSpell checking (finding valid words or close misspellings)CIP routing table lookup (using binary tries on address bits)DFinding the median of a stream of integers

Tries are used in autocomplete, spell checking, and longest-prefix matching in IP routers (where each bit of the IP address is a branch). Median-of-a-stream is solved with two heaps, not a trie.

Test what you learned.