Questions: Tries (Prefix Trees)

Question 1

A trie stores 1,000,000 words from a dictionary. How long does it take to look up whether the word 'algorithm' (10 characters) is present?

• A. O(1,000,000) — the query must be compared against all stored words
• B. O(log 1,000,000) ≈ O(20) — binary search over sorted dictionary entries
• C. O(10) — one edge traversal per character in the query string
• D. O(10 × 1,000,000) — each character must be checked against all stored strings

Answer: (C)

Trie lookup is O(m) where m is the length of the query string — independent of the number of stored strings. At each node you follow exactly one edge for the next character; if the edge is missing, the word is absent; if you reach the end with an end-of-word flag, the word is present. The dictionary size introduces no additional comparisons — this is the key advantage over sorted arrays or hash tables for string lookups.

Question 2

Why are tries better than hash sets for autocomplete functionality?

• A. Tries guarantee O(1) lookup while hash sets are O(m) for string keys
• B. Tries store words in sorted alphabetical order, enabling binary search on suggestions
• C. Tries support prefix queries natively — navigating to a prefix node puts you at the root of all matching completions
• D. Tries use less memory than hash sets for large vocabularies with long strings

Answer: (C)

A hash set answers 'does this exact string exist?' efficiently but has no structural connection between 'pre-' and 'prefix', 'preview', 'prevent', etc. In a trie, navigating p→r→e puts you at a node whose entire subtree consists of words starting with 'pre'. Collecting completions is then a simple DFS from that node — an operation that has no efficient analog in a hash set.

Question 3

A trie storing 10,000 words is slower to search than a trie storing 100 words, assuming the query string is the same length.

• T. True
• F. False

Answer: False

Trie search time is O(m) — the length of the query — regardless of how many words are stored. Each step follows one labeled edge; the dictionary size adds no additional traversal steps. This dictionary-size independence is precisely what distinguishes trie lookup from hash-table lookup (which can degrade with collisions) and binary search (which is O(log n)).

Question 4

In a trie, most node reachable from the root represents a complete stored word.

• T. True
• F. False

Answer: False

Most nodes represent prefixes, not complete words. A trie storing 'car' and 'card' has nodes at c, ca, car, and card. The 'car' node is marked as a word end, but 'c' and 'ca' are purely intermediate — they may represent no stored word at all. The end-of-word boolean flag is what distinguishes complete words from intermediate prefix nodes.

Question 5

Why does a trie consume more memory than a hash set when stored strings share few common prefixes, and when does the trade-off reverse?

Model answer: Each trie node stores a dictionary (or fixed-size array) of potential child pointers — one slot per possible character. With few shared prefixes, most nodes have mostly-empty child slots: a lot of wasted space for each unique character path. A hash set stores only the full strings compactly. The trade-off reverses when strings heavily share prefixes: each shared prefix character is stored in one node rather than repeated in every string, making the trie more space-efficient. Autocomplete dictionaries (thousands of words sharing 'un-', 'pre-', 'com-' etc.) are the canonical case where tries win on both time and space.

The memory trade-off depends directly on prefix overlap in the data. The trie's structural advantage — shared storage for shared prefixes — only pays off when that sharing actually exists. This is why domain-specific knowledge (is this a natural-language word set or arbitrary strings?) informs which structure to choose.