Tries (Prefix Trees)

A Trie (pronounced "try") is a specialized tree data structure used for efficient retrieval of a key in a large dataset of strings. Unlike a BST where each node stores a full word, a Trie stores characters. The path from the root down to a specific node represents a string prefix.

Real-Life Analogy

Think of Google Autocomplete. When you type "c-a-t", Google instantly drops down suggestions like "cat", "cats", "catch". Google is traversing a Trie. It starts at the root, moves to c, then a, then t. At that node, it looks down at the children to see all possible words that share the exact prefix "cat".

Memory Layout

The Root node is empty. Each node contains a Hash Map (or Array) mapping a character to its child node. Each node also contains a boolean flag isEndOfWord to signify if the path down to that character completes a valid dictionary word.

This Trie contains the words: "car", "cat", "cats", and "dog". Notice how "cat" and "cats" share the identical "c-a-t" branch!

Time Complexity

Let $L$ be the length of the string/word.

[!TIP] Hash Tables can also search for a word in $O(1)$ time. So why use a Trie? Hash Tables cannot do Prefix Matching! If you want to find all words starting with "app", a Hash Table is useless because the hash of "apple" is completely different from the hash of "app". A Trie easily solves this.

Implementation in Code

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 O(L)
  public insert(word: string): void {
    let curr = this.root;
    for (const char of word) {
      if (!curr.children.has(char)) {
        curr.children.set(char, new TrieNode());
      }
      curr = curr.children.get(char)!;
    }
    curr.isEndOfWord = true; // Mark the end of the word
  }

  // Search O(L)
  public search(word: string): boolean {
    let curr = this.root;
    for (const char of word) {
      if (!curr.children.has(char)) {
        return false;
      }
      curr = curr.children.get(char)!;
    }
    return curr.isEndOfWord; // Must be a complete word, not just a prefix!
  }

  // StartsWith O(L)
  public startsWith(prefix: string): boolean {
    let curr = this.root;
    for (const char of prefix) {
      if (!curr.children.has(char)) {
        return false; // Prefix doesn't exist at all
      }
      curr = curr.children.get(char)!;
    }
    return true; // We don't care if it's the end of a word!
  }
}