Trie (Prefix Tree)

Tree where each node represents a character. Enables O(m) prefix lookups.

How it works

A Trie (pronounced "try", from retrieval) is a specialized tree where each node represents a single character. A path from the root to a terminal node spells out a stored word.

Key properties: - Prefix sharing: words with a common prefix share nodes (e.g., "the", "their", "there" all share "t→h→e"). - O(m) insert and search, where m is the word length — independent of how many words are stored. - Enables powerful prefix queries: autocomplete, spell-check, IP routing.

Compared to a hash map: a trie uses more memory per entry but natively supports ordered traversal and prefix matching, which hash maps cannot do efficiently.

Complexity

Best case

O(m)

Average case

O(m)

Worst case

O(m)

Space

O(ALPHABET × n)

Visualizer

Generating steps…

Where it's used in the real world

Search engines / autocomplete

Prefix suggestions

Google's search bar and IDE auto-complete descend a trie (or a compressed variant like a DAWG/FST) to enumerate all completions for the typed prefix in microseconds.

IP routing (Linux kernel)

Longest-prefix match

The Linux kernel's FIB trie performs longest-prefix-match on IP addresses using a bitwise trie, selecting the most specific routing rule for every packet.

Spell checkers / dictionaries

Word validation and suggestions

Hunspell (used in LibreOffice, Firefox) stores dictionaries as compressed tries to check whether a string is a valid word and to enumerate similar words for suggestions.

Implementation

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

class Trie {
  root = new TrieNode();

  insert(word: string): void {
    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;
  }

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

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

const t = new Trie();
["the", "their", "there", "a", "any"].forEach(w => t.insert(w));
console.log(t.search("their"));    // true
console.log(t.search("th"));       // false (prefix only)
console.log(t.startsWith("th"));   // true

Related algorithms

Hash TableLive

Key-value store with O(1) average lookup using a hash function.

O(1)

KMP String SearchLive

Find pattern in text in O(n+m) using a failure function.

O(n+m)