Tries

No. 16 · SVG · Letter treeprefix tree · insert · search · starts_with · autocomplete

Drag across the tree. Click it, then use ← → to step and Space to play.

A trie stores strings one character per level, so words with the same beginning share a path: "car", "cat" and "cart" all hang off the same c → a. Each node maps characters to children and carries a flag for "a word ends here". Looking a word up never compares it to other words; it just walks its L characters down from the root, so insert, search and starts_with all cost O(L), no matter how many words are stored.

FIG. 16 · The board from page 6, where each gate holds one character and the root is the empty string. A thick ink ring means end_of_word: a whole word stops at that gate. The word being processed runs along the channel below, with its current letter in red. Red marks the gate the code is at, and ringed gates and lit grooves are the path walked so far. Callout: A root.

Step 1 / 1
READY
Walked
Created
Words
Result
CodeTrie.insert
def insert(self, word):
    cur = self.root
    for c in word:
        if c not in cur.children:
            cur.children[c] = TrieNode()
        cur = cur.children[c]
    cur.end_of_word = True

Examples

Trie + DFS · LeetCode 211

Words: dad, bad, mad, bed. search(".ed"): a dot matches any letter, so at the root the search tries every child. 'd' has no 'e' below it, so it backtracks and tries 'b', where b → e → d ends a word. Answer: True. Trigger: "word dictionary".

O(L) without dotsO(26^dots · L) worsteach dot can fan out to every child
Trie · LeetCode 14

["flower", "flow", "flight"]. Insert them all; the common prefix is the path down from the root while every node has exactly one child and no word has ended. It splits after "fl" (o / i). Answer: "fl". Trigger: "prefix".

O(total chars) timeO(total chars) spacebuild once; the walk is at most the shortest string

Time and space

OperationTimeSpaceWhy
insert(word)O(L)up to L new nodesOne node per character, created only where the path doesn't exist yet.
search(word), starts_with(prefix)O(L)O(1)Walk L edges; independent of how many words are stored.
Whole trie—O(total characters)At most one node per character inserted; shared prefixes are stored once.
Hash set of words (page 9)O(L) to hashO(total characters)Fast for exact lookups, but "which words start with ca?" means checking every word.

Why end_of_word?

The path c → a exists because "car" and "cat" were inserted, but "ca" was not. Without the flag, search("ca") would wrongly say yes. The flag is the only difference between search and starts_with.

Trigger words: when the problem wants a trie

Prefixes

  • prefix
  • starts with
  • autocomplete

Every word below a node shares the prefix spelled by the path to it.

Dictionaries

  • word dictionary
  • wildcard search
  • word search in a grid

Many lookups against the same set of words.

Template

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_word = False

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

    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.end_of_word = True

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

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

    def _walk(self, s):            # follow s, or None if it breaks
        cur = self.root
        for c in s:
            if c not in cur.children:
                return None
            cur = cur.children[c]
        return cur