Trie Implementation

Description

Autocomplete must list every word starting with what the user has typed, from a dictionary of a million words, on every keystroke. A hash set answers "is this exact word there?" but has no idea which words start with "inte". A sorted list can binary-search for the range. A trie organizes the words by their prefixes directly.

This skill builds a trie: words as paths of characters, shared prefixes sharing nodes, and an end mark that separates "a word ends here" from "some word passes through". It also covers wildcard search, which branches at each "." and must still finish on an end mark.

We'll go from simple to more technical:

1. The pattern: insert, search and startsWith over a node per character.
2. A second flavor: wildcard search that tries every child at a ".".
3. Where tries run (autocomplete, spell checkers, IP routing, search-engine dictionaries).
4. What breaks it: no end-mark check, index math on other characters, wildcards, memory.

The approach

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    boolean isEnd;                                   // a complete word ends exactly here
}

void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        if (node.next[c - 'a'] == null) node.next[c - 'a'] = new TrieNode();
        node = node.next[c - 'a'];
    }
    node.isEnd = true;
}

TrieNode find(String s) {                            // the node where s's path ends, or null
    TrieNode node = root;
    for (char c : s.toCharArray()) {
        node = node.next[c - 'a'];
        if (node == null) return null;
    }
    return node;
}

boolean search(String word)       { TrieNode n = find(word); return n != null && n.isEnd; }
boolean startsWith(String prefix) { return find(prefix) != null; }

class TrieNode:
    def __init__(self):
        self.next = {}                               # letter -> TrieNode: any alphabet
        self.is_end = False                          # a complete word ends exactly here


def insert(word: str) -> None:
    node = root
    for c in word:
        if c not in node.next:
            node.next[c] = TrieNode()
        node = node.next[c]
    node.is_end = True


def find(s: str) -> TrieNode | None:                 # the node where s's path ends, or None
    node = root
    for c in s:
        node = node.next.get(c)
        if node is None:
            return None
    return node


def search(word: str) -> bool:
    node = find(word)
    return node is not None and node.is_end


def starts_with(prefix: str) -> bool:
    return find(prefix) is not None

Every word is a path; words with a common prefix share its nodes. Each operation walks at most L nodes - O(L), independent of the dictionary's size. The end mark is what separates the two questions: after inserting "carpet", startsWith("car") is true but search("car") is false - the path exists, but no word ends there. Returning find(word) != null from search is the classic bug.

A second flavor: wildcard search

"Does any stored word match b.d?" - where . stands for any letter - is a walk that branches at each wildcard:

boolean match(String word, int i, TrieNode node) {
    if (node == null) return false;
    if (i == word.length()) return node.isEnd;       // must end exactly at a word
    char c = word.charAt(i);
    if (c != '.') return match(word, i + 1, node.next[c - 'a']);
    for (TrieNode child : node.next) {               // '.' tries every existing child
        if (child != null && match(word, i + 1, child)) return true;
    }
    return false;
}

def match(word: str, i: int, node: TrieNode | None) -> bool:
    if node is None:
        return False
    if i == len(word):
        return node.is_end                           # must end exactly at a word
    c = word[i]
    if c != ".":
        return match(word, i + 1, node.next.get(c))
    return any(match(word, i + 1, child) for child in node.next.values())   # '.' tries every existing child

Letters follow one child; a . tries each child that exists. The search is bounded by the trie's size, but a pattern of all dots can visit every node of that length.

Where you'll see it

Search-box autocomplete, spell checkers, T9-style keypad lookup, and IP routers (a binary trie over address bits finds the longest matching network prefix) are tries. Search engines often store their term dictionaries as compressed tries or finite-state transducers (Lucene's FST) to answer prefix and fuzzy queries.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. After inserting only "carpet", what do search("car") and startsWith("car") return, and why?

2. Why does a trie operation cost O(L) regardless of how many words are stored?

3. In wildcard search, what must be true when the pattern runs out?

Key takeaways

• Words are paths; shared prefixes share nodes; operations are O(L).
• search needs the end mark; startsWith only needs the path.
• Wildcards branch over existing children and still need the end mark.
• Arrays for small alphabets, maps for large ones; radix tries compress long chains.