Tries

Problem

You hold a collection of words and must answer questions about prefixes: is this a stored word, does any word start with this, which words start with this, or which of these many words can be spelled on a board. A hash set answers the first question in O(length) but cannot answer the others without scanning every word, because a hash destroys the order of the characters. A sorted list with binary search can answer prefix queries, but inserting is slow. A trie answers every one of them by following one character at a time.

Intuition

Write the words car, card, care, cat, do, dog on a page. Many start the same way: car, card and care share the prefix car, and car and cat share ca. A trie draws each shared prefix once. Starting at an empty root, each edge carries one letter, and a word is the path from the root to a node that is marked "a word ends here". The 6 words have 19 letters in total, but the trie needs only 9 letter nodes, because the shared prefixes collapse.

The mark matters. The node for ca exists because car and cat pass through it, but ca is not a stored word. Without the end mark you could not tell a word from a mere prefix. This is the most common bug in a first trie: answering search with "I found the path" instead of "I found the path and the end mark is set".

Each node is one letter. Amber nodes end a stored word; the root is empty. The diagram scrolls sideways on a narrow screen.

Mechanics

The invariant

The path from the root to any node spells a prefix of at least one stored word, and every prefix of every stored word has exactly one node. A node's children are keyed by the next letter, so two different words can only share a node if they share the whole path leading to it. An end flag on a node means "the path to here is itself a word".

Insert, search and prefix

Insert walks the word one letter at a time, creating the child when it is missing, and sets the end flag on the last node. Search walks the same way but never creates; it fails if a letter has no child, and otherwise answers with the end flag of the last node. Starts with is search without the final check: reaching the node at all is the answer. All three cost one step per letter, O(L) for a word of length L, independent of how many words are stored.

Correctness follows from the invariant. A word is stored exactly when its path exists and its last node is marked; a prefix is present exactly when its path exists. Because each node has at most one child per letter, the walk is deterministic, with no choices to try.

Wildcards and the board search

A dot that matches any letter turns the deterministic walk into a search: at a dot, try every child and succeed if any branch succeeds. That is a depth-first search on the trie, and its worst case is every node at that depth. For a grid of letters the roles reverse. Instead of testing each word separately, build a trie of all the words and run a depth-first search from each cell that carries the trie node along: step to a neighbour only if the current node has a child for that neighbour's letter. The moment no stored word continues the path, the search backs out, so one walk over the board serves every word at once. Removing a leaf from the trie after its word is found keeps the search from rediscovering the same word and shrinks the work as the board is mined out.

Green letters found a child; the amber letter is the first with none. Reaching the end of the query is not enough for a word: the node must also carry the end mark.

Worked example

The trie holds car, card, care, cat, do, dog: 9 letter nodes for 19 letters of text.

ca is a prefix but not a word, which is exactly why the end mark exists. The prefix car leads to a node with three words below it: car, card, care.

The pattern ca. follows c and a and then branches at the dot. The pattern ..g opens with two dots, so it branches at the first two levels and enters 5 nodes before it finds dog. A pattern with a dot early costs more than one with a dot late.

Implementation

