Trie (Prefix Tree) — The Complete Guide

         (root)
        /      \
       a        b
      /          \
     p            a
    / \            \
   p   e*          t*
   |               |
   l              l*
   |
   e*

* = end of word marker

Paths from root:
  a → p → p → l → e  = "apple" ✓ (e is marked)
  a → p → p          = "app"   ✓ (second p is marked)
  a → p → e          = "ape"   ✓ (e is marked)
  b → a → t          = "bat"   ✓ (t is marked)
  b → a → l → l      = "ball"  ✓ (second l is marked)

Key insight: "apple" and "app" share the path a→p→p.
The shared prefix is stored ONCE, not twice.

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: boolean = false;
  // Optional: store the word itself, count, or other metadata
  word?: string;
}

class Trie {
  root = new TrieNode();

  /** Insert a word into the Trie — O(L) */
  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.isEnd = true;
    node.word = word; // useful for Word Search II
  }

  /** Check if a word exists exactly — O(L) */
  search(word: string): boolean {
    const node = this._walkTo(word);
    return node !== null && node.isEnd;
  }

  /** Check if any word starts with this prefix — O(P) */
  startsWith(prefix: string): boolean {
    return this._walkTo(prefix) !== null;
  }

  /** Walk to the node at the end of the given string */
  private _walkTo(s: string): TrieNode | null {
    let node = this.root;
    for (const ch of s) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch)!;
    }
    return node;
  }
}

// Usage:
// const trie = new Trie();
// trie.insert("apple");
// trie.search("apple");    → true
// trie.search("app");      → false (not marked as end)
// trie.startsWith("app");  → true  (prefix exists)

function autocomplete(trie: Trie, prefix: string): string[] {
  const results: string[] = [];
  const prefixNode = trie._walkTo(prefix);
  if (!prefixNode) return results;

  // DFS from prefix node to collect all words
  function dfs(node: TrieNode, path: string): void {
    if (node.isEnd) results.push(path);
    for (const [ch, child] of node.children) {
      dfs(child, path + ch);
    }
  }

  dfs(prefixNode, prefix);
  return results;
}
// Time: O(P + K × avgLen) where P = prefix length, K = matching words
// This is the foundation for autocomplete, search suggestions, etc.

function findWords(board: string[][], words: string[]): string[] {
  const trie = new Trie();
  for (const word of words) trie.insert(word);

  const result: string[] = [];
  const rows = board.length, cols = board[0].length;

  function backtrack(r: number, c: number, node: TrieNode): void {
    // Prune: out of bounds, visited, or no Trie path
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const ch = board[r][c];
    if (ch === '#' || !node.children.has(ch)) return;

    const nextNode = node.children.get(ch)!;

    // Found a word!
    if (nextNode.isEnd) {
      result.push(nextNode.word!);
      nextNode.isEnd = false; // avoid duplicates
    }

    // Choose: mark visited
    board[r][c] = '#';

    // Explore: 4 directions
    backtrack(r + 1, c, nextNode);
    backtrack(r - 1, c, nextNode);
    backtrack(r, c + 1, nextNode);
    backtrack(r, c - 1, nextNode);

    // Unchoose: restore
    board[r][c] = ch;

    // Optimization: prune empty Trie branches
    if (nextNode.children.size === 0) {
      node.children.delete(ch);
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      backtrack(r, c, trie.root);
    }
  }

  return result;
}
// Key: the Trie guides the backtracking — you only explore paths
// that could form a word. Without the Trie, you'd run a separate
// backtracking search for each word (much slower).

class WordDictionary {
  root = new TrieNode();

  addWord(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.isEnd = true;
  }

  search(word: string): boolean {
    return this._dfs(word, 0, this.root);
  }

  private _dfs(word: string, idx: number, node: TrieNode): boolean {
    if (idx === word.length) return node.isEnd;

    const ch = word[idx];
    if (ch === '.') {
      // Wildcard: try ALL children
      for (const child of node.children.values()) {
        if (this._dfs(word, idx + 1, child)) return true;
      }
      return false;
    } else {
      // Exact match: follow the specific child
      if (!node.children.has(ch)) return false;
      return this._dfs(word, idx + 1, node.children.get(ch)!);
    }
  }
}
// Time: O(L) for exact search, O(26^dots × L) worst case for wildcards
// Key: '.' branches into all 26 children — exponential in # of dots
// but practical because most paths die quickly

function findMaximumXOR(nums: number[]): number {
  // Binary Trie node: children[0] and children[1]
  const root: [any, any] = [null, null];

  function insert(num: number): void {
    let node = root;
    for (let i = 31; i >= 0; i--) {
      const bit = (num >> i) & 1;
      if (!node[bit]) node[bit] = [null, null];
      node = node[bit];
    }
  }

  function maxXorWith(num: number): number {
    let node = root;
    let xor = 0;
    for (let i = 31; i >= 0; i--) {
      const bit = (num >> i) & 1;
      const opposite = 1 - bit;
      // Greedily pick the opposite bit if it exists
      if (node[opposite]) {
        xor |= (1 << i);
        node = node[opposite];
      } else {
        node = node[bit];
      }
    }
    return xor;
  }

  let maxResult = 0;
  for (const num of nums) {
    insert(num);
    maxResult = Math.max(maxResult, maxXorWith(num));
  }
  return maxResult;
}
// Time: O(n × 32) = O(n)  Space: O(n × 32)
// Key insight: XOR is maximized when bits differ. At each level,
// greedily choose the opposite bit. The Trie lets you do this
// in O(32) per number instead of O(n) brute-force comparisons.

