# Tries — Part 1: The Pattern

A trie (prefix tree) stores strings character by character: each edge is a character, each path from the root spells a prefix, and a flag marks where complete words end. Inserting or looking up a word costs **O(L)** for its length L, **independent of how many words are stored**, and every word sharing a prefix shares the same path. That makes tries the natural answer to **prefix queries**: autocomplete, "starts with", wildcard search, and searching many words at once in a grid.

![A trie holding app, apple, apt and bat; shared prefixes share nodes](diagrams/01-trie.svg)

## 1. When to Use a Trie

| Need | Trie | Hash set |
|---|---|---|
| exact membership | O(L) | O(L) to hash, simpler |
| "any word starts with p?" / all words with prefix p | **O(L + matches)** | must scan every word |
| wildcard (`b.d`) | DFS over children | scan everything |
| search many dictionary words in a grid | one DFS, prune dead prefixes | one search per word |
| longest common prefix / shortest unique prefix | walk while one child | awkward |

## 2. Template

```typescript
class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TrieNode());
      node = node.children.get(c)!;
    }
    node.isEnd = true;
  }
  private walk(s: string): TrieNode | null {
    let node: TrieNode | undefined = this.root;
    for (const c of s) {
      node = node.children.get(c);
      if (!node) return null;
    }
    return node;
  }
  search(word: string): boolean { const n = this.walk(word); return n !== null && n.isEnd; }
  startsWith(prefix: string): boolean { return this.walk(prefix) !== null; }
}

function trieDemo(words: string[], queries: string[]): boolean[][] {
  const t = new Trie();
  for (const w of words) t.insert(w);
  return queries.map((q) => [t.search(q), t.startsWith(q)]);
}
```

```python
class TrieNode:
    def __init__(self):
        self.children = {}          # char -> TrieNode
        self.is_end = False         # a word ends here

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

    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def _walk(self, s):
        node = self.root
        for c in s:
            node = node.children.get(c)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

def trie_demo(words, queries):
    t = Trie()
    for w in words:
        t.insert(w)
    return [[t.search(q), t.starts_with(q)] for q in queries]
```

Children can be a **hash map** (any alphabet, memory-light for sparse nodes) or a **fixed array of 26** (faster, lowercase only). Mention the trade-off.

## 3. Common Extensions

- **Count prefixes:** store `count` on each node (words passing through) for "how many words start with p".
- **Autocomplete:** walk to the prefix node, then DFS to collect words (store up to 3 best suggestions per node for speed, as in Search Suggestions System).
- **Wildcards:** on `.`, try every child recursively.
- **Word Search II:** build a trie of the dictionary, DFS the grid along trie edges, and prune any trie branch once its words are found.

## Under the Hood: Memory and Radix Trees

A naive trie can use a lot of memory: one node per character with a children map. Production systems compress chains of single-child nodes into one edge labelled with a whole substring: a **radix tree (Patricia trie)**. Linux's routing tables use them for IP prefix lookup, Redis uses a radix tree for Streams and cluster slot mapping, and HTTP routers (Go's httprouter, Fastify's find-my-way) use them to match URL paths. Search engines' autocomplete layers use tries or FSTs (finite-state transducers) that also share suffixes.

## Common Pitfalls

1. **Forgetting the end-of-word flag:** after inserting "apple", "app" must not count as a word unless inserted.
2. **Confusing `search` and `startsWith`:** both walk the path; only `search` checks the flag.
3. **Rebuilding the trie per query** instead of once.
4. **Not pruning in Word Search II:** without removing found words, the search revisits dead branches.
5. **Memory blow-up** with 26-slot arrays on sparse data.

## Quick Reference

```text
insert: node = root; for c: node = node.children.setdefault(c, Node()); node.end = True
search: walk; return node and node.end · startsWith: walk; return node is not None
O(L) per operation · space O(total characters)
```