class TrieNode:
    __slots__ = ("children", "end")

    def __init__(self):
        self.children = {}          # letter -> TrieNode
        self.end = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.end = True

    def _walk(self, text):
        node = self.root
        for ch in text:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.end

    def starts_with(self, prefix):
        return self._walk(prefix) is not None


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def add_word(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.end = True

    def search(self, pattern):
        def match(node, i):
            if i == len(pattern):
                return node.end
            if pattern[i] == ".":
                return any(match(child, i + 1) for child in node.children.values())
            child = node.children.get(pattern[i])
            return child is not None and match(child, i + 1)

        return match(self.root, 0)


def find_words(board, words):
    root = TrieNode()
    for word in words:
        node = root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.end = word                  # store the word itself, so no path rebuilding is needed

    rows, cols = len(board), len(board[0])
    found = []

    def dfs(r, c, parent):
        ch = board[r][c]
        node = parent.children[ch]
        if node.end:
            found.append(node.end)
            node.end = False             # report each word once
        board[r][c] = "#"                # mark visited in place
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in node.children:
                dfs(nr, nc, node)
        board[r][c] = ch
        if not node.children and not node.end:
            del parent.children[ch]      # prune exhausted branches

    for r in range(rows):
        for c in range(cols):
            if board[r][c] in root.children:
                dfs(r, c, root)
    return found

A dictionary of children is the idiomatic Python choice: it handles any alphabet and only stores the letters that exist. In find_words the end flag holds the word itself, which doubles as the "is a word" test because any non-empty string is truthy.

Variations and edge cases

• Fixed alphabet. For lowercase letters a list of 26 slots per node is faster than a dictionary but uses 26 pointers per node even when most are empty.
• Counts per node. Store how many words pass through each node to answer "how many words have this prefix" in O(L), or to delete a word by decrementing.
• Reversed words. Insert each word backwards to match suffixes; pairs-that-form-a-palindrome problems combine a trie of reversed words with a check on the leftover part.
• Tokens other than letters. The edges can be directory names, so an in-memory file system is a trie whose nodes hold file contents.
• Edge cases: the empty string (marks the root, so give the root an end flag if empty words are allowed), a word that is a prefix of another, a word inserted twice, a query longer than every stored word, and a board with repeated letters, where the in-place visited mark keeps a path from reusing a cell.

Complexity and tradeoffs

• Time: insert, search and prefix are O(L) for a word of length L, independent of the number of stored words. A wildcard query is O(L) in the best case and can visit every node in the worst case, which is why the dots in the example above matter. The board search is O(cells × 4^L) in the worst case for a word length L, but the trie prunes almost all of that in practice.
• Space: at most one node per letter of input, here 9 nodes against 19 letters, and far fewer when prefixes are shared. The cost is the per-node overhead of a dictionary or a 26-slot array, which can exceed the cost of storing the strings directly.
• Baseline. A hash set answers exact membership in O(L) with less memory. Scanning every word for a prefix is O(words × L). A sorted array with binary search finds a prefix in O(L log n) but cannot take new words cheaply.
• When it fails. When only exact lookups are needed, a set is simpler and smaller. When the words are few and the prefixes short, the trie's overhead is not paid back. For huge dictionaries a compressed trie or a finite state transducer saves memory by merging single-child chains.

Problems

The first two home problems are the basic trie and its wildcard extension; the third is the board search that makes pruning pay off. The two Hard problems from the Grind list reuse the structure for palindromes and file paths.

Medium

• 208. Implement Trie (Prefix Tree) Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Each node maps a character to a child and flags whether a word ends there, so lookups cost the length of the word.
• 211. Design Add and Search Words Data Structure Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Store the words in a trie and branch into every child at a dot, so each wildcard search is a depth-first walk.

Hard

• 212. Word Search II Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Put every word into one trie and run a single board DFS guided by it, pruning trie branches whose words have all been found.
• 336. Palindrome Pairs Grind 169
  For each word, split it every possible way; when one part is a palindrome, look up the reverse of the other part in a map of words.
• 588. Design In-Memory File System Grind 169
  A trie of path components, where each node is a directory or a file with content, makes ls, mkdir and file access path walks.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 139. Word Break Medium
• 2707. Extra Characters in a String Medium
• 140. Word Break II Hard

Connections

A trie is a tree whose children are keyed by a letter, so the traversals of the depth-first page apply directly, and a dictionary of children is the hash map of the hash-maps page placed at every node. The word-break problems ask whether a string splits into dictionary words; a trie speeds up their inner loop by scanning forward through the string one letter at a time and stopping when the prefix dies, instead of slicing and hashing substrings. The board search is backtracking with a pruning oracle, which returns in the backtracking pages later on.

Check yourself

References

• Fredkin, "Trie memory", Communications of the ACM 3(9), 1960: the paper that named the structure.
• de la Briandais, "File searching using variable length keys", Proc. Western Joint Computer Conference, 1959: the first description of the structure.
• Knuth, The Art of Computer Programming, volume 3, section 6.3: digital searching.
• Sedgewick and Wayne, Algorithms, section 5.2: tries and ternary search tries.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 12 problems: radix trees.
• Skiena, The Algorithm Design Manual, the section on string data structures.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.