# Algo Tries

> Implement a trie (prefix tree) in Python for O(m) word insert/search, O(p) prefix checks, and O(p+k) prefix enumeration; build autocomplete, spell-checkers, and k-mer/gene-name lookup over DNA or dictionary strings. Use when asked for prefix tree, trie data structure, autocomplete implementation, dictionary/word membership, longest-prefix match, gene-name or k-mer prefix search, or radix/compressed trie.

- Skill: `pavel-kravchenko/algo-tries` (Agent Skill)
- Install (CLI): `npx skillmds@latest add pavel-kravchenko/algo-tries`
- Raw SKILL.md: https://api.skillmd.com/api/skills/pavel-kravchenko/algo-tries/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Docs & Writing
- Author: pavel-kravchenko (https://skillmd.com/u/pavel-kravchenko)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/pavel-kravchenko/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

| Operation | Time | Notes |
|-----------|------|-------|
| Insert | O(m) | m = word length |
| Search (exact) | O(m) | |
| Prefix check | O(p) | p = prefix length |
| Prefix collect | O(p + k) | k = results |
| Delete | O(m) | |

**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.

```python
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.

```python
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.

```python
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.