Tries (Prefix Trees)

What is a Trie?

A trie stores strings as paths of characters from a shared root. Words with the same prefix travel through the same early nodes.

You need maps or child arrays, strings, and tree traversal. The short version is: follow one character edge at a time and mark the nodes where complete words end.

The Core Idea: Share Prefix Paths

In Insert and Search 'apple', the words apple and app share the path a -> p -> p. The path then ends for app and continues through l -> e for apple.

How can one node mean both a complete word and the start of a longer word? It stores an end marker separately from its children.

It is like a filing cabinet organized one letter at a time. Words beginning with the same letters stay in the same drawers until their letters differ.

How Insert Reuses a Prefix

The Rule You Keep True

After consuming the first i characters, the current node represents exactly that length-i prefix. Following a missing child proves no stored word has that prefix.

The stopping rule changes by query:

• Exact search requires both the full path and an end marker.
• Prefix search requires only the full path.
• Wildcard search branches across several children for wildcard positions.
• Board word search combines trie prefixes with DFS over neighboring cells.

Design Add and Search Words is the one that usually trips us up. A wildcard cannot follow one known child, so the search must try every child at that trie node and succeed if any branch matches the rest of the pattern.

Picking the Right Shape

From Rule to Code

1. Start at the root before reading a word or query.
2. For each character, create its child during insertion or fail if it is missing during lookup.
3. Move to that child and continue with the next character.
4. Mark the final node during insertion.
5. For exact search, check the end marker; for prefix search, the completed path is enough.

Insertion and lookup take O(L) time for word length L, with memory proportional to the number of created prefix nodes.