Tries

Words: cat, car, card, care, bat, ball
 
         root
        /    \
       c      b
       |      |
       a      a
      / \    / \
     t   r  t   l
         |      |
         d      l
         ↑      ↑
        "card" "ball"

class TrieNode {
  constructor() {
    this.children = {};    // char → TrieNode
    this.isEnd = false;    // true if a word ends here
    this.count = 0;        // optional: how many words pass through this node
  }
}
 
class Trie {
  constructor() {
    this.root = new TrieNode();
  }
 
  // Insert a word — O(L)
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
      node.count++; // optional: track words passing through
    }
    node.isEnd = true;
  }
 
  // Exact search — O(L)
  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return node.isEnd; // must be a complete word, not just a prefix
  }
 
  // Prefix check — O(L)
  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return true; // prefix exists (may or may not be a complete word)
  }
 
  // Delete a word — O(L)
  delete(word) {
    function _delete(node, word, depth) {
      if (!node) return false;
      if (depth === word.length) {
        if (!node.isEnd) return false;
        node.isEnd = false;
        return Object.keys(node.children).length === 0; // safe to delete?
      }
      const ch = word[depth];
      if (!node.children[ch]) return false;
      const shouldDelete = _delete(node.children[ch], word, depth + 1);
      if (shouldDelete) {
        delete node.children[ch];
        return !node.isEnd && Object.keys(node.children).length === 0;
      }
      return false;
    }
    _delete(this.root, word, 0);
  }
}

class AutocompleteTrie extends Trie {
  // Find all words with given prefix
  autocomplete(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return []; // prefix doesn't exist
      node = node.children[ch];
    }
    // DFS from this node to collect all words below
    const results = [];
    this._dfs(node, prefix, results);
    return results;
  }
 
  _dfs(node, current, results) {
    if (node.isEnd) results.push(current);
    for (const [ch, child] of Object.entries(node.children)) {
      this._dfs(child, current + ch, results);
    }
  }
}
 
const trie = new AutocompleteTrie();
['react', 'redux', 'remix', 'reason', 'recoil', 'resolve'].forEach(w => trie.insert(w));
 
trie.autocomplete('re');   // → ['react', 'redux', 'remix', 'reason', 'recoil', 'resolve']
trie.autocomplete('red');  // → ['redux']
trie.autocomplete('rem');  // → ['remix']

function replaceWords(dictionary, sentence) {
  const trie = new Trie();
  for (const root of dictionary) trie.insert(root);
 
  return sentence.split(' ').map(word => {
    // Walk the trie — stop at first complete word (shortest root)
    let node = trie.root;
    let prefix = '';
    for (const ch of word) {
      if (!node.children[ch]) break;
      prefix += ch;
      node = node.children[ch];
      if (node.isEnd) return prefix; // found shortest root
    }
    return word; // no root found, keep original
  }).join(' ');
}
 
// dictionary=["cat","bat","rat"], sentence="the cattle was rattled by the battery"
// → "the cat was rat by the bat"

function findWords(board, words) {
  const trie = new Trie();
  words.forEach(w => trie.insert(w));
 
  const result = new Set();
  const m = board.length, n = board[0].length;
 
  function dfs(node, row, col, path) {
    if (row < 0 || row >= m || col < 0 || col >= n) return;
    const ch = board[row][col];
    if (ch === '#' || !node.children[ch]) return; // visited or not in trie
 
    const nextNode = node.children[ch];
    const nextPath = path + ch;
    if (nextNode.isEnd) result.add(nextPath);
 
    board[row][col] = '#'; // mark visited
    dfs(nextNode, row+1, col, nextPath);
    dfs(nextNode, row-1, col, nextPath);
    dfs(nextNode, row, col+1, nextPath);
    dfs(nextNode, row, col-1, nextPath);
    board[row][col] = ch; // restore
  }
 
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      dfs(trie.root, r, c, '');
 
  return [...result];
}

Standard trie for "smart", "smartphone":     Compressed trie:
 
s → m → a → r → t (end)                     "smart" (end)
                  ↓                               ↓
                p → h → o → n → e (end)       "phone" (end)
 
Compressed: "smart" node → "phone" node (stores whole strings, not chars)
Used in: ip routing tables, Unix file systems, autocomplete at scale