Trie

#How does it work?

A trie (prefix tree) stores words letter by letter. Each edge stands for a letter, and the path from the root down to a node spells a prefix.

Words with a common prefix share the same path: for "car" and "cart" the c-a-r nodes are stored once. Nodes carry an end-of-word flag so you know where a word stops.

Lookup time depends on the length of the word, not on how many words the trie holds. That makes prefix queries such as autocomplete very fast.

#Try it yourself

#Basic operations

insert(word)

Follows the word's letters from the root, creates the missing nodes and marks the last node as the end of a word.

search(word)

Follows the letters; returns true if the path never breaks and the last node ends a word.

startsWith(prefix)

Only checks that the path exists; true if at least one word starts with the prefix.

delete(word)

Clears the end-of-word flag and removes nodes no other word needs.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

from typing import Dict, Optional


class Node:
    def __init__(self) -> None:
        self.children: Dict[str, "Node"] = {}
        self.is_word = False  # a word ends at this node


class Trie:
    def __init__(self) -> None:
        self._root = Node()

    def insert(self, word: str) -> None:
        node = self._root
        for c in word:
            node = node.children.setdefault(c, Node())
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

    def _walk(self, text: str) -> Optional[Node]:
        """Follows the letters; None if the path breaks off."""
        node = self._root
        for c in text:
            node = node.children.get(c)
            if node is None:
                return None
        return node


trie = Trie()
for word in ["cat", "car", "cart", "dog"]:
    trie.insert(word)

show = lambda b: "true" if b else "false"
print(show(trie.search("car")))      # true
print(show(trie.search("ca")))       # false: only a prefix
print(show(trie.starts_with("ca")))  # true
print(show(trie.search("do")))       # false

#Complexity

L is the length of the word (or prefix). Keeping children in a 26-element array makes each step O(1) but costs memory; a hash map saves memory with O(1) average steps.

#When to use it?

Autocomplete, spell checking, word games (Boggle, crosswords), longest-prefix matching in IP routing tables and searching many words in one text (Aho-Corasick) are all built on tries.

#Practice

Log in to answer questions and save your progress.