Tries: The Core Idea

A search box holds 100,000 product names. The user types p, then pr, then pre, and after every keystroke you must answer: does anything start with this? With a plain list, each answer scans every name. On a real 100,000-word list that is about 5 milliseconds per keystroke in Python — fine for one user, far too slow for a thousand users typing at once.

A hash set does not help. It answers "is prefix stored?" in one step, but it cannot answer "does anything start with pre?", because hashing pre tells you nothing about where prefix or press were stored. Hashing deliberately destroys the structure a prefix query needs.

A trie keeps that structure. It stores the words in a tree where the path from the root spells the word. Answering "does anything start with pre?" means walking three edges — p, r, e — whether the dictionary holds 10 words or 10 million. On the same 100,000-word list that answer takes about 1 microsecond.

The picture before the code

Think of the letter tabs on the side of a thick paper dictionary. To find words starting with ca, you open at the c tab, then you look only at the ca pages. You never read the d pages. Each letter you know narrows the search to a smaller part of the book.

How to recognise it

Four signals in the problem statement point at a trie:

• The word "prefix" appears. "Count words that begin with a given string." "Return every completion of what the user typed." "Find the shortest prefix that is unique."
• Autocomplete or search-as-you-type. Queries arrive one character at a time, and you must answer after each one.
• A whole dictionary tested against a board or a text. Word Search II gives you a letter grid and thousands of words. Searching for each word on its own repeats the same work thousands of times.
• Words share a lot of structure. car, card, care, careful share their first three letters. A trie stores those letters once.

The constraints give the same hint. A line like "up to 30,000 words, each at most 20 characters, and up to 30,000 queries" says the intended cost per query depends on the length of a word, not on the number of words. That is O(L) per operation, which is a trie.

One counter-signal matters just as much: if every query asks "is this exact word stored?", you do not need a trie. A set is simpler and far smaller. The section "When a set is the better answer" below puts numbers on that.

How it works

Build one by hand. Insert car, cart, cat and dog, in that order:

That is 8 nodes plus the root. Storing the four words as separate strings costs 3 + 4 + 3 + 3 = 13 characters. The saving is the shared prefix ca, held once instead of three times.

Now trace search("car"): from the root, follow c, then a, then r. All three edges exist, and node r has its flag set, so the answer is yes. search("ca") walks the first two edges and stops at node a. The path exists, but no word ends at a, so the answer is no. starts_with("ca") walks the same path and answers yes, because it does not look at the flag.

The invariant that makes this correct is simple: every node stands for exactly one string — the letters on the path from the root to it. Two words share a node exactly when they share that prefix. So walking a prefix lands on the only node that can lead to words with that prefix, and everything below that node is the complete set of matching words. Nothing outside it can match, so nothing outside it is ever read.

The end-of-word flag is not optional. Node r is both the end of car and a step on the way to cart. Without the flag, car and ca look the same — both end at a node that exists. Every prefix of every stored word would be reported as a stored word.

The forms it takes

The walk is always the same. What changes is what each node remembers:

The node layout also comes in two forms:

The template

1class TrieNode:2    """One node: children keyed by character, plus an end-of-word flag."""34    def __init__(self) -> None:5        self.children: dict[str, TrieNode] = {}6        self.is_word = False789class Trie:10    """Prefix tree with insert, exact search and prefix search."""1112    def __init__(self) -> None:13        self.root = TrieNode()1415    def insert(self, word: str) -> None:16        node = self.root17        for ch in word:18            if ch not in node.children:19                node.children[ch] = TrieNode()   # create only when missing20            node = node.children[ch]21        node.is_word = True                      # after the loop, not inside it2223    def _walk(self, prefix: str) -> TrieNode | None:24        """Return the node where prefix ends, or None if the path breaks."""25        node = self.root26        for ch in prefix:27            node = node.children.get(ch)28            if node is None:29                return None30        return node3132    def search(self, word: str) -> bool:33        node = self._walk(word)34        return node is not None and node.is_word3536    def starts_with(self, prefix: str) -> bool:37        return self._walk(prefix) is not None

Read it line by line:

• TrieNode has two fields. children maps a character to the next node. is_word says whether a stored word ends here. There is no char field: the character lives on the edge, in the dictionary key.
• insert is walk-or-create. At each character, go down the edge if it exists, otherwise make it first. The flag is set once, after the loop, on the node reached by the last character.
• _walk follows the prefix and returns the node where it ends, or None the moment an edge is missing. There is no point reading further once the path breaks.
• search and starts_with share that walk. They differ by one condition: search also needs node.is_word. Writing them next to each other makes the difference impossible to forget.

Complexity

Every operation walks one node per character and does constant work at each — one dictionary lookup and one pointer move.

The missing term is the number of words. A trie of 10 words and a trie of 10 million words answer a 3-letter prefix query in the same 3 steps. That is the property you are paying for.

Space is O(S) in the worst case, one node per character when no prefixes are shared. Here is what that costs in practice. On a real list of 100,000 English words (958,719 characters, 9.6 letters on average), prefix sharing cut the node count to 396,747. But each Python node is an object plus a dictionary, and the whole trie took about 98 MB. A set of the same strings took about 9 MB. The trie is roughly ten times larger.

When a set is the better answer

The first row is a tie on paper. Both are O(L), because hashing a string reads all L characters — people forget this when they call a hash lookup "O(1)". The set wins on memory and on constant factors.

Before you build a trie, ask three questions:

1. Does any query involve a prefix, not a whole word? If not, use a set.
2. Will the same trie serve many queries? Building costs O(S), the same as one scan of every word. One query never repays that.
3. Is the alphabet reasonable? With a dict of children any alphabet works, but memory grows with every distinct character.

Where it goes wrong

Trie bugs rarely crash. They return plausible answers, which is why they survive testing.

• No end-of-word flag. Insert cart, then search("ca") returns True. The code passes every starts_with test and fails search.
• The flag set inside the insert loop. Same symptom by a different road: inserting cart marks c, ca, car and cart as words.
• starts_with that checks the flag. Now starts_with("ca") is False even though cat is stored.
• A found word not cleared in Word Search II. A word reachable by two paths on the board is reported twice.
• Memory on a large alphabet. A fixed array of 256 slots per node for byte strings, or any array for Unicode, explodes. Use a dict of children.
• A trie where a set would do. More code, ten times the memory, and the interviewer will ask why.

One test catches the first three bugs at once: insert one word, then search for each of its proper prefixes. Every search must return False, and every starts_with must return True.