What is a Trie and a common use case?

Deep dive

A trie (prefix tree) stores keys character-by-character. Each node is a prefix, and a terminal marker indicates a full word. Operations depend on key length L, not on the number of stored keys (aside from memory and cache effects).

Typical operations:

• insert(word): O(L)
• search(word): O(L)
• startsWith(prefix): O(L)

Common use cases

• Autocomplete / prefix search (type-ahead).
• Dictionary + spell checking.
• Routing / IP prefixes (often via compressed tries).

Examples

type Node = { end: boolean; next: Map<string, Node> }
const root: Node = { end: false, next: new Map() }

function insert(word: string) {
  let node = root
  for (const ch of word) {
    const child = node.next.get(ch) ?? { end: false, next: new Map() }
    node.next.set(ch, child)
    node = child
  }
  node.end = true
}

function startsWith(prefix: string): boolean {
  let node = root
  for (const ch of prefix) {
    const child = node.next.get(ch)
    if (!child) return false
    node = child
  }
  return true
}

Trade-offs

• Tries can be memory-heavy (many nodes). Variants like radix trees/compact tries reduce overhead.
• Alphabet size matters: arrays are fast for small alphabets; maps save memory for sparse nodes.

Common pitfalls

• Ignoring Unicode normalization/case-folding (prefixes may not match what users expect).