Implementing a trie for prefix matching and suggestions

A prefix tree, usually called a trie, makes autocomplete a character-by-character traversal instead of a full scan of a word list. Given the prefix melb, it follows matching child nodes and can quickly identify stored completions. The same structure supports dictionary lookups, spell checking, domain suggestions and route search, while keeping the matching logic clear enough to implement from scratch.

This article builds a Python trie with terminal markers, occurrence counts and ranked completions. It also covers Unicode normalisation, traversal limits, testing and realistic use in Australian products. The aim is a dependable implementation rather than a toy that only works with clean, lower-case English words.

How a prefix tree organises words

Each node represents a path from the root and stores outgoing character edges. A terminal marker distinguishes a complete word from a prefix such as car in carpenter. Because car, card and cart share their first three edges, a trie stores that common portion once. Queries can therefore stop as soon as an edge is missing, rather than checking every dictionary entry.

This sharing creates a useful separation between lookup and ranking. Prefix matching answers “which stored words remain possible?” while scoring decides “which of those words should appear first?” A frequency, editorial weight or contextual score can be attached to each terminal node. A trie without scores can still produce suggestions, but it usually needs a secondary alphabetical or length-based ordering.

Hash tables are excellent for exact membership checks, yet they do not naturally expose all entries under a shared prefix. Tries and B-trees solve different problems: a guide to implementing a B-tree is useful for ordered range scans and disk-friendly indexing, while a trie is strongest for many prefix queries over related strings.

Building the trie in Python

For Python 3.10 and later, a node can be represented by a dictionary of children, a Boolean word flag, a frequency and an optional display spelling. Python dictionaries provide expected constant-time child lookup, while an explicit branch keeps insertion clear and avoids creating unused nodes.

from __future__ import annotations

from dataclasses import dataclass, field


@dataclass(slots=True)
class TrieNode:
    children: dict[str, TrieNode] = field(default_factory=dict)
    is_word: bool = False
    frequency: int = 0
    display: str | None = None


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str, frequency: int = 1) -> None:
        node = self.root

        for char in word.casefold():
            child = node.children.get(char)
            if child is None:
                child = TrieNode()
                node.children[char] = child
            node = child

        node.is_word = True
        node.frequency += frequency
        node.display = word

    def prefix_node(self, prefix: str) -> TrieNode | None:
        node = self.root

        for char in prefix.casefold():
            node = node.children.get(char)
            if node is None:
                return None

        return node

The node stores both a canonical key and the spelling shown to the user. casefold() handles case-insensitive matching more reliably than lower() for Unicode text, and the original display value preserves capitalisation. If an application deliberately ignores accents, Unicode normalisation can produce another key; that policy should be explicit rather than hidden inside insertion.

prefix_node is the critical read path. It returns None immediately when the next character has no child, so a missing prefix costs only the length already examined. The root also represents the empty prefix, which makes it possible to request the highest-ranked words from the whole corpus.

Adding ranked word suggestions

Collect candidates from the matched node’s subtree, then sort them by score. The following method returns the whole matching set before applying the limit, ensuring that a low-frequency word does not win merely because a depth-first traversal happened to visit it first.

    def suggest(self, prefix: str, limit: int = 5) -> list[str]:
        node = self.prefix_node(prefix)
        if node is None:
            return []

        candidates: list[tuple[str, int]] = []
        stack = [node]

        while stack:
            current = stack.pop()

            if current.is_word and current.display is not None:
                candidates.append((current.display, current.frequency))

            stack.extend(current.children.values())

        candidates.sort(key=lambda item: (-item[1], item[0]))
        return [word for word, _ in candidates[:limit]]

The frequency score is deliberately simple. It works well when the corpus reflects real usage, such as a search log with recent events. It does not capture location, recency or intent: in a railway interface, Sydney may outrank Siding for some users, while a sports interface may need the opposite. A production ranker can combine trie candidates with those contextual signals.

Prefix matching should also be distinguished from fuzzy matching. A trie answers queries that share an exact initial sequence; it will not find Melnourne when the user omitted b. Correcting that spelling requires edit-distance candidates, phonetic indexes or a separate typo model. Combining the two stages is common: generate exact-prefix candidates first, then reorder them using spelling and context scores.

