The Trie: Fast Prefix Search Explained

Type git ch into a command palette and useful suggestions appear before the full command exists. Enter mar in a contacts field and names beginning with those letters arrive immediately. These interactions are not ordinary exact-key lookups: the query is an incomplete string, and every completion sharing that prefix may be relevant.

A hash table is excellent when the whole key is known, but it does not preserve relationships between keys. A trie, pronounced “try” and named after retrieval, makes those relationships explicit. Each edge contributes a symbol, and each path from the root represents a prefix. Words with the same beginning share the same path, so prefix lookup depends primarily on the prefix length rather than the number of stored words.

That attractive bound is only the start. A practical trie must define what a character means, control substantial pointer overhead, rank results, delete safely, survive persistence and concurrent access, and sometimes admit that a sorted array or hash table is the better tool.

Why Prefix Search Changes the Index #

Suppose the dictionary contains car, card, care, cat, and dog. A hash set can answer whether care exists in expected $O(L)$ time, where L is the number of symbols in the query. To answer “which values start with ca?”, however, it must scan keys or maintain another ordered index. The hash function deliberately destroys the lexical neighborhood that prefix search needs.

A sorted array preserves that neighborhood. Binary search can find the first candidate in $O(P \log N)$ comparisons, where P is prefix length and N is the number of keys, then scan the matching range. This is often remarkably effective for static data because arrays are compact and cache-friendly.

A trie takes a different route. Starting at the root, follow one edge per prefix symbol. If any edge is absent, no completion exists. If the path exists, its final node is the root of exactly the matching subtree.

An asterisk marks a terminal node. car must be terminal even though it also has children; otherwise the structure could represent card and care but not distinguish car as a stored key. The path to ca is not terminal in this example, yet it is a valid prefix.

A Unicode-Aware TypeScript Trie #

The implementation below supports insertion, exact search, prefix checks, ranked autocomplete, and deletion. It keeps two forms of a term: a normalized key used for traversal and the original display string stored at the terminal node. Without that separation, case folding could make suggestions look unnatural to users.

Normalization is injectable because no universal policy exists. The default applies NFC normalization and English-locale lowercase conversion. NFC makes canonically equivalent sequences such as a precomposed é and e plus a combining accent follow the same path. A Turkish product, a case-sensitive symbol index, or a system that strips accents should provide a policy appropriate to its domain.

type Normalizer = (value: string) => string;

type Suggestion = {
  value: string;
  score: number;
};

class TrieNode {
  readonly children = new Map<string, TrieNode>();
  terminalValue: string | undefined;
  score = 0;
}

export class Trie {
  private readonly root = new TrieNode();

  constructor(
    private readonly normalize: Normalizer = (value) =>
      value.normalize('NFC').toLocaleLowerCase('en-US'),
  ) {}

  insert(value: string, score = 0): void {
    const key = this.normalize(value);
    if (key.length === 0) {
      throw new Error('Trie keys must not be empty');
    }

    let node = this.root;
    for (const symbol of key) {
      let child = node.children.get(symbol);
      if (!child) {
        child = new TrieNode();
        node.children.set(symbol, child);
      }
      node = child;
    }

    node.terminalValue = value;
    node.score = score;
  }

  search(value: string): boolean {
    const node = this.findNode(this.normalize(value));
    return node?.terminalValue !== undefined;
  }

  hasPrefix(prefix: string): boolean {
    return this.findNode(this.normalize(prefix)) !== undefined;
  }

  autocomplete(prefix: string, limit = 10): Suggestion[] {
    if (!Number.isInteger(limit) || limit < 0) {
      throw new Error('limit must be a non-negative integer');
    }

    const start = this.findNode(this.normalize(prefix));
    if (!start || limit === 0) return [];

    const candidates: Suggestion[] = [];
    const visit = (node: TrieNode): void => {
      if (node.terminalValue !== undefined) {
        candidates.push({ value: node.terminalValue, score: node.score });
      }
      for (const child of node.children.values()) visit(child);
    };

    visit(start);
    candidates.sort(
      (left, right) =>
        right.score - left.score || left.value.localeCompare(right.value),
    );
    return candidates.slice(0, limit);
  }

