Tries for prefix suggestions in a small dictionary
Build a small prefix trie with explicit terminal markers, return limited suggestions in alphabetic order, and include output size in the query cost.

A trie follows one edge per character to find the node for a prefix, then explores the words below that node. Finding the prefix and returning every matching word have different costs. For a developer implementing autocomplete, a short prefix can be cheap to locate while still matching a large fraction of the dictionary.
Use the words car, card, care, cat, and dog. Prefix ca has four matches. Prefix car has three, including car itself. That last result requires a terminal marker on the node for the final r; having children does not mean the node cannot also finish a word.
Separate edges from completed words
Each node stores a mapping from a character to a child and a Boolean marking whether a word ends there. Inserting an already stored word sets the same Boolean again, so this trie represents a set of distinct strings. It does not count word frequency or attach several documents to one word.
class TrieNode:
def __init__(self):
self.children = {}
self.terminal = False
def insert(root, word):
if not isinstance(word, str) or not word or any(c not in 'abcdefghijklmnopqrstuvwxyz' for c in word):
raise ValueError('expected a nonempty lowercase ASCII word')
node = root
for character in word:
if character not in node.children:
node.children[character] = TrieNode()
node = node.children[character]
node.terminal = True
def suggestions(root, prefix, limit=5):
if not isinstance(prefix, str):
raise ValueError('expected a string prefix')
if type(limit) is not int:
raise ValueError('expected an integer suggestion limit')
if limit <= 0:
return []
node = root
for character in prefix:
if character not in node.children:
return []
node = node.children[character]
result, path = [], list(prefix)
def visit(current):
if current.terminal:
result.append(''.join(path))
if len(result) == limit:
return
for character, child in sorted(current.children.items()):
path.append(character)
visit(child)
path.pop()
if len(result) == limit:
return
visit(node)
return result
root = TrieNode()
for word in ['car', 'card', 'care', 'cat', 'dog']:
insert(root, word)
assert suggestions(root, 'car') == ['car', 'card', 'care']
assert suggestions(root, 'ca', 2) == ['car', 'card']
assert suggestions(root, 'cab') == []
The search first follows the prefix without building a separate filtered list of all words. Once it reaches the prefix node, the traversal emits the current path if terminal and explores children in character order. Emitting before descending makes a word precede its extensions in ordinary lexicographic order.
The mutable path list avoids constructing a fresh full prefix string at every internal node. A string is assembled only when a complete suggestion is returned. The append and pop operations must remain paired so that a later sibling does not inherit characters from the previous branch.
The terminal marker at r distinguishes a stored word from a prefix that merely leads to longer words. Removing car should clear that marker while preserving the branches for card and care. Deleting the whole r subtree would remove valid longer words too.
Include the returned characters in the cost
Let P be prefix length, V the number of nodes visited below its node before the limit is reached, and B the total number of characters in the returned strings. With a bounded alphabet and constant expected dictionary access, this implementation uses O(P + V + B) work. Sorting each node’s children has bounded cost here because the alphabet has only 26 characters.
If the alphabet is unbounded, include the cost of sorting each visited node’s outgoing keys. If suggestions are preordered in another structure, that cost moves to insertion or maintenance. No representation eliminates the work of producing B characters for the caller.
The query can stop after its requested number of results, but it may still traverse long paths before finding them. A node can be a long chain with one terminal word at the end. A bound such as O(P + number of matches) hides that path length and the size of the returned strings.
Princeton’s trie discussion and TrieST implementation separate key lookup from prefix collection. The array-based character representation shown there has different per-node memory costs from the sparse dictionaries used in this example.
Choose a ranking rule before adding caches
Alphabetic order is simple and deterministic, but product autocomplete often ranks by frequency, recency, or a user’s context. A depth-first alphabetic traversal cannot promise the highest-ranked matches under those rules. You may need a priority structure, stored top suggestions at each prefix, or a separate search index.
Caching the best suggestions at every node makes reads cheaper but makes updates more expensive. A frequency change for one word can affect every node along its path. Removing a word can require finding a replacement candidate outside the current cached set. Those are new maintenance requirements, not a small alteration to the terminal flag.
Memory also deserves a workload check. The trie shares common prefixes but stores nodes and child mappings for distinct prefixes. A sorted array of words with two binary searches for a prefix range can be smaller and may be sufficient when the dictionary changes infrequently. A compressed trie reduces chains of single-child nodes but changes edge matching and update logic.
Keep normalization consistent
This example accepts only nonempty lowercase ASCII words. It does not silently lowercase or strip accents. A multilingual application needs a deliberate normalization and collation policy applied consistently during insertion and lookup; Unicode case folding can change string length, and code-point order is not every language’s alphabetical order. For example, Python’s str.casefold maps the German ß to ss. Applying that transformation would change the identity policy of the stored keys; this example does not apply it implicitly.
An empty query prefix starts at the root and returns the first limited suggestions from the whole dictionary. A prefix containing an unsupported character returns no match in this implementation. If the API should reject malformed queries instead, add that validation as an explicit contract.
Test a word that is also another word’s prefix, repeated insertion, a missing edge, and limits of zero, one, and more than the available matches. For deletion, test clearing a terminal with surviving descendants. Those cases verify what users actually see rather than only confirming that a few nodes were allocated.
Delete a word without deleting its extensions
Deletion needs to distinguish a stored word, a reachable prefix and an unused branch. First follow the entire word while recording the parent and character of each edge. If an edge is missing or the final node is not terminal, return without changing anything. Otherwise clear the terminal marker and remove empty, nonterminal nodes while walking back toward the root.
def remove(root, word):
if not isinstance(word, str) or not word or any(c not in 'abcdefghijklmnopqrstuvwxyz' for c in word):
raise ValueError('expected a nonempty lowercase ASCII word')
node, trail = root, []
for character in word:
if character not in node.children:
return False
trail.append((node, character))
node = node.children[character]
if not node.terminal:
return False
node.terminal = False
for parent, character in reversed(trail):
child = parent.children[character]
if child.terminal or child.children:
break
del parent.children[character]
return True
assert remove(root, 'car')
assert suggestions(root, 'ca') == ['card', 'care', 'cat']
assert not remove(root, 'car')
assert remove(root, 'card')
assert suggestions(root, 'ca') == ['care', 'cat']
assert remove(root, 'care')
assert suggestions(root, 'ca') == ['cat']
assert 'r' not in root.children['c'].children['a'].children
assert suggestions(root, 'd') == ['dog']
After removing car, its r node still has d and e children, so pruning stops immediately. Removing card later discards the d leaf but stops at r because care remains. Removing care finally discards both e and r; it stops at a because the t branch still stores cat. The separate dog branch never participates in this traversal.
The stopping condition protects two kinds of useful nodes. A node with children still connects longer words, while a terminal node may represent a shorter stored word even after its last child disappears. Stopping at either condition preserves the dictionary. The root object itself is never deleted, which gives callers a stable entry point even after removing the last word.
For a word of length L, this deletion uses O(L) expected work and O(L) extra trail entries under the same dictionary-access assumption as insertion. It needs no recursive calls. Suggestion collection above remains recursive, however: a very long single word can still exceed Python’s recursion limit when enumerated. Supporting unbounded word length requires an explicit traversal stack or a documented length limit; iterative deletion alone does not solve that separate issue.
The integer limit check also matters to the visible contract. A fractional limit would not equal any integer result count, allowing the earlier stopping test to miss the intended cap. This API accepts built-in integer limits, returns no suggestions for nonpositive values, and rejects booleans and fractional limits. Invalid prefix types are rejected; an unsupported character inside a string simply finds no matching edge.
As an exercise, maintain a reference set of words through random insertions and deletions. For every query, filter by startswith, sort, and apply the same nonpositive-limit rule before comparing results. Check absent-word removal leaves every node untouched, and remove the last word to confirm the root remains usable for a later insertion. Those tests verify both observable suggestions and the pruning contract.