Tries (Prefix Trees)

A trie (pronounced "try", from re_trie_val) is a tree where each edge is labelled with a character, and each path from the root spells out a prefix. Words that share a prefix share the same path — "car", "card", and "care" all travel down the same c → a → r spine before branching.

That shared structure is the whole point. Instead of comparing a query against every stored word, a trie walks one character at a time, and the branching factor does the filtering for you. Looking up a word — or checking whether any word starts with a given prefix — takes time proportional to the length of the query, not to how many words you have stored.

Anatomy of a node

Each node holds two things: a children map from the next character to a child node, and an isEnd flag marking whether a complete word ends here. The flag matters because "car" is a real word even though its path continues on to "card" — without isEnd you could not tell a stored word from a mere prefix.

• children: a map (or array) from a single character to the child node for that character.
• isEnd: true when the path from the root to this node spells a complete inserted word.
• The root represents the empty prefix and stores no character of its own.

Insert, search, and startsWith

All three operations are the same walk: descend character by character from the root. Insert creates missing child nodes as it goes and sets isEnd at the last character. Search walks the same path and checks isEnd at the end. startsWith is search without the isEnd check — it only cares that the path exists.

class TrieNode {
  constructor() {
    this.children = new Map()   // char -> TrieNode
    this.isEnd = false
  }
}

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

  insert(word) {
    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
  }

  // walk the path; return the final node or null if it breaks
  _walk(prefix) {
    let node = this.root
    for (const ch of prefix) {
      if (!node.children.has(ch)) return null
      node = node.children.get(ch)
    }
    return node
  }

  search(word) {
    const node = this._walk(word)
    return node !== null && node.isEnd   // must be a full word
  }

  startsWith(prefix) {
    return this._walk(prefix) !== null   // path just has to exist
  }
}

Autocomplete — the killer app

The distinction between search and startsWith is exactly what powers autocomplete. Walk to the node for the typed prefix, then DFS the subtree beneath it, collecting every path that hits an isEnd. Those are all the completions of what the user has typed so far.

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