function replaceWords(dictionary: string[], sentence: string): string {
  const trie = new Trie();
  for (const root of dictionary) trie.insert(root);

  return sentence.split(' ').map(word => {
    let node = trie.root;
    for (let i = 0; i < word.length; i++) {
      const ch = word[i];
      if (!node.children.has(ch)) break; // no matching root
      node = node.children.get(ch)!;
      if (node.isEnd) return word.slice(0, i + 1); // shortest root found!
    }
    return word; // no root found, keep original
  }).join(' ');
}
// Time: O(D × L + S × W) where D = dict size, S = sentence words
// Key: stop at the FIRST isEnd — that's the shortest root.
// The Trie naturally gives you the shortest prefix match.

Start: root = {}

Insert "apple":
  root → a (new) → p (new) → p (new) → l (new) → e (new, isEnd=true)
  
  Tree:  (root)
           |
           a
           |
           p
           |
           p
           |
           l
           |
           e*

Insert "app":
  root → a (exists) → p (exists) → p (exists, mark isEnd=true)
  
  Tree:  (root)          No new nodes created!
           |              "app" shares the path with "apple"
           a
           |
           p
           |
           p*  ← now marked as end
           |
           l
           |
           e*

Insert "ape":
  root → a (exists) → p (exists) → e (new, isEnd=true)
  
  Tree:  (root)
           |
           a
           |
           p
          / \
         p*  e*  ← "ape" branches off at the second 'p' level
         |
         l
         |
         e*

Insert "bat":
  root → b (new) → a (new) → t (new, isEnd=true)
  
  Tree:    (root)
          /      \
         a        b
         |        |
         p        a
        / \       |
       p*  e*     t*
       |
       l
       |
       e*

Final Trie stores 4 words using 9 nodes (not 4×3.5 = 14 characters).
Shared prefix "ap" saves 2 nodes between "apple"/"app" and "ape".

Trie contains: "apple", "app", "ape", "bat"
Search pattern: "a.e" (. matches any single character)

Step 1: idx=0, char='a'
  Exact match → follow 'a' child
  Current node: 'a'

Step 2: idx=1, char='.'
  Wildcard! Branch into ALL children of 'a':
  
  Branch A: follow 'p' child
    Step 3a: idx=2, char='e'
      Check 'p' node's children for 'e':
      'p' has children: {p, e}
      
      Branch A1: follow 'p' → idx=3, but word is only 3 chars
        idx === word.length → check isEnd on 'p' node
        'p' node isEnd = true (word "app")
        But wait — we're at idx=3 and word length is 3, so we check
        the node we landed on. We followed a→p→p, isEnd=true.
        But the pattern is "a.e" — we need 'e' at position 2, not 'p'.
        Actually let me re-trace...
      
  Let me redo this more carefully:
  
  Node at 'a' has children: {p}
  
  Branch: follow 'p' (the only child)
    Step 3: idx=2, char='e'
      Node at 'p' (second level) has children: {p, e}
      Check for 'e': YES, 'e' exists!
      Follow 'e' → idx=3
      idx === word.length (3) → check isEnd
      'e' node isEnd = true → MATCH FOUND! ✓
      
      This matched the word "ape" (a → p → e)

Result: "a.e" matches "ape" ✓

Key observations:
- '.' at position 1 tried all children of 'a' (just 'p' here)
- With a larger alphabet, '.' would branch into up to 26 paths
- Most branches die quickly — practical performance is much better
  than the theoretical O(26^dots) worst case

Does the problem involve PREFIX-based operations on strings?
├── NO  → Probably not a Trie problem.
│         Exact lookup only? → HashSet
│         Substring matching? → KMP, Rabin-Karp, or Suffix structures
│         Sorting strings? → Radix sort or standard sort
└── YES → What kind of prefix operation?
          ├── Insert + search + startsWith?
          │   └── Basic Trie (LC 208)
          ├── Find all words with a given prefix?
          │   └── Trie + DFS collection (autocomplete)
          ├── Search with wildcards (.)?
          │   └── Trie + recursive DFS branching (LC 211)
          ├── Find words from a dictionary in a grid?
          │   └── Trie + Backtracking (LC 212)
          ├── Replace words with shortest dictionary root?
          │   └── Trie walk, stop at first isEnd (LC 648)
          └── Maximum XOR of two numbers?
              └── Binary Trie (LC 421)

Node structure needed?
├── Just isEnd → basic problems
├── isEnd + word string → Word Search II (easy retrieval)
├── isEnd + count → counting prefixes, Map Sum Pairs
└── children[0] and children[1] → binary Trie for XOR