Design choices and evaluation checks

A production design should make the following decisions explicit:

• Sparse child maps: Store only existing edges, so a large vocabulary does not allocate an alphabet-sized array for every node.
• Terminal metadata: Keep the word flag, score and display value at the node where a complete word ends.
• Canonical keys: Normalise case consistently, but retain the original spelling for results and locale-specific labels.
• Bounded work: Cap result counts, input length and any recursive or breadth-first traversal to resist accidental denial of service.

Evaluation should combine correctness, speed and relevance:

• Prefix correctness: Compare results with a straightforward reference filter for empty, partial, complete and unknown prefixes.
• Latency: Measure time to first and later suggestions, including cache hits, under realistic concurrent traffic.
• Ranking relevance: Use expected completions and click-through data to check that frequent or contextually suitable words appear first.
• Memory footprint: Count nodes as well as characters, since one dictionary and several fields are created for every prefix.

These checks expose trade-offs that a passing unit test can hide. A complete candidate scan gives high-quality ranking but costs more for prefixes with thousands of descendants. A bounded traversal is faster, yet pruning by score requires a priority queue or a separate candidate index. Larger corpora also call for compact arrays, integer child identifiers or compressed tries rather than one Python dictionary per node.

Australian use cases and data duties

Place-name search is a natural Australian test. A transport app used around Sydney, Melbourne, Brisbane and Canberra must match suburbs, stations and abbreviations such as QLD, NSW and VIC. People commonly search for an address on a phone while travelling, so each keypress should update results quickly. Keeping canonical place names separate from normalised keys prevents Parramatta from becoming unreadable merely because the index stores parramatta.

The same principle suits retail search in the Australian market, where shoppers use Woolworths or Coles apps to find groceries by partial name. Favourites, organisation names and brand spellings differ from a standard dictionary, so corpus-derived frequencies usually produce better results than a fixed word list. Australian English spellings should remain visible in results even when matching ignores capitalisation.

Racing adds specialised vocabulary made up of meeting, race and runner names. Readers interested in the local market can consult horse racing betting Australia for relevant context, then examine how a domain corpus would affect prefix rankings. Stable identifiers should drive internal joins, while the visible suggestion can preserve the official race name.

Privacy and consumer law matter when suggestions reveal a person’s interests or locations. Personal information handled by organisations covered by the Privacy Act 1988 remains subject to Australian privacy obligations, including limits on collection and use. A commercial autocomplete service must also meet the Australian Consumer Law’s standards for services due care and technical support. Teams can reduce exposure by aggregating frequencies, shortening retention and avoiding raw keystrokes in logs, while obtaining advice for their particular obligations.

Testing complexity and deployment

Correctness tests should cover exact prefix sets, mixed case, an empty prefix, a missing prefix, duplicate canonical spellings and equal-score ranking ties. Property-based tests can generate random strings, insert them into a trie and compare its output with a reference list comprehension. Include real Australian names such as Kaurna, Warrigal and Ngarrindjeri, plus Māori text containing macrons, to expose encoding assumptions.

For a word of length (m), insertion takes expected (O(m)) time because each child lookup is expected constant time. Finding a prefix of length (p) takes expected (O(p)). The supplied suggestion method visits (v) nodes in the matching subtree and sorts (k) terminal candidates, giving (O(v + k \log k)) time. Space is proportional to the total number of distinct prefixes, plus per-node object overhead.

A web deployment can send a request after two or three characters, debounce rapid keystrokes and enforce a small result limit on both client and server. An immutable in-memory trie is suitable when the vocabulary changes rarely; a more dynamic product can keep several indexes for separate corpora, languages or ranking policies. Common prefixes benefit from caching, but private data must never leak through a shared cache key.

Implementation notes and edge cases can be reviewed through contact the editors. A tested trie is a focused tool for prefix retrieval: it trades memory and update effort for fast candidate generation, leaving relevance scoring and broader search indexing as separate concerns.