Tries (Prefix Trees) & Radix Trees: Autocomplete, IP Routing, and Lexical Engines

If you have $100,000,000$ product titles in an e-commerce catalog and a user types "pro" into the search bar, how do you return the top 5 autocomplete suggestions in under a millisecond? Hint: You don't scan a Hash Table, and you don't stop at a Binary Search Tree.

---

In Article 5, we saw that Hash Tables achieve $O(1)$ exact lookups by scrambling keys across buckets—which completely destroys prefix relationships ("pro", "prod", "product" land in totally unrelated buckets).

In Article 6, we saw that a Balanced Binary Search Tree preserves alphabetical order, but searching for a string of length $L$ across $N$ strings requires $O(\log_2 N)$ node comparisons, where each comparison may scan up to $L$ characters—totaling $O(L \cdot \log_2 N)$ time.

What if we designed a tree where the lookup time didn't depend on the number of stored words $N$ at all, but only on the length $L$ of the word you are typing?

Welcome to the Trie (Prefix Tree) and its space-optimized sibling, the Radix Tree (Compact Prefix Tree)—the structures that power real-time search autocomplete, high-speed HTTP API routers, full-text search engines, and core internet BGP/IPv4 routing tables.

---

1. The Academic Foundation: Digital Search and $O(L)$ Prefix Traversal

Named by Edward Fredkin in 1960 from the middle syllable of retrieval (and pronounced "try" in academic lectures to distinguish it from "tree"), a Trie is a $k$-ary search tree where:

1. Unlike a BST, no node stores the full key. Instead, a node's position in the tree defines the prefix associated with it.
2. Each edge leaving a node represents a single character (or byte/bit) from the alphabet $\Sigma$.
3. Every node carries a boolean flag isEndOfWord (and optionally a frequency weight or route handler payload) indicating whether the path from the root to that node forms a complete registered key.

flowchart TB
    Root(("ROOT"))
    T["'t'"]
    TE["'e'"]
    TEA["'a'<br/>(isWord: true, freq: 85)"]
    TEAM["'m'<br/>(isWord: true, freq: 140)"]
    TED["'d'<br/>(isWord: true, freq: 30)"]
    TO["'o'<br/>(isWord: true, freq: 500)"]
    TOO["'o'"]
    TOOL["'l'<br/>(isWord: true, freq: 320)"]

    Root --> T
    T --> TE
    T --> TO
    TE --> TEA
    TEA --> TEAM
    TE --> TED
    TO --> TOO
    TOO --> TOOL

Why Trie Prefix Search Is Independent of Dataset Size $N$

Suppose a user types the 3-character prefix "tea" into a Trie holding $N = 50,000,000$ words:

1. Start at ROOT.
2. Follow edge 't' (step 1) $\rightarrow$ edge 'e' (step 2) $\rightarrow$ edge 'a' (step 3).
3. In exactly $L = 3$ pointer hops ($O(L)$ time!), you are standing at the "tea" node. Every single word in the entire 50-million-word dictionary that starts with "tea" is guaranteed to live in the subtree directly beneath this node!

Compressing Chains: The Radix Tree (Patricia Trie)

In a standard Trie, long words that don't branch (like "microservices" or URL segments like "/api/v1/organizations/") create long chains of single-child nodes, wasting memory and CPU cache lines.

A Radix Tree (Compact Prefix Tree) merges every single-child chain into a single edge labeled with a full substring:

flowchart LR
    subgraph StandardTrie["Uncompressed Trie: 7 Nodes for 'tool' & 'toon'"]
        direction LR
        R1(("Root")) --> N_t["t"] --> N_o1["o"] --> N_o2["o"]
        N_o2 --> N_l["l (Word)"]
        N_o2 --> N_n["n (Word)"]
    end

    subgraph RadixTree["Compressed Radix Tree: 3 Nodes"]
        direction LR
        R2(("Root")) --> Edge_too["'too'"]
        Edge_too --> Leaf_l["'l' (Word)"]
        Edge_too --> Leaf_n["'n' (Word)"]
    end

Complexity Comparison Table

