Trie (Prefix Tree)

A Trie (pronounced “try”) or Prefix Tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. It is widely used in applications like:

• Autocomplete: Suggesting words based on a prefix.
• Spell Checkers: Verifying if a word exists in a dictionary.
• IP Routing: Longest prefix matching.

1. Anatomy of a Trie

Unlike a Binary Search Tree, nodes in a Trie do not store the keys associated with them. Instead, a node’s position in the tree defines the key.

• Root: Empty node.
• Children: Each node has up to 26 children (for lowercase English letters).
• IsWord: A boolean flag indicating if the path to this node represents a complete word.

Visualization: Trie Construction

Insert words into the Trie and watch how nodes are created and shared.

Words: []

2. Implementation

We typically use a TrieNode class containing an array of children and a boolean flag.

class Trie {
  private class TrieNode {
    private TrieNode[] children;
    private boolean isEnd;

    public TrieNode() {
      children = new TrieNode[26];
      isEnd = false;
    }
  }

  private TrieNode root;

  public Trie() {
    root = new TrieNode();
  }

  // Inserts a word into the trie.
  public void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
      int index = c - 'a';
      if (node.children[index] == null) {
        node.children[index] = new TrieNode();
      }
      node = node.children[index];
    }
    node.isEnd = true;
  }

  // Returns true if the word is in the trie.
  public boolean search(String word) {
    TrieNode node = SearchNode(word);
    return node != null && node.isEnd;
  }

  // Returns true if there is any word in the trie that starts with the given prefix.
  public boolean startsWith(String prefix) {
    return SearchNode(prefix) != null;
  }

  // Helper to find the node for a given string
  private TrieNode SearchNode(String s) {
    TrieNode node = root;
    for (char c : s.toCharArray()) {
      int index = c - 'a';
      if (node.children[index] == null) {
        return null;
      }
      node = node.children[index];
    }
    return node;
  }
}

Complexity Analysis

• Time Complexity: O(L) for insert/search, where L is length of the word.
• Space Complexity: O(N * L), where N is total words and L is average length (in the worst case of no prefix sharing).

Practice Problems

1. Design Add and Search Words Data Structure (Medium)
2. Word Search II (Hard) - Backtracking on a Trie.
3. Maximum XOR of Two Numbers in an Array (Medium) - Bitwise Trie.

3. Deep Dive Strategy Lab: Trie Prefix Tree

Intuition Through Analogy

Think of this chapter like searching text in a large log stream. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?