  delete(value: string): boolean {
    const symbols = Array.from(this.normalize(value));

    const remove = (
      node: TrieNode,
      index: number,
    ): { deleted: boolean; prune: boolean } => {
      if (index === symbols.length) {
        if (node.terminalValue === undefined) {
          return { deleted: false, prune: false };
        }
        node.terminalValue = undefined;
        node.score = 0;
        return { deleted: true, prune: node.children.size === 0 };
      }

      const symbol = symbols[index];
      if (symbol === undefined) return { deleted: false, prune: false };
      const child = node.children.get(symbol);
      if (!child) return { deleted: false, prune: false };

      const result = remove(child, index + 1);
      if (result.prune) node.children.delete(symbol);
      return {
        deleted: result.deleted,
        prune: node.terminalValue === undefined && node.children.size === 0,
      };
    };

    return remove(this.root, 0).deleted;
  }

  private findNode(key: string): TrieNode | undefined {
    let node = this.root;
    for (const symbol of key) {
      const child = node.children.get(symbol);
      if (!child) return undefined;
      node = child;
    }
    return node;
  }
}

JavaScript strings use UTF-16 internally, but for...of and Array.from iterate Unicode code points rather than individual code units. That avoids splitting an astral character into two invalid edges. It still does not segment user-perceived grapheme clusters: an emoji plus modifiers or a family joined with zero-width joiners can span several code points. Use Intl.Segmenter if product semantics require one edge per grapheme. More importantly, apply exactly the same normalization during insert, search, delete, and prefix lookup. Inconsistent normalization creates entries that were successfully written but can never be found.

Deletion deserves attention. Clearing car must retain the nodes needed by card; clearing card may remove only the now-unused d branch. The recursive result therefore separates “a key was deleted” from “this node is safe to prune.”

Complexity Is More Than the Prefix Walk #

Let L be the number of normalized symbols in a full key, P the symbols in a prefix, S the nodes visited below the matched prefix, R the number of terminal results found, K the requested result limit, and U the number of distinct prefix nodes stored.

The headline $O(P)$ bound finds the subtree; it cannot output R strings in less than $O(R)$ time. The sample autocomplete is intentionally clear, not optimal for a huge popular prefix such as an empty string. A size-K min-heap reduces ranking selection to $O(R \log K)$, though traversal still touches S nodes. Caching the top K suggestions at every node can make reads approach $O(P + K)$ while increasing memory and making every score update more expensive.

Memory is often the trie’s limiting factor. A Map, object header, pointers, allocator alignment, terminal value, and score can cost far more than the character represented by a node. Shared prefixes save character storage conceptually, yet a sparse JavaScript object graph can still be much larger than the source strings. Measure retained heap size with realistic data; node count alone is not a memory budget.

Compression, Ranking, and Update Strategy #

A radix tree, also called a compressed trie or Patricia-style trie in related binary settings, collapses every chain of single-child nodes into one edge labeled with a string fragment. Instead of c -> a -> r, it may store one car edge until the path branches. Lookup still compares the same symbols, but there are fewer objects and pointer hops. Insertions and deletions become more involved because edges may need to split or merge.

For large static vocabularies, a succinct trie, minimal deterministic acyclic word graph, or finite-state transducer can share equivalent suffix structure and encode edges in compact arrays. These representations trade simple mutation for smaller memory, sequential access, and fast loading. They are excellent for dictionaries shipped with an application and less convenient for a suggestion set changing every second.

Ranking changes the data model, not just the final sort. A production score might combine global frequency, freshness, edit distance, language, account-specific history, and business rules. Store stable global signals in the index, but avoid multiplying the trie per user. Fetch a modest global candidate set, then rerank it with request-specific signals. Define deterministic tie-breaking so pagination, snapshots, and tests do not flicker.

There are three common strategies for top results:

