Tries — Prefix Trees for Fast String Lookups

The Concept

A trie (also called a prefix tree) stores strings by decomposing them into individual characters. Each edge in the tree represents one character, so every path from the root spells out a prefix — or, when a special end-of-word flag is set on the terminal node, a complete word.

The key insight: strings that share a prefix share the same path from the root. The words "car", "card", "care", and "careful" all travel through the same c → a → r chain before diverging. That shared structure is what makes prefix queries cheap.

Structure of a trie node

children maps the next character to its subtree. is_word marks whether the path from the root to this node spells a complete stored word. Without that flag you could not distinguish "car" from "card" — both share the same c → a → r path; the flag on the r node settles it.

Core Operations

insert — O(L)

Walk the word one character at a time. At each step, if the required child does not exist, create it. After the last character, set is_word = True. The cost is exactly L node visits for a word of length L, regardless of how many other words are already stored.

search — O(L)

Walk the word character by character. If any character is missing from children, the word was never inserted — return False. If you reach the last character successfully, return node.is_word. This distinguishes "car" (stored) from "ca" (not stored, even if words beginning with "ca" exist).

startsWith — O(L)

Same walk as search, but stop at the end of the prefix and return True without checking is_word. Even if no complete word ends at that node, the prefix itself exists in the trie.

Code Implementation

Complexity Analysis

L is the length of the word or prefix being processed. Every operation is independent of the number of words already in the trie.

Applications

Autocomplete. Navigate to the node representing the typed prefix, then collect every word reachable in the subtree below that node. That subtree contains exactly the words that start with the prefix — nothing more, nothing less.

Longest common prefix. Walk down from the root while every visited node has exactly one child and is_word is False. The moment you hit a branch (more than one child) or a word-end marker, the path you have walked is the longest prefix shared by all inserted words.

Spell checking and dictionary lookup. A trie holding the entire dictionary answers "is this a valid word?" in O(word length) — no hash collisions, no binary searching.

IP routing. Network routers use a variant of the trie (a Patricia/radix trie) to match destination addresses against prefix-based routing tables in O(address length) time.

Interactive Labs

Watch how the trie builds character-by-character as words are inserted, and how search follows the same path without extra allocations.

See the autocomplete traversal in action: navigate to the prefix node, then gather all words in its subtree.

The longest-common-prefix query walks down while there is only one branch — it stops as soon as the path forks or a word ends.

Key Takeaways

• One character per edge. Shared prefixes cost no extra space — the trie compresses them naturally.
• O(L) for everything. Insert, search, and startsWith are all proportional to the word or prefix length — not the number of stored words. A trie holding a million words searches just as fast as one holding ten.
• is_word flag is essential. It is what turns a prefix tree into a word store. Without it, you cannot distinguish a complete word from a prefix that happens to have words extending beyond it.
• Autocomplete is a subtree traversal. Once you reach the prefix node, any DFS/BFS of its subtree yields all completions. The trie does in O(prefix length + output size) what a sorted array would need O(n) to scan for.
• Space trade-off. In the worst case (no shared prefixes), a trie uses more memory than a hash set. In practice, natural language has enormous prefix overlap, so tries are memory-competitive and operationally superior for prefix queries.