AlgoScope

Trie

A trie stores words by their letters, one node per letter, so every path from the root spells a prefix and words that begin the same way share the same nodes. Inserting a word follows the existing path as far as it goes and only creates nodes for the part that is new. Looking a word up is the same walk: a missing child means the word is not there, and even a full match only counts if the last node was marked as the end of a word. Because the walk depends only on the word's length, a trie answers prefix questions, autocomplete above all, faster than any sorted list.

The player

Words with prefix ca.•carttdog

The trie holds car, cart, cat, dog. Which of them start with "ca"? Walk the prefix, then every terminal node below the node reached is one answer: autocomplete in two phases.

How it runs, step by step

  1. The trie holds car, cart, cat, dog. Which of them start with "ca"? Walk the prefix, then every terminal node below the node reached is one answer: autocomplete in two phases.

    Words with prefix ca.

  2. Letter 'c': follow it.

    Follow c.

  3. Letter 'a': follow it.

    Follow a.

  4. Terminal node reached below the prefix: "car" is answer 1.

    Found car.

  5. Terminal node reached below the prefix: "cart" is answer 2.

    Found cart.

  6. Terminal node reached below the prefix: "cat" is answer 3.

    Found cat.

  7. 3 words start with "ca": car, cart, cat. Walking the prefix is O(length). Collecting costs the size of the subtree.

    3 words found.

The code

Trie, in Python

class Node:
    def __init__(self):
        self.children = {}
        self.terminal = False

def insert(root, word):
    node = root
    for c in word:
        node = node.children.setdefault(c, Node())    # follow, or create the missing child
    node.terminal = True                              # this node ends a word

def search(root, word):
    node = root
    for c in word:
        node = node.children.get(c)
        if node is None: return False                 # a missing child: not stored
    return node.terminal                              # a prefix of a word is not a word

def with_prefix(root, prefix):
    node = root
    for c in prefix:
        node = node.children.get(c)
        if node is None: return []
    out = []
    def collect(n, sofar):                            # DFS below the prefix node
        if n.terminal: out.append(sofar)
        for c, child in n.children.items(): collect(child, sofar + c)
    collect(node, prefix)
    return out

def delete(root, word):
    path = [root]
    for c in word:
        child = path[-1].children.get(c)
        if child is None: return False                # not stored
        path.append(child)
    if not path[-1].terminal: return False            # only a prefix
    path[-1].terminal = False                         # unmark the word end
    for i in reversed(range(len(word))):              # prune upward
        node = path[i + 1]
        if not node.children and not node.terminal:
            del path[i].children[word[i]]
        else:
            break
    return True

Trie, in JavaScript

class Node { constructor() { this.children = new Map(); this.terminal = false; } }

function insert(root, word) {
  let node = root;
  for (const c of word) {
    if (!node.children.has(c)) node.children.set(c, new Node());   // follow, or create the missing child
    node = node.children.get(c);
  }
  node.terminal = true;                                      // this node ends a word
}

function search(root, word) {
  let node = root;
  for (const c of word) {
    node = node.children.get(c);
    if (node === undefined) return false;                    // a missing child: not stored
  }
  return node.terminal;                                      // a prefix of a word is not a word
}

function withPrefix(root, prefix) {
  let node = root;
  for (const c of prefix) {
    node = node.children.get(c);
    if (node === undefined) return [];
  }
  const out = [];
  const collect = (n, sofar) => {                            // DFS below the prefix node
    if (n.terminal) out.push(sofar);
    for (const [c, child] of n.children) collect(child, sofar + c);
  };
  collect(node, prefix);
  return out;
}

function deleteWord(root, word) {                            // `delete` is a reserved word in JS
  const path = [root];
  for (const c of word) {
    const child = path.at(-1).children.get(c);
    if (child === undefined) return false;                   // not stored
    path.push(child);
  }
  if (!path.at(-1).terminal) return false;                   // only a prefix
  path.at(-1).terminal = false;                              // unmark the word end
  for (let i = word.length - 1; i >= 0; i--) {               // prune upward
    const node = path[i + 1];
    if (node.children.size === 0 && !node.terminal) path[i].children.delete(word[i]);
    else break;
  }
  return true;
}

Trie, in Kotlin

class Node { val children = mutableMapOf<Char, Node>(); var terminal = false }

fun insert(root: Node, word: String) {
    var node = root
    for (c in word) node = node.children.getOrPut(c) { Node() }   // follow, or create the missing child
    node.terminal = true                                             // this node ends a word
}

fun search(root: Node, word: String): Boolean {
    var node = root
    for (c in word) node = node.children[c] ?: return false         // a missing child: not stored
    return node.terminal                                             // a prefix of a word is not a word
}