Approximate matching is a separate requirement. A plain trie handles prefixes, not typos in arbitrary positions. A Levenshtein automaton can traverse only trie paths within a chosen edit distance, but it adds state and can become expensive for generous thresholds. Do not advertise typo tolerance merely because autocomplete exists.

Persistence, Concurrency, and Tests #

The class above is an in-memory mutable index. Persisting it as deeply nested JSON is easy but bloated, slow to parse, and awkward to version. Often the source of truth should remain a database or append-only log, with the trie rebuilt as a derived index. For quick startup, write a versioned snapshot using flat node and edge arrays, record the normalization and scoring versions, and replay updates after the snapshot offset.

In a single JavaScript event loop, each synchronous method is atomic with respect to other callbacks, but a sequence such as “read score, await, update score” is not. Workers and server replicas add real parallelism. One practical design has a single writer publish immutable snapshots while readers retain a snapshot reference for the duration of a request. Copy-on-write paths make that possible without cloning the whole trie. Other systems put a read-write lock around a mutable index or route mutations through one owner. Whichever model is chosen, define whether readers need the latest write or merely a consistent version.

Tests should target invariants and adversarial boundaries rather than only happy examples:

import { describe, expect, it } from 'vitest';
import { Trie } from './trie.js';

describe('Trie', () => {
  it('distinguishes complete keys from prefixes and ranks matches', () => {
    const trie = new Trie();
    trie.insert('car', 2);
    trie.insert('card', 7);
    trie.insert('care', 5);

    expect(trie.search('ca')).toBe(false);
    expect(trie.hasPrefix('ca')).toBe(true);
    expect(trie.autocomplete('car', 2).map((item) => item.value)).toEqual([
      'card',
      'care',
    ]);
  });

  it('normalizes equivalent Unicode and prunes only unused branches', () => {
    const trie = new Trie();
    trie.insert('Café');
    trie.insert('cafeteria');

    expect(trie.search('CAFE\u0301')).toBe(true);
    expect(trie.delete('café')).toBe(true);
    expect(trie.search('Café')).toBe(false);
    expect(trie.search('cafeteria')).toBe(true);
    expect(trie.delete('missing')).toBe(false);
  });
});

Add property-based tests when the trie becomes infrastructure. Generate operation sequences and compare exact membership with a reference Map normalized by the same function. After every insertion and deletion, verify that autocomplete contains only keys with the requested normalized prefix, has no duplicates, respects ranking order, and never loses a neighboring key. Include empty input, duplicate insertion, zero limits, very long keys, combining marks, astral symbols, and locale-sensitive case mappings.

Choosing the Smallest Correct Index #

Tries are compelling when prefix queries dominate, vocabulary is large enough to justify an index, and latency must be predictable with respect to prefix length. They also enable lexicographic traversal and can share prefixes in datasets such as routes, identifiers, dictionary words, and IP prefixes. They are not an automatic upgrade for every string collection.

For fifty command names, a filtered array may be clearer and fast enough. For a static list of a million normalized terms, a sorted packed array can beat a JavaScript trie in both memory and wall-clock time. For exact session-token lookup, use a hash table. The right decision comes from query shape, update rate, latency distribution, and measured memory, not from the most attractive asymptotic row.

Takeaways #

• A trie turns shared prefixes into shared paths, finding a prefix subtree in expected $O(P)$ time.
• Terminal markers distinguish a stored key from a path that merely leads to longer keys.
• Unicode normalization is part of the index contract; use the same policy for every operation and preserve display values separately.
• Autocomplete cost includes descendant traversal and ranking. Heap selection or per-node top-K caches optimize different workloads.
• Node and pointer overhead can dominate memory, making radix compression or packed static representations valuable.
• Persistence and concurrency require explicit snapshot, ownership, and consistency choices; an in-memory class is only the core algorithm.
• Hash tables and sorted arrays remain better when queries are exact, data is small, or the vocabulary changes mainly through batch rebuilds.

The trie earns its place when the product asks a prefix-shaped question often enough. Once normalization, ranking, memory, and updates are treated as first-class design inputs, it becomes more than a textbook tree: it becomes a deliberate search index with understandable costs.