Structure ($N$ keys, avg length $L$)	Exact Lookup	Prefix Match (startsWith(P))	Insert / Delete	Space Overhead
Hash Table	$O(L)$ (to hash string)	$O(N \cdot L)$ (Full table scan!)	$O(L)$	Low
Balanced BST	$O(L \cdot \log N)$	$O(L \cdot \log N + K)$	$O(L \cdot \log N)$	Medium
Standard Trie	$O(L)$	$O(P + K)$	$O(L)$	High (shared prefixes compressed)
Radix Tree (Compact Trie)	$O(L)$	$O(P + K)$	$O(L)$	Low/Medium (path-compressed)

---

2. Under the Hood: Testable Ranked Autocomplete Trie & Wildcard Matcher

Below is a complete, zero-dependency TypeScript implementation of a Frequency-Ranked Autocomplete Trie supporting:

1. $O(L)$ word insertion with popularity scoring.
2. $O(P)$ prefix navigation + ranked Top-$K$ suggestion retrieval.
3. Glob/wildcard pattern matching (searchPattern("t..l") where . matches any single character—a classic lexical engine feature!).

Copy and execute this code directly in the JS/TS Playground:

class TrieNode {
  public readonly children = new Map<string, TrieNode>();
  public isEndOfWord: boolean = false;
  public frequency: number = 0;
  public word: string | null = null;
}

export interface AutocompleteSuggestion {
  word: string;
  frequency: number;
}

/**
 * Production-Style Ranked Autocomplete & Lexical Prefix Tree (Trie)
 */
class AutocompleteTrie {
  private readonly root = new TrieNode();
  private _wordCount: number = 0;

  public get wordCount(): number {
    return this._wordCount;
  }

  /**
   * O(L) Insert or Increment Search Term Popularity
   */
  public insert(rawWord: string, frequencyBoost: number = 1): void {
    const word = rawWord.trim().toLowerCase();
    if (!word) return;

    let current = this.root;
    for (const ch of word) {
      let next = current.children.get(ch);
      if (!next) {
        next = new TrieNode();
        current.children.set(ch, next);
      }
      current = next;
    }

    if (!current.isEndOfWord) {
      current.isEndOfWord = true;
      current.word = word;
      this._wordCount++;
    }
    current.frequency += frequencyBoost;
  }

  /**
   * O(L) Exact Word Check
   */
  public hasExact(rawWord: string): boolean {
    const node = this.traversePrefix(rawWord.trim().toLowerCase());
    return node !== null && node.isEndOfWord;
  }

  /**
   * O(P + Subtree) Ranked Top-K Autocomplete Suggestions
   */
  public autocomplete(rawPrefix: string, limit: number = 5): AutocompleteSuggestion[] {
    const prefix = rawPrefix.trim().toLowerCase();
    const prefixNode = this.traversePrefix(prefix);
    if (!prefixNode) {
      return [];
    }

    const matches: AutocompleteSuggestion[] = [];
    this.collectWords(prefixNode, matches);

    // Sort descending by frequency, then alphabetically for deterministic ties
    matches.sort((a, b) =>
      b.frequency !== a.frequency
        ? b.frequency - a.frequency
        : a.word.localeCompare(b.word)
    );

    return matches.slice(0, limit);
  }

  /**
   * Backtracking Wildcard Search: '.' matches any single character
   * Example: "t..l" matches "tool" and "tall"
   */
  public searchWildcard(pattern: string): string[] {
    const results: string[] = [];
    const cleanPattern = pattern.trim().toLowerCase();

    const dfs = (node: TrieNode, index: number): void => {
      if (index === cleanPattern.length) {
        if (node.isEndOfWord && node.word !== null) {
          results.push(node.word);
        }
        return;
      }

      const ch = cleanPattern[index];
      if (ch === ".") {
        for (const childNode of node.children.values()) {
          dfs(childNode, index + 1);
        }
      } else {
        const nextNode = node.children.get(ch);
        if (nextNode) {
          dfs(nextNode, index + 1);
        }
      }
    };

    dfs(this.root, 0);
    return results.sort();
  }

  private traversePrefix(prefix: string): TrieNode | null {
    let current = this.root;
    for (const ch of prefix) {
      const next = current.children.get(ch);
      if (!next) return null;
      current = next;
    }
    return current;
  }

