Pattern #18

Trie

Recommended

Prefix trees for dictionaries, word search, and shared prefixes.

When to use

Many strings share prefixes, or you need startsWith / autocomplete / board word search over a dictionary.

Recognition cues

Implement trie / add and search words
Word search II
Replace words / longest word in dictionary

Common pitfalls

Forgetting end-of-word mark vs mere prefix
Not sharing nodes (memory blow-up)
Mutating board without restoring in word search

90-second recognition drill

Which pattern fits best?

Implement trie / add and search words
Word search II
Replace words / longest word in dictionary

Tree DFSBinary SearchTrieGraph DFS

Interactive

Mental model

A full worked walkthrough of the invariant. Pause, scrub the dots, or use ← →. Aim to narrate each step yourself.

Step 1 of 8

Empty trie. Insert app, apple, bat.

How to think about it

Each edge is a character; a path from the root is a prefix. Nodes store children map (or array of 26) and an isWord flag. Insert walks/creates edges; search requires isWord; startsWith only needs the path to exist.

Template shapes

Shape	Core move	Notes
Map children	Flexible alphabet	Simple code
Array[26]	Lowercase only	Faster constants
Board DFS + trie	Prune dead prefixes	Word Search II

Complexity baseline

Insert/search O(L) in word length. Space O(total characters) across inserts.

From template to problem

Define node: children + isWord.
insert: walk/create; mark end.
search / startsWith: walk; differ on isWord.
For multi-word grid search: DFS while trie path lives.

Template

Same skeleton in TypeScript, Python, and C#. Adapt the invariant; keep the structure.

Trie · Template

/** Trie template: insert / search / startsWith. */
export class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}
export class Trie {
  root = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isWord = true;
  }
  search(word: string): boolean {
    const node = this.walk(word);
    return Boolean(node?.isWord);
  }
  startsWith(prefix: string): boolean {
    return this.walk(prefix) != null;
  }
  private walk(s: string): TrieNode | null {
    let node: TrieNode | null = this.root;
    for (const ch of s) {
      if (!node!.children.has(ch)) return null;
      node = node!.children.get(ch)!;
    }
    return node;
  }
}

/** Trie template: insert / search / startsWith. */
export class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}
export class Trie {
  root = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isWord = true;
  }
  search(word: string): boolean {
    const node = this.walk(word);
    return Boolean(node?.isWord);
  }
  startsWith(prefix: string): boolean {
    return this.walk(prefix) != null;
  }
  private walk(s: string): TrieNode | null {
    let node: TrieNode | null = this.root;
    for (const ch of s) {
      if (!node!.children.has(ch)) return null;
      node = node!.children.get(ch)!;
    }
    return node;
  }
}

Path

Start path View in problem browser →

#ProblemTypeDifficultyDone

1#208 Implement Trie (Prefix Tree)Guidemedium
2#211 Design Add and Search Words Data StructureGuidemedium
3#212 Word Search IIGuidehard
4#421 Maximum XOR of Two Numbers in an ArrayGuidemedium
5#648 Replace WordsGuidemedium
6#720 Longest Word in DictionaryGuidemedium