Algorithms - 6. Trie (Prefix Tree)

When to use Trie

Use a Trie when you need fast prefix-based operations on a collection of strings. The name "Trie" comes from the word "retrieval" (pronounced like "try"), invented by Edward Fredkin in 1960. Though derived from "retrieval," it's specifically designed for rapid string retrieval and prefix matching operations.

Alternative names: Trie is also commonly called a "Prefix Tree" or "Digital Tree". The name "Prefix Tree" is particularly descriptive because every node in the tree represents a common prefix of its descendants. Some literature also refers to it as a "Radix Tree" (though technically a Radix Tree is a space-optimized variant of a Trie).

While most commonly used for word validation, it excels at:

• Autocomplete/suggestions (classic use case - finding all words with a common prefix)
• Spell checkers (checking if a word exists in dictionary)
• IP routing tables (longest prefix matching)
• Phone directory (searching contacts by prefix)
• Word games (validating words in Scrabble, finding words in Boggle)
• Any problem requiring efficient prefix matching or existence checking across many strings

Example problem

Autocomplete System: Given a dictionary of words ["apple", "app", "apricot", "application", "apply", "banana", "band", "bandana"], implement a search system that:

1. Can quickly check if "apple" is a valid word
2. Can find all words starting with "app" for autocomplete
3. Can efficiently add new words to the dictionary

Answer: A Trie handles all three operations in O(m) time where m is the length of the word/prefix, independent of dictionary size!

How a Trie Stores Our Dictionary

Here's how our example words form a Trie structure:

        root
       /    \
      a      b
     /       |
    p        a
   /|\       |\
  p r i      n d
  | | |      | |
  l i c      a a
  | | |      | |
  [e*] c a   [n*] n
      | |        |
      o t        [a*]
      | |
      [t*] i
           |
           o
           |
           [n*]

[*] = end of word marker
Words: app*, apple*, apricot*, application*, apply*, banana*, band*, bandana*

Notice how "app", "apple", "application", and "apply" all share the prefix "app" - stored only once!

Single most important insight

Tries trade space for speed by sharing common prefixes - each path from root to node represents a prefix, allowing O(m) operations regardless of how many strings are stored, because you only traverse the characters you're searching for.

Mental note: The Trie's genius lies in transforming string operations into tree traversals. Instead of comparing entire strings repeatedly, we follow a single path character by character. Each node decision is simply: "Does this character exist as a child?" This simple traversal automatically leverages all shared prefixes.

Why "Trie" not "Tree": Though it's a tree structure, the name "Trie" distinguishes it from general trees by emphasizing its specialized purpose - efficient retrieval of strings through prefix sharing. It's a tree optimized specifically for string operations, not just any hierarchical data.

Decision Framework

The Universal Trie Decision

Every Trie operation boils down to one question:

"Does the current node have a child for this character?"

• YES → Follow that path
• NO → Create it (insert) or return result (search/prefix)

This single decision, repeated for each character, powers all Trie operations.

At every character in your operation, you face this decision:

• During insertion: Create new node or follow existing path?
• During search: Continue down existing path or return false?
• During prefix match: Keep following the path while it exists

Code

Design Choices Explained

function createTrieNode() {
  return {
    isEndOfWord: false,    // Why: Distinguishes complete words from prefixes
    children: new Map()    // Why: Map handles sparse character sets efficiently
  };                       // (vs array[26] which wastes memory for unused letters)
}

Core Trie Implementation

function Trie() {
  const root = createTrieNode();

  function insert(word) {
    let currentNode = root;

    for (const char of word) {
      const hasChildWithChar = currentNode.children.has(char);

      // DECISION FRAMEWORK: Create new path or follow existing?
      if (!hasChildWithChar) {
        const newNode = createTrieNode();
        currentNode.children.set(char, newNode);
      }

      currentNode = currentNode.children.get(char);
    }

    // Mark the end of a complete word
    currentNode.isEndOfWord = true;
  }

  function search(word) {
    let currentNode = root;

    for (const char of word) {
      const hasChildWithChar = currentNode.children.has(char);

      // DECISION FRAMEWORK: Path exists or return false?
      if (!hasChildWithChar) {
        return false; // Character not found, word doesn't exist
      }

      currentNode = currentNode.children.get(char);
    }

    // Found all characters, but is it a complete word?
    const isCompleteWord = currentNode.isEndOfWord;
    return isCompleteWord;
  }

  function startsWith(prefix) {
    let currentNode = root;

    for (const char of prefix) {
      const hasChildWithChar = currentNode.children.has(char);

      // DECISION FRAMEWORK: Continue traversal or prefix not found?
      if (!hasChildWithChar) {
        return false;
      }

      currentNode = currentNode.children.get(char);
    }

    // If we've traversed the entire prefix, it exists
    return true;
  }

  // Return the public interface
  return {
    insert,
    search,
    startsWith
  };
}

// Example usage with our dictionary
const dictionary = Trie();
const words = ["apple", "app", "apricot", "application", "apply"];

for (const word of words) {
  dictionary.insert(word);
}

