Tries

A Trie (prefix tree) is a tree-shaped data structure where each node represents a single character and the path from root to a node spells a prefix. Tries give O(m) insert, search, and prefix-match where m is the word length — far faster than scanning an array of strings for prefix queries.

Core Implementation

class TrieNode {
  constructor() {
    this.children = {};   // char -> TrieNode
    this.isEnd = false;   // marks end of a valid word
  }
}

class Trie {
  constructor() { this.root = new TrieNode(); }

  // O(m)
  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.isEnd = true;
  }

  // O(m) — returns true if exact word exists
  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }

  // O(m) — returns true if any word starts with prefix
  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }

  _traverse(str) {
    let node = this.root;
    for (const ch of str) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }
}

Autocomplete

Navigate to the prefix node, then collect all words in that subtree using DFS.

Trie.prototype.autocomplete = function(prefix) {
  const node = this._traverse(prefix);
  if (!node) return [];
  const results = [];
  const dfs = (n, current) => {
    if (n.isEnd) results.push(current);
    for (const [ch, child] of Object.entries(n.children)) dfs(child, current + ch);
  };
  dfs(node, prefix);
  return results;
};

const t = new Trie();
['apple', 'app', 'application', 'apt'].forEach(w => t.insert(w));
t.autocomplete('app'); // ['app', 'apple', 'application']

Word Search in a Board

Build a Trie from the word list, then DFS across the board. The Trie lets you prune paths that cannot complete any word early — far faster than checking each word individually.

function findWords(board, words) {
  const trie = new Trie();
  words.forEach(w => trie.insert(w));
  const found = new Set();
  const rows = board.length, cols = board[0].length;

  function dfs(node, r, c, path) {
    if (node.isEnd) found.add(path);
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] === '#') return;
    const ch = board[r][c];
    const child = node.children[ch];
    if (!child) return;
    board[r][c] = '#'; // mark visited
    for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) dfs(child, r+dr, c+dc, path+ch);
    board[r][c] = ch; // restore
  }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      dfs(trie.root, r, c, '');

  return [...found];
}

Compressed Trie (Radix Tree)

A standard Trie wastes nodes on long chains with no branching. A radix tree compresses each unbranched chain into a single node storing the whole substring. JavaScript's Map-based route matching (e.g., Express, React Router) is implemented with a radix tree under the hood.

Complexity

• Insert / Search / StartsWith: O(m) time where m = key length
• Space: O(ALPHABET × total characters) — can be large for broad alphabets
• Autocomplete: O(m + k) where k = number of matching words returned