Algo Tries

Trie (Prefix Tree)

When to Use

• Implementing autocomplete or type-ahead suggestions over a fixed vocabulary.
• Exact word/dictionary membership testing plus prefix existence checks (starts_with).
• Enumerating all strings sharing a prefix (spell-checker suggestions, IP longest-prefix routing).
• Bioinformatics: fast prefix lookup over gene/variant name lists, or counting unique k-mers in a DNA sequence.
• You need better prefix performance than a hash-set scan (O(p+k) vs O(n·m)) and can afford one node per character.

Version Compatibility

Pure Python, stdlib only — no external dependencies. Works on Python ≥ 3.9 (uses dict and list[str] type hints; use List[str] from typing on 3.8).

Prerequisites

• Comfortable with recursion and dict-of-dict tree traversal.
• No packages to install. Related structure: hash tables (see algo-hash-tables-bloom) as the O(1)-average alternative for exact-match-only lookups.

Complexity

vs Hash Table: trie gives O(p + k) prefix search vs O(n × m) full scan; a hash set/dict is usually lower memory and just as fast for exact-match-only lookups with no prefix queries.

Goal: store a set of strings so that exact lookup, prefix existence, and "all words with this prefix" are all fast. Approach: one TrieNode per character; the path from root to a node is the prefix built so far; is_end marks nodes that are complete words.

from __future__ import annotations


class TrieNode:
    """A single node in the trie: one edge per next character."""

    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False  # True if a word ends exactly at this node


class Trie:
    """Prefix tree supporting insert, exact search, prefix search, and delete."""

    def __init__(self):
        self.root = TrieNode()

    def _find_node(self, prefix: str) -> TrieNode | None:
        """Walk from root following `prefix`; return the ending node or None."""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def insert(self, word: str) -> None:
        """Add `word` to the trie. O(m)."""
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word: str) -> bool:
        """True only if `word` was inserted exactly (not just a prefix)."""
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        """True if any inserted word begins with `prefix`."""
        return self._find_node(prefix) is not None

    def get_all_with_prefix(self, prefix: str) -> list[str]:
        """Return every inserted word starting with `prefix`, sorted."""
        results: list[str] = []
        node = self._find_node(prefix)
        if node is None:
            return results
        self._collect(node, prefix, results)
        return results

    def _collect(self, node: TrieNode, word: str, results: list[str]) -> None:
        if node.is_end:
            results.append(word)
        for ch, child in sorted(node.children.items()):
            self._collect(child, word + ch, results)

    def delete(self, word: str) -> bool:
        """Remove `word`. Only prunes nodes that become childless non-endpoints."""

        def _del(node: TrieNode, depth: int) -> bool:
            if depth == len(word):
                if not node.is_end:
                    return False
                node.is_end = False
                return not node.children  # safe to prune if leaf
            ch = word[depth]
            if ch not in node.children:
                return False
            if _del(node.children[ch], depth + 1):
                del node.children[ch]
                return not node.children and not node.is_end
            return False

        return _del(self.root, 0)

    def get_all_words(self) -> list[str]:
        """Return every word stored in the trie, alphabetically sorted."""
        return self.get_all_with_prefix("")

Application: Autocomplete and Spell-Check

Goal: turn raw prefix hits into ranked suggestions. Approach: cap get_all_with_prefix results; for spell-check, back off to shorter prefixes when the exact word is missing.

def autocomplete(trie: Trie, prefix: str, max_results: int = 5) -> list[str]:
    """Return up to `max_results` completions for `prefix`."""
    return trie.get_all_with_prefix(prefix)[:max_results]


def spell_suggest(trie: Trie, word: str, max_suggestions: int = 5) -> list[str]:
    """
    Suggest corrections for `word` by backing off to shorter prefixes
    until a match is found, then ranking by length similarity.
    """
    word = word.lower()
    for i in range(len(word), 0, -1):
        candidates = trie.get_all_with_prefix(word[:i])
        if candidates:
            candidates.sort(key=lambda w: abs(len(w) - len(word)))
            return candidates[:max_suggestions]
    return []

Application: Gene-Name Prefix Lookup and k-mer Counting

Goal: apply a trie to bioinformatics prefix problems — gene symbol autocomplete and unique k-mer counting in a DNA sequence. Approach: insert gene symbols (or every k-length substring) and reuse the same trie API; is_end nodes reached during a DFS are the unique items.

def gene_autocomplete(trie: Trie, prefix: str) -> list[str]:
    """Return gene symbols in `trie` starting with `prefix`, alphabetically sorted."""
    return trie.get_all_with_prefix(prefix)


def count_unique_kmers_trie(sequence: str, k: int) -> tuple[int, list[str]]:
    """
    Count unique k-mers in a DNA sequence using a trie.

    Inserts every length-k substring; each distinct root-to-is_end path
    is one unique k-mer.
    """
    trie = Trie()
    for i in range(len(sequence) - k + 1):
        trie.insert(sequence[i : i + k])
    kmers = trie.get_all_words()
    return len(kmers), kmers


GENE_NAMES = ["BRCA1", "BRCA2", "BRAF", "BRD4", "TP53", "TP63", "MYC", "MYCN"]
gene_trie = Trie()
for gene in GENE_NAMES:
    gene_trie.insert(gene)
assert gene_autocomplete(gene_trie, "BR") == ["BRAF", "BRCA1", "BRCA2", "BRD4"]

dna = "ATCGATCGATCGAATTCCGATCGATCGATCG"
trie_count, _ = count_unique_kmers_trie(dna, k=3)
assert trie_count == len({dna[i : i + 3] for i in range(len(dna) - 2)})

Pitfalls

• search vs starts_with: "ca" returns True for starts_with even if only "cat" was inserted; search checks is_end and returns False for a bare prefix.
• Deleting a prefix of another word: never remove nodes that have children; only clear is_end. delete above prunes only when a node becomes both childless and a non-endpoint.
• Memory vs hash map: a dict-per-node trie uses more memory than a flat hash map for large, sparse alphabets. Use a fixed-size array of |Σ| children only when the alphabet is small and dense (e.g., DNA: 4 symbols).
• Case sensitivity: tries are case-sensitive by default; .lower()/.upper() inputs consistently before insert/search (gene symbols like BRCA1 are usually kept uppercase, not lowercased).
• k-mer trie vs set: a trie gives the same unique-count as len(set(kmers)) but at O(n·k) memory for shared prefixes — for pure counting on large genomes, a hash set or a suffix array/tree (see algo-suffix-arrays) scales better.

See Also

• algo-aho-corasick — multi-pattern matching by adding failure links to a trie.
• algo-hash-tables-bloom — O(1)-average exact lookup when prefix queries aren't needed.
• algo-suffix-arrays / algo-suffix-trees — substring (not just prefix) search over a single long sequence, e.g. whole-genome k-mer/repeat analysis.