Exploring Trie Data Structure in TypeScript: Implementation and Applications

Type "pro" into a search bar and get suggestions for "programming," "product," and "profile." Behind that feature is often a trie.

20 Apr 2024

Type "pro" into a search bar and get suggestions for "programming," "product," and "profile." Behind that feature is often a trie.

A trie (pronounced "try") is a tree where each node represents a single character. Paths from root to leaf spell out words. Shared prefixes share nodes. The word "apple" and "app" share the nodes a-p-p, then diverge.

This structure makes prefix-based lookups extremely fast -- O(m) where m is the length of the word, regardless of how many words are stored.

Implementation

Typescript

class TrieNode {
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

class Trie {
  root: TrieNode;

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

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

  search(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) return false;
      node = node.children.get(char)!;
    }
    return node.isEndOfWord;
  }

  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return false;
      node = node.children.get(char)!;
    }
    return true;
  }

  autocomplete(prefix: string): string[] {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return [];
      node = node.children.get(char)!;
    }

    const results: string[] = [];
    this.collect(node, prefix, results);
    return results;
  }

  private collect(node: TrieNode, prefix: string, results: string[]): void {
    if (node.isEndOfWord) results.push(prefix);
    for (const [char, child] of node.children) {
      this.collect(child, prefix + char, results);
    }
  }
}

Typescript

const trie = new Trie();
trie.insert('apple');
trie.insert('app');
trie.insert('application');

console.log(trie.search('apple'));       // true
console.log(trie.search('app'));         // true
console.log(trie.search('ap'));          // false
console.log(trie.startsWith('app'));     // true
console.log(trie.autocomplete('app'));   // ['app', 'apple', 'application']

Where Tries Excel

Autocomplete systems: Type a prefix, get all matching words in O(m + k) where m is prefix length and k is the number of results.
Spell checkers: Store a dictionary in a trie. Check if a word exists in O(m). Suggest corrections by traversing nearby nodes.
IP routing: Longest prefix match on binary tries is how routers determine where to forward packets.
Text indexing: Tries can index documents for fast prefix-based search across large datasets.

The Trade-off

Tries use more memory than hash tables. Each character gets its own node with a Map of children. For a dictionary of English words, this adds up.

A hash set can check if a word exists in O(1) average case, and uses less memory. But it can't do prefix queries. You can't ask a hash set "give me all words starting with 'pro'" without checking every entry.

If your use case involves prefix matching, autocomplete, or ordered iteration of strings, a trie is the right tool. For simple existence checks, a hash set wins.

Go further

Production-Ready Systems with LLMs and Agents

A hands-on Maven cohort: six weeks, twelve live sessions, five graded projects where you ship real LLM and agent systems that survive real traffic, cost, and failure, not notebooks.

Use code AGENTS300 for $300 off: early-bird, capped at 12 seats.

Free lessonPrompting Like an Engineer, Not a Wizard

Exploring Trie Data Structure in TypeScript: Implementation and Applications

Implementation

Where Tries Excel

The Trade-off

Production-Ready Systems with LLMs and Agents

Keep reading