fun withPrefix(root: Node, prefix: String): List<String> {
    var node = root
    for (c in prefix) node = node.children[c] ?: return emptyList()
    val out = mutableListOf<String>()
    fun collect(n: Node, sofar: String) {                            // DFS below the prefix node
        if (n.terminal) out += sofar
        for ((c, child) in n.children) collect(child, sofar + c)
    }
    collect(node, prefix)
    return out
}

fun delete(root: Node, word: String): Boolean {
    val path = mutableListOf(root)
    for (c in word) path += path.last().children[c] ?: return false   // not stored
    if (!path.last().terminal) return false                           // only a prefix
    path.last().terminal = false                                      // unmark the word end
    for (i in word.indices.reversed()) {                              // prune upward
        val node = path[i + 1]
        if (node.children.isEmpty() && !node.terminal) path[i].children.remove(word[i]) else break
    }
    return true
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • One node per letter. A path from the root is a prefix. Shared prefixes share nodes.
  • Insert follows existing children and creates the missing ones. The last node is marked terminal.
  • Search fails on a missing child, and a full match without a terminal mark is only a prefix.

Where this is used

Lucene and Elasticsearch term indexSearch

Lucene holds the index of its term dictionary in memory as a finite state transducer, a trie over the terms with shared prefixes stored once and identical tails merged as well, mapping a prefix to the offset of the on-disk block that holds those terms. A prefix query or a completion suggester walks that structure down to the prefix and enumerates what hangs below it. This is why foo* is cheap in Elasticsearch and *foo is not: only one of the two is a walk from the root, and the other has to touch every term.

Ethereum account stateBlockchain

Accounts live in a Merkle Patricia trie keyed by the hash of the address, and each contract's storage is a second trie of the same kind keyed by the hash of the slot number, so a path down either one is the nibbles of that key and every node is named by the hash of its own contents. One root hash therefore commits to the whole state, and a light client can be handed just the nodes along a single path as proof of what a balance is. Because an update only changes nodes on one path, applying a transaction rehashes a few dozen nodes rather than the entire state.

Scrabble move generationGames

Engines such as Quackle keep the lexicon as a DAWG, a trie whose identical suffix subtrees have been merged into one, which shrinks it by roughly an order of magnitude and lets the whole dictionary stay in memory. Move generation walks the graph a letter at a time and abandons a branch the moment no tile on the rack matches a child, so the overwhelming majority of impossible placements are never enumerated at all. The GADDAG variant indexes each word from every one of its letters outward, so a play can be grown in both directions from a tile already on the board.

Keypad predictive textText input

On a phone keypad each digit stands for three or four letters, so a typed sequence is ambiguous until the dictionary rules the alternatives out. T9-style input keeps a trie of the dictionary and, on each keypress, advances only the live paths whose next letter sits on that key, so the surviving set shrinks with every digit and the suggestion is whatever is left. Filtering a word list instead would re-read the dictionary on every keypress. The trie only has to extend the frontier it is already holding.

Why it works this way

Why a terminal flag, instead of just checking for a leaf

The obvious shortcut is to treat a childless node as a word end, and it breaks the moment one stored word is a prefix of another. Insert card and then car: car creates no nodes at all, it only sets a flag on a node that already has a child, so a leaf test would report card and miss car entirely. The converse fails too once deletes are in play, since a delete that clears the flag without pruning leaves a childless node that no longer ends any word. Nothing about a node's shape says whether a word ends there, which is why the flag is stored on the node.

Deleting a word cannot simply delete its nodes

car and card share their first three nodes, so tearing out card's path would take car with it. The safe order is to clear the terminal flag first, then walk back up removing a node only while it has no children and is not itself terminal, stopping at the first node that fails that test. Clearing the flag and pruning nothing is still correct, because search trusts the flag and nothing else, but a trie under a long insert-and-delete workload then never gives any memory back.

Is a trie actually faster than a hash map?

For a plain lookup, usually not. Hashing a string already reads every character of it, so both are O(length), but the hash map does one probe into a contiguous table while the trie does a pointer chase per character, each one a likely cache miss. A node that holds a fixed array of 26 children also costs 208 bytes of pointers on a 64-bit machine, or half that on a JVM with compressed references, whether those children exist or not, and near the leaves almost all of them are empty. The trie earns its place only when you need prefixes or sorted order, which a hash map cannot give you at any price.

Walking to the prefix is the cheap part

Reaching the prefix node costs one step per character, but listing the words below it costs a step per node in that entire subtree, so a one-letter prefix over a dictionary means walking most of the trie. Production autocomplete does not pay that at query time: it stores the best few completions, ranked by frequency, on each node, so the answer is read straight off the node the walk lands on. The lookup was never the expensive part of a suggester. The ranking is.

Read more

Next up

DP on a Grid

Cheapest path

Next lesson: DP on a Grid