advanced-strings • Intermediate

Trie (Prefix Tree) & Autocomplete Dictionaries

A Trie is a multi-way tree structure where each node represents a character. Searching, inserting, and prefix matching ("app", "apple", "apply") executes in O(L) time where L is word length.

Intuitive Mental Model

The Phonebook Keypad: Pressing 'A' filters to all A-words; pressing 'P' narrows to AP-words; pressing 'P' narrows to APP-words.

C / TypeScript ImplementationHardware & Algorithmic Standard

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord = false;
}

class Trie {
  root = new TrieNode();
  insert(word: string): void {
    let curr = this.root;
    for (const ch of word) {
      if (!curr.children.has(ch)) curr.children.set(ch, new TrieNode());
      curr = curr.children.get(ch)!;
    }
    curr.isEndOfWord = true;
  }
}

Key Architectural Takeaways

•O(L) Prefix Search: Time complexity depends only on the query word length L, independent of dictionary size N.
•Autocomplete & IP Routing: Used for Longest Prefix Match in router CIDR routing tables.

Common Coding Mistake

Using a fixed array TrieNode[26] in memory-constrained environments with large alphabets (Unicode), wasting huge heap RAM.

Optimal Solution

Use HashMaps or Radix Trees (Compressed Tries) for sparse node allocations.

Next: Suffix Arrays & Kasai's Longest Common Prefix (LCP)