What Is a Trie? The Prefix Tree That Powers Autocomplete

You've used one today. The moment your browser finished 'javascript array methods' from 'java' and a half-typed prayer, something trie-shaped was in the system doing the work. Tries aren't exotic. They're just the data structure that's been quietly finishing your sentences for years while you took the credit.

What Is a Trie? The Name Gives It Away

A trie comes from the word "retrieval." Computer scientist Edward Fredkin coined the term in 1960 and apparently never anticipated sixty years of pronunciation arguments. Two camps exist: /ˈtriː/ (like "tree") and /ˈtraɪ/ (like "try"). The second usually wins in technical conversations because "a tree called a trie pronounced like tree" is a sentence that breaks people.

You'll also see it called a prefix tree. That's the clearer name. Use it if you want to avoid starting debates at standup.

Why a Tree? The Prefix Insight

When you store strings in a hash map, each string is independent. "cat" and "car" share nothing. If you want all words starting with "ca", you scan every key. That's O(n) regardless of how many words actually start with "ca." You're going through the entire bookshelf to find the cat section, even though you already know where the C's are.

The trie's core insight is that strings with common prefixes share their prefix in the data structure. "cat", "car", "card", and "care" all start with "c" and "a". In a trie, the "c" node and the "a" node each exist exactly once, no matter how many words share them. Every word with that prefix walks the same path down the tree.

This is why prefix queries are fast. Navigate to the node for "ca" and everything in the subtree below it is a word starting with "ca". No scanning. The structure encodes the answer.

That's also what makes tries show up in autocomplete engines, spell checkers, IP routing tables (where routers do longest prefix matching on addresses), and bioinformatics tools that search DNA sequences for matching patterns.

The Structure: Nodes, Children, and a Flag

A trie node holds two things:

A map from characters to child nodes
A boolean flag marking whether a complete word ends at this node

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end: bool = False

Some implementations replace the dictionary with an array of 26 slots, one per lowercase letter. That makes character lookup O(1) rather than average O(1), but wastes memory when the alphabet is sparse. For interview problems that constrain input to lowercase English letters, either works. For Unicode or arbitrary characters, use a dictionary.

The root node is empty. It has no character itself. Think of it as the lobby of the trie. Nothing lives there, but every operation starts there.

A Concrete Example: Building a Dictionary

Insert four words: "cat", "car", "card", "care".

SVG diagram of a trie containing cat, car, card, care, showing shared c and a nodes at the top, branching to t and r, with r further branching to d and e. Filled blue circles mark is_end nodes.

The "c" and "a" nodes are shared by all four words. The "r" node is shared by "car", "card", and "care". That sharing is where the space savings come from. In a hash map, you'd store four separate strings. In the trie, the common prefix "ca" is stored once.

Notice "r" is marked is_end = True because "car" is a valid word even though "card" and "care" extend beyond it. The flag doesn't stop traversal. It just marks that a word boundary exists here.

Search for all words starting with "car": traverse root → c → a → r in three steps. You're at the "r" node. Everything below it, plus the node itself if marked, is your answer. No other part of the trie is touched.

Three Operations, All O(m)

Every core trie operation runs in O(m) time, where m is the length of the word or prefix. That doesn't depend on how many words are in the trie. Which is a strange thing to type and have it be true.

Insert creates nodes as needed, one character at a time:

def insert(self, word: str) -> None:
    node = self.root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end = True

Search follows the same path and checks the end flag at the final node:

def search(self, word: str) -> bool:
    node = self.root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end

StartsWith is identical to search but skips the end flag:

def starts_with(self, prefix: str) -> bool:
    node = self.root
    for char in prefix:
        if char not in node.children:
            return False
        node = node.children[char]
    return True

starts_with("ca") returns True even though "ca" isn't a word in the dictionary. You successfully reached the node for "a". Whether a complete word ends there is irrelevant for a prefix check. That distinction matters when you implement LeetCode 208, which asks for both search and startsWith as separate methods.

The Space Trade-off

Worst case, storing n words of average length m costs O(n × m) space. Same as a hash map.

In practice, real word lists have massive prefix overlap. A 50,000-word English dictionary shares dozens of common roots. Words like "pre", "un", "com", "re" appear as prefixes thousands of times. Every shared character is a node you're not duplicating. Tries use less space than hash maps when your dataset has many common prefixes. They use more when it doesn't.

Gru's plan meme: 'Presented code challenge in interview / Didn't fall for the just-use-a-hashmap solution / Hashmap was the answer / Hashmap was the answer'

When you reach for a trie on sparse data and realize a hash map would've been fine.

There's also per-node overhead to factor in. Each TrieNode carries a dictionary and a boolean. In Python, a dictionary has non-trivial memory overhead even when nearly empty. For interviews, clarity matters more than memory micro-optimization, but if you're asked to compare the two structures on space, know that tries only win when prefix overlap is high.

Where tries clearly beat hash maps is on time for prefix operations. A hash map doing starts_with has to iterate all keys. A trie navigates directly to the prefix node. For datasets with k words matching a prefix, the trie costs O(p) to reach the prefix plus O(k × m) to enumerate matches. The hash map always costs O(n × m). When n is large and k is small, the trie wins by a lot.

For a direct comparison and when each structure is the right call, trie vs. hash map covers the trade-offs in detail.

When the Interview Reaches for a Trie

The clearest signal is a prefix query. If the problem involves checking whether any stored word begins with a given prefix, or retrieving all matches for a prefix, a hash map can't do it efficiently. A trie can.

Other patterns to watch for:

Autocomplete or suggestion systems. Store the word list in a trie and navigate by prefix.
Word search in a grid (LeetCode 212). A trie lets you prune DFS paths the moment you reach a node with no children matching the next character. Without a trie, you'd restart the search from scratch for every word.
Wildcard matching (LeetCode 211). A '.' can match any character. At a wildcard, branch into all children and recurse. The trie structure makes that DFS clean.
XOR maximization (LeetCode 421). Store numbers bit by bit in a binary trie (each node has a 0 branch and a 1 branch). To maximize XOR, greedily pick the opposing bit at each level.

LeetCode 208 is the starting point. Build it from scratch without notes. If you can wire up the TrieNode class and implement all three methods correctly in one pass, the harder problems follow naturally.

One piece of the trie that trips engineers in live interviews isn't the code. It's explaining the prefix-sharing insight out loud while you code. Those are two separate skills and only one of them gets trained on LeetCode. SpaceComplexity runs voice-based mock interviews where you code and narrate simultaneously, with rubric-based feedback on both dimensions.

Key Takeaways

A trie stores strings by sharing common prefixes. Each node holds one character. A path from root to an is_end node spells a complete word.
Insert, search, and startsWith all run in O(m) time where m is the string length, regardless of how many words are stored.
Tries beat hash maps on prefix queries. Hash maps win on exact lookups and sparse data without common prefixes.
Interview signals: autocomplete, prefix matching, word search in a grid, wildcard patterns, XOR maximization.
Build LeetCode 208 from scratch. That's the gate.