  private collectWords(node: TrieNode, out: AutocompleteSuggestion[]): void {
    if (node.isEndOfWord && node.word !== null) {
      out.push({ word: node.word, frequency: node.frequency });
    }
    for (const child of node.children.values()) {
      this.collectWords(child, out);
    }
  }
}

// ============================================================================
// Verification & Execution
// ============================================================================
const searchEngine = new AutocompleteTrie();

// Seed dictionary with search terms and historical query counts
const catalog: Array<[string, number]> = [
  ["typescript", 950],
  ["typechecker", 310],
  ["types", 620],
  ["typography", 180],
  ["tool", 540],
  ["toolkit", 410],
  ["tall", 120],
  ["terminal", 490],
];

for (const [term, freq] of catalog) {
  searchEngine.insert(term, freq);
}

console.log("Total Indexed Terms:", searchEngine.wordCount); // 8
console.log("Top 3 Autocomplete for 'typ':", JSON.stringify(searchEngine.autocomplete("typ", 3)));
// Expected: [{"word":"typescript","frequency":950},{"word":"types","frequency":620},{"word":"typechecker","frequency":310}]

console.log("Wildcard Match 't..l':", searchEngine.searchWildcard("t..l"));
// Expected: ["tall", "tool"]

---

3. Where Tries & Radix Trees Live in Production Systems

1. High-Throughput HTTP Routers (Fastify find-my-way, Go httprouter, Gin)

Early web frameworks (like Express.js) matched incoming URLs against an array of regular expressions one by one—an $O(R)$ linear scan across $R$ registered routes.

Modern high-performance web frameworks like Fastify (Node.js) and Gin / httprouter (Go) compile all registered routes (/api/v1/users/:id, /api/v1/users/settings, /api/v2/posts) into a Radix Tree:

• All routes starting with /api/v1/ share the exact same root edge!
• Matching an incoming request URL takes $O(\text{URL length})$ time regardless of whether your microservice defines $10$ routes or $10,000$ routes.

2. Core Internet Routers: Longest Prefix Match (LPM) in CIDR IP Routing

Every time an IP packet travels across the internet, backbone routers must inspect the destination IPv4/IPv6 address and pick the routing table rule with the Longest Prefix Match (LPM)—for example, preferring a specific /24 subnet (192.168.1.0/24) over a broader /16 supernet (192.168.0.0/16). (You can calculate CIDR bitmasks, network ranges, and host blocks interactively using our Subnet Calculator and inspect IP metadata with the IP Geolocation Tool.)

How do hardware routers perform Longest Prefix Match across $1,000,000+$ global BGP routes at 100 Gigabits per second? They store CIDR binary prefixes inside a Compressed Multibit Binary Trie (Luleå / Tree Bitmap algorithm) directly in ASIC SRAM!

3. Elasticsearch & Apache Lucene: Finite State Transducers (FSTs)

How does Elasticsearch search billions of documents for terms, prefixes, and fuzzy typos (Levenshtein Automaton) while keeping the term dictionary small enough to fit entirely in RAM?

Lucene compiles its sorted term index into a Finite State Transducer (FST)—which is a Trie that shares both common prefixes AND common suffixes (turning the tree into a minimal Directed Acyclic Word Graph), compressing dictionary memory footprints by $4\times\text{–}20\times$.

---

4. The Professor's Architecture Cheat Sheet

When to Choose a Trie or Radix Tree:

• Autocomplete, Typeahead, and Spellcheckers: Real-time prefix filtering and Levenshtein edit-distance search (which you can pair with text analysis tools like our Find & Replace and Word Counter).
• Hierarchical Path Routing & Permission Trees: HTTP URL routing, file path matching, and wildcard topic subscriptions in message brokers (e.g., MQTT sensors/+/temperature).
• IP Subnet & CIDR Lookup Tables: Binary Longest Prefix Matching.

When NOT to Choose a Standard Uncompressed Trie:

• Exact Key-Value Lookups on Long Random Strings (like UUIDs or SHA-256 Hashes): Because random hashes share almost no common prefixes, an uncompressed Trie explodes into millions of sparse single-child pointer nodes. Use a Hash Table for exact match or a Radix Tree when path compression is needed.