Noesis
3.4.14 · D5Trees

Question bank — Trie (prefix tree) — insert, search, startsWith, applications (autocomplete, spell check)

1,708 words8 min read↑ Back to topic

Every term used below is built in the parent note: a trie is a tree where each root-to-node path spells a prefix, each node carries an isEnd flag (true only where an inserted word ends), and the root is the empty string "".

True or false — justify

TF1. search and startsWith walk the same path through the trie.
True — both descend one node per character from the root; they differ only in the final check: search returns node.isEnd, startsWith returns True.
TF2. If startsWith("ca") is True, then search("ca") is also True.
False — the path c→a existing only proves ca is a prefix of some word (like car); search also requires isEnd to be set at the a node, which it is not unless ca itself was inserted.
TF3. If search("card") is True, then startsWith("car") must be True.
True — to reach card's end node you must have walked through the c→a→r nodes, so that prefix path certainly exists.
TF4. Adding a millionth word to a trie slows down every subsequent search.
False — search cost is where is the query length; it visits one node per character and never scans other words, so it is independent of .
TF5. A trie always uses less memory than a Hash Table storing the same words.
False — tries only win memory when words share prefixes; with unrelated words each node overhead (especially a full -sized child array) can make a trie far heavier than a hash table.
TF6. Every leaf node in a trie corresponds to a complete word.
True — a leaf has no children, so a path stopped there; but this is a one-way fact, and you still cannot rely on "leaf ⇒ word" for the reverse (see the next item).
TF7. Only leaf nodes can be word-ends.
False — car ends at an internal node that also has child d for card; that is precisely why the explicit isEnd flag exists rather than inferring words from leaves.
TF8. Two different words can end at the very same node.
False — a node represents one unique prefix (the path spelling it), so at most one word can end there; isEnd is a single boolean, not a counter.
TF9. Inserting the same word twice corrupts the trie or double-counts it.
False — the second insert re-walks existing nodes and re-sets isEnd = True (already true), leaving the structure unchanged; it is idempotent.
TF10. Deleting car from a trie containing card requires removing the r node.
False — you only unset isEnd at the r node; the r node still has child d, so removing it would destroy card too.
TF11. startsWith("") (empty prefix) should return True on a non-empty trie.
True — the empty path never breaks; it just stays at the root, and the root (empty string) is a prefix of every word, so any word makes it True.

Spot the error

SE1. "In search, once the loop finishes without breaking, return True."
The error: finishing the walk only proves the path exists (a prefix); a real word needs return node.isEnd. search("ca") would wrongly say True.
SE2. "My loop is for c in word: if c in node.children: continue."
It never descends — continue skips to the next char while node stays at the root, so you check every character against the root's children only. You must do node = node.children[c].
SE3. "startsWith should return node.isEnd at the end, same as search."
Then startsWith("ca") would be False even though car exists — wrong. startsWith must ignore isEnd and return True whenever the path survives.
SE4. "To delete a word, I remove its end node and everything below it."
The subtree below may hold longer words (card under car); blindly deleting the subtree destroys them. Deletion unsets isEnd, then prunes a node only if it has no children and is not itself a word-end.
SE5. "I skip isEnd and treat any node with no children as a word."
Fails for car when card exists: car's node has a child, so you would never report car as a word. An explicit isEnd boolean is mandatory.
SE6. "Autocomplete: I walk to the prefix, then return every node in the subtree."
You must return only nodes where isEnd is true, not every node. Otherwise you emit partial strings like ca or car+partial that were never inserted words. DFS collects paths, filters on isEnd.
SE7. "I store children as a fixed 26-slot array to save time; it works for any input."
Only if the alphabet is exactly lowercase a–z. For digits, uppercase, Unicode, or ', the array either overflows or wastes space — a map of children (see Radix Tree (Compressed Trie) for the compressed variant) is safer.

Why questions

WY1. Why does a hash set fail at "give me all words starting with pre" while a trie shines?
A hash set scatters keys with no notion of shared prefixes, so it must scan all keys; a trie stores shared prefixes as shared paths, so you walk to pre and explore only that subtree.
WY2. Why is search on a trie but on a balanced Binary Search Tree of strings ?
The BST does comparisons and each string comparison is itself up to ; the trie makes exactly one node hop per character with no comparisons against other words.
WY3. Why does the trie root represent the empty string rather than a character?
Every word is reached by walking edges labeled with characters, so the starting point before any edge has consumed zero characters — the empty prefix "", which every word shares.
WY4. Why does autocomplete use DFS on the subtree rather than re-searching the dictionary?
The subtree under the prefix node already contains exactly the words with that prefix; DFS visits only those, whereas re-scanning the dictionary examines irrelevant words too.
WY5. Why can a trie prune spell-check suggestions so aggressively?
If a candidate prefix has no path in the trie, every extension of it is absent as well, so the entire descendant space is skipped in one check — the same reason Longest Prefix Match and Edit Distance search on a trie stay cheap.
WY6. Why does the space bound depend on total characters rather than word count alone?
With a map of children, each distinct character on each distinct path costs one node; shared prefixes are stored once, so cost equals the number of unique path characters, i.e. total characters minus what sharing saves.
WY7. Why is isEnd a boolean and not just "does this node have children"?
Having children answers "is this a prefix of longer words", which is a different question from "did a word end here"; a node can be both (car), so the two facts are stored separately.

Edge cases

EC1. What does search("") return on a trie where no empty word was inserted?
The walk never moves, ending at the root; it returns root.isEnd, which is False unless you explicitly inserted the empty string, so normally False.
EC2. What does inserting the empty string "" do?
The loop over its characters runs zero times, so you immediately set root.isEnd = True, marking the empty string as a valid word — after which search("") becomes True.
EC3. search("ban") when the root has no b child — how far does it walk?
Zero steps into the body: at character 0 the child is missing, so it returns False immediately without touching any deeper node.
EC4. You insert car, then card, then delete card — what happens to car?
Deletion unsets isEnd at d and, since d is now a childless non-word, prunes it; the r node keeps its own isEnd = True, so search("car") still returns True.
EC5. You insert a and then apple — is a still findable?
Yes — a's node has isEnd = True, and adding apple merely extends children below it (p→p→l→e), never clearing the flag, so search("a") stays True.
EC6. A prefix query equals a full stored word, e.g. startsWith("car") where car was inserted.
True — the path plainly exists; startsWith does not distinguish "prefix that is also a word" from "prefix only", it just confirms the road is there.
EC7. Case sensitivity: you insert Car (capital C) and query search("car").
False — C and c are different edge labels, so the paths diverge at character 0; normalize case on both insert and query if case-insensitive matching is intended.
EC8. Duplicate deletion: you call delete on a word that was never inserted.
The walk either breaks (path missing) or reaches a node with isEnd = False; either way there is nothing to unset, so the trie is unchanged and the operation is a safe no-op.
Recall One-sentence self-test

Which single line separates search from startsWith, and why does that line change everything? ::: search ends return node.isEnd (asks "did a word end here?") while startsWith ends return True (asks "does the road exist?") — same walk, different final question.