console.log(dictionary.search("apple"));    // true
console.log(dictionary.search("app"));      // true
console.log(dictionary.search("appl"));     // false (not a complete word)
console.log(dictionary.startsWith("app"));  // true

Step-by-Step: Inserting "app"

Let's trace how we insert the word "app" into an empty Trie:

Starting state: root (empty)

1. Process 'a':
   - Does root have child 'a'? NO
   - Create new node for 'a'
   - Move to node 'a'
   State: root → a

2. Process 'p':
   - Does 'a' have child 'p'? NO
   - Create new node for 'p'
   - Move to first 'p'
   State: root → a → p

3. Process 'p':
   - Does first 'p' have child 'p'? NO
   - Create new node for second 'p'
   - Move to second 'p'
   State: root → a → p → p

4. Mark end of word:
   - Set isEndOfWord = true on second 'p'
   Final: root → a → p → p[*]

Advanced Operations

Finding All Words with a Prefix (Autocomplete)

// Add this to the Trie function's returned object
function findAllWordsWithPrefix(prefix) {
  let currentNode = root;

  // First, navigate to the prefix end
  for (const char of prefix) {
    const hasChildWithChar = currentNode.children.has(char);

    if (!hasChildWithChar) {
      return []; // Prefix doesn't exist
    }

    currentNode = currentNode.children.get(char);
  }

  // Collect all words starting from this node
  const results = [];
  collectWords(currentNode, prefix, results);
  return results;
}

function collectWords(node, currentWord, results) {
  const isWord = node.isEndOfWord;

  if (isWord) {
    results.push(currentWord);
  }

  // Recursively collect from all children
  for (const [char, childNode] of node.children) {
    const nextWord = currentWord + char;
    collectWords(childNode, nextWord, results);
  }
}

// Usage example:
console.log(dictionary.findAllWordsWithPrefix("app"));
// Returns: ["app", "apple", "application", "apply"]

Common Implementation Pitfalls

1. Forgetting the end-of-word marker: Without isEndOfWord, you can't distinguish between "app" (a complete word) and "appl" (just a prefix that exists in "apple")

2. Using arrays instead of Maps:

   • Array approach: children = new Array(26) wastes memory when you only use a few letters
   • Map approach: children = new Map() only stores characters that actually exist

3. Not handling empty strings: Decide upfront - is an empty string a valid word in your Trie? Most implementations treat it as invalid

4. Confusing prefix existence with word existence: "appl" exists as a prefix in our Trie (path to "apple"), but it's not a word itself

Doubt buster

Common doubt: "Won't a Trie use excessive memory? If I have words like 'a', 'ab', 'abc', ..., 'abcdefghijklmnopqrstuvwxyz', I'm creating 26 nodes just for one word!"

Visual Comparison: Trie vs Raw String Storage

Let's analyze storing "algorithm", "algorithms", "algorithmic", "algorithmically":

Without Trie (storing raw strings):
- "algorithm"         → 9 characters
- "algorithms"        → 10 characters
- "algorithmic"       → 11 characters
- "algorithmically"   → 16 characters
Total: 46 character storage units

With Trie (sharing prefixes):
         a-l-g-o-r-i-t-h-m (9 nodes)
                          ├─ [end] (word: "algorithm")
                          ├─ s-[end] (1 node for "algorithms")
                          └─ i-c (2 nodes)
                              ├─ [end] (word: "algorithmic")
                              └─ a-l-l-y-[end] (4 nodes for "algorithmically")
Total: 16 nodes (9 + 1 + 2 + 4)

The Key Insight About Prefix Sharing

The magic: Instead of 46 characters, we only need 16 nodes because "algorithm" is shared by all four words!

Real-world efficiency - Consider a dictionary of English words:

• Words share massive prefixes ("run", "running", "runner", "runs")
• Common patterns emerge ("pre-", "un-", "re-", "-ing", "-ed")
• The more words you add, the more prefix sharing occurs

Example with 1000 words starting with "pre-":

• Naive storage: ~7000 characters (average 7 chars after "pre")
• Trie storage: 3 nodes for "pre" + branching paths (much less than 7000)

When Tries Actually Waste Space

Tries are inefficient when:

1. No common prefixes: Storing ["xyz", "abc", "qrs"] creates completely separate paths
2. Very short strings: Overhead of node structure exceeds string length
3. Random data: UUIDs or hashes have no meaningful prefix patterns

The Space-Time Tradeoff

The brilliance of Tries: They trade space for exceptional time guarantees:

| Operation | HashMap | Trie | |-----------|---------|------| | Insert | O(m) average, O(n×m) worst | O(m) always | | Search | O(m) average, O(n×m) worst | O(m) always | | Prefix match | O(n×m) - check all strings | O(m) - just follow path | | Autocomplete | O(n×m) - scan everything | O(m+k) - m for prefix, k for results |

Where n = number of strings, m = string length, k = number of results

The guarantee: While Tries may use more memory for random strings, they provide unbeatable time complexity for prefix operations. In domains with natural prefix patterns (words, URLs, file paths), they're both time AND space efficient!