Skip to content
Essay · Data Structures

When to use a trie

When to use a trie: when your questions are about prefixes, not whole keys. Here is how it compares with a hash set and a sorted array, with memory and operation counts for a 100,000 word dictionary.

By Vishy11 min readPublished · 16 Nov 2026

Knowing when to use a trie comes down to one question: do you ask about prefixes? If you only test whether whole keys exist, a hash set is smaller and faster. If you need every key starting with some text, or must stop a search the moment no key can match, a trie earns its memory.

What is a trie and how does it work?

A trie is a tree in which every edge carries one character, so each path from the root spells a prefix, and a flag on a node says that a complete word ends there. Words that begin the same way share their first nodes instead of storing them again.

The framing I use is shared track. A hash set sells every word its own ticket, and each ticket is a complete, independent string. A trie lays one stretch of railway for car, card, care and cart, and only splits the line at the point where the destinations differ. Anything that happens on the shared stretch happens once. That is the entire idea, and every strength and weakness of the structure follows from it: you pay in nodes, and you gain the ability to stand at any station on the line and ask what is reachable from here.

Here is a minimal version in Python, using a dictionary of children per node.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def _walk(self, text):
        node = self.root
        for ch in text:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def contains(self, word):
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

Insert and lookup both take O(m) time, where m is the length of the key, and neither depends on how many words are stored. That sounds like a victory over a hash set until you remember that hashing a string also reads all m characters. A hash set lookup on strings is O(m) too; the O(1) you were taught assumes the key has a fixed small size. So for exact membership the two are asymptotically the same, and the hash set has far better constants. I cover the reasons behind those constants in why is my hash map slow, and the underlying mechanics in load factor and collisions.

The difference shows up in the one operation the hash set cannot do. After _walk('ca') you hold a pointer to a node that represents everything beginning with ca. You can ask whether anything continues from there, enumerate it, or keep walking one character at a time without ever restarting from the beginning. A hash set has no notion of "the words that start with this", because hashing destroys the similarity between neighbouring keys on purpose.

When should you use a trie instead of a hash set?

Use a trie when the questions you ask are about prefixes: which stored keys start with this text, does any stored key start with this text, or what is the longest stored key that begins this input. If every question is "is this exact string present", use a hash set and move on.

In practice I look for three signals.

  • Repeated prefix queries. Autocomplete, type-ahead search, command palettes, spell suggestions. The user types one character at a time, and each keystroke extends the previous prefix by one. A trie lets you hold the current node and advance one edge per keystroke, which is O(1) work per key press before you collect results.
  • Search that needs early termination. If you are generating candidate strings (tracing paths in a letter grid, building words from a rack of tiles) and want to abandon a branch the instant no dictionary word can start with the current partial string, you need a cheap prefix test that you can carry along. The trie node you are standing on is that test.
  • Ordered or grouped enumeration. Visiting children in alphabetical order yields all keys in sorted order, and a subtree is exactly the set of keys sharing a prefix. Grouping by shared start, such as longest common prefix across many strings, falls out naturally.

The signals against a trie are equally concrete. The dictionary is small (a few hundred words, where a linear scan is already instant). The queries are one-off, so you would build the structure and throw it away. Or the alphabet is huge and the keys are sparse, so most nodes would hold a single child and you would be paying a full node for every character.

How much does a trie really cost compared with a hash set?

A trie usually costs ten to fifty times the memory of a hash set holding the same words, and in exchange it turns a prefix query from a scan of everything into a walk proportional to the answer. Whether that exchange is good depends on the numbers, so here are some.

Take a dictionary of 100,000 words with an average length of 8 characters. That is 800,000 characters in total. English-like word lists share a lot of prefixes, so a trie over them ends up with roughly 300,000 nodes (an estimate; your list will vary, but the ratio of two to three characters per node is typical). Now the user types pre and we want all matches. Suppose 400 words start with it.

  • Hash set. There is no prefix lookup, so we scan all 100,000 words and test startswith on each. That is 100,000 checks, each looking at up to 3 characters. In a compiled language that is around a millisecond; in Python it is more like 10 to 20 ms. Per keystroke.
  • Trie. Three steps to reach the node for pre, then a depth-first walk of its subtree. If those 400 words occupy about 1,500 nodes below that point, we visit about 1,500 nodes. That is about 65 times fewer operations than the scan.

Multiply by a typing session. A user types 10 characters while you re-query each time. The scan does about 1,000,000 checks; the trie does 10 cheap steps plus a few thousand node visits. If a server handles 1,000 such sessions a second, that is a billion checks against a few million node visits. That is the difference between a machine that is busy and one that is idle.

Now the bill. A node with a fixed array of 26 child pointers costs 26 times 8 bytes plus a flag, about 216 bytes. Times 300,000 nodes, that is around 65 MB. A hash set of 100,000 short strings needs a few megabytes. If you instead use a hash map per node, as in the Python code above, the overhead grows: an empty dict in CPython is already tens of bytes and a dict holding one key is around 180 bytes, so you can easily pass 60 MB and often much more. The trie in this example is ten to twenty times larger than the set, and that is before you consider cache behaviour: every step is a pointer chase to a node that may live anywhere in memory, so a cold walk of 1,500 nodes can cost on the order of 100 microseconds on its own.

ApproachPrefix query (400 matches, 100k words)Approx. memoryInsertBest when
Hash setScan all: about 100,000 checksA few MBO(m) averageExact membership only
Sorted array + binary searchAbout 17 comparisons, then read 400 resultsA few MBO(n) shiftStatic dictionary
Trie, array of 26 children3 steps, then about 1,500 node visitsAbout 65 MBO(m)Dynamic data, small alphabet, pruning search
Trie, hash map childrenSame visits, slower constants60 MB or more in PythonO(m)Large alphabet, sparse keys
Compressed (radix) trieSimilar, fewer nodesCloser to the setO(m), fiddlyProduction prefix indexes

Is a sorted array better than a trie for prefix search?

For a dictionary that does not change, very often yes. A sorted array answers a prefix query with a binary search plus a linear read of the matches, and it does so in a fraction of the memory, which is a fact people forget because the trie is the more famous answer.

Here is how it works. Sort the 100,000 words once. To find everything starting with pre, binary search for the first word that is not smaller than pre, which takes about 17 comparisons (log base 2 of 100,000 is just under 17), each looking at a few characters. Then read forward while words still start with pre. That is 17 comparisons plus 400 reads, compared with the trie's 1,500 node visits, and the reads are sequential memory, which the CPU loves. In my experience the sorted array wins on raw speed for static data in most languages, and the margin is large once you count cache misses.

So why does the trie survive? Two reasons. First, mutation: inserting into the middle of a sorted array of 100,000 entries moves about 50,000 pointers on average, while a trie insert touches m nodes. If words arrive constantly, the array is the wrong tool (a balanced tree or skip list would fix that, at which point you are in the same memory range as the trie). Second, and more important for interviews and for search code, the trie lets you carry state. In a backtracking search you hold a node pointer and advance it in O(1) as you extend the candidate. With a sorted array you would restart a binary search at every step, or maintain a pair of narrowing indices, which is doable but clumsy. The trie's strength is not that it is the fastest way to answer one prefix query. It is that a prefix becomes a thing you can hold in your hand and step forward.

Which interview problems actually need a trie?

The honest list is short: implementing the structure itself, multi-word grid search, autocomplete systems, and a few bitwise problems where the keys are binary numbers. Most string problems that look like they want a trie are solved more cheaply with a hash map or sliding window, so check that first.

The one that makes the structure indispensable is the multi-word grid search. You are given a small board of letters and a list of words, and you must report which words can be traced by moving between adjacent cells without reusing a cell. The naive approach runs a separate depth-first search for each word. With 1,000 words on a 4 by 4 board, that is 1,000 independent searches, each starting from up to 16 cells and branching up to 3 ways per step after the first. Almost all of that work is repeated, because 40 different words might begin with the same three letters and each search retraces them.

With a trie, you insert all 1,000 words, then run one search from each of the 16 cells while carrying the current trie node. When the next letter on the board has no child under the current node, you stop immediately, because no word could possibly continue. One pass explores every word at once and abandons dead prefixes early. This is the textbook case of the shared-track idea: the search shares the track the words share.

The other cases are smaller variations. A system that suggests the top few completions stores a count at each node. Replacing words in a sentence by their shortest known root walks the trie until it hits a word flag. And in the maximum XOR of two numbers problem the trie is binary, each node has two children (bit 0 or bit 1), and you greedily walk the opposite bit at each level, which gives O(32) work per number regardless of how many numbers you stored. That last one is a good reminder that the alphabet does not have to be letters; the same shape works for any key you can read one symbol at a time.

What does not need a trie: checking duplicates (contains duplicate is a set), counting anagram groups (a sorted key in a hash map), or substring search (that is the territory of rolling hashes and automata, not prefix trees). A trie indexes prefixes of many keys, not substrings of one text, and mixing those two up is the most common wrong turn.

What mistakes make a trie slower than it should be?

The big ones are using it where a hash set would do, choosing a node layout that does not match the alphabet, and doing hidden string copying while collecting results. All three are easy to avoid once you know to look.

  • Confusing a prefix with a word. Without the end flag, a trie that contains card will claim to contain car. Keep contains and starts_with as two separate functions, as in the code above, because they check different things at the same node.
  • A 26-slot array for a huge alphabet. For lowercase English the array is fine and fast. For Unicode text it is absurd: most slots are empty, so use a hash map per node, or compress single-child chains into one edge labelled with a substring (a radix tree).
  • Rebuilding strings at every node. When enumerating matches, appending to a new string at each step copies up to m characters each time. Push characters onto one list, record a copy only when you hit a word flag, and pop on the way back. The trap is the same one described in why string concatenation in a loop is slow.
  • Recursing on long keys. Insert and search are loops; do not write them recursively. A 100,000 character key would blow the call stack for no benefit.
  • Building it for one query. Construction costs the total number of characters, 800,000 steps in the example. If you ask a single prefix question, one scan of the list is cheaper than building anything.
  • Forgetting memory is a budget. A trie that fits comfortably in a unit test can take hundreds of megabytes on real data. Estimate nodes times bytes per node before you commit, the way you would estimate any table size.

The deeper habit is the one I try to apply to every data structure choice: write down the exact queries first. If the list of queries has a prefix in it, the trie is a candidate and the sorted array is its main rival. If it does not, the trie is just an expensive hash set.

Frequently asked questions

Is trie lookup faster than a hash map lookup?

Not for exact membership. Both read every character of the key, so both are O(m), and the hash map is usually faster in practice because it touches fewer scattered memory locations. The trie only wins when the question involves a prefix.

How much memory does a trie use?

Expect roughly one node for every two to three characters in a typical English word list, and each node costs from tens to a couple of hundred bytes depending on the layout. For 100,000 words that is commonly 20 to 70 MB with simple nodes, against a few MB for a hash set, so compress single-child chains or use a sorted array if memory matters.

Should I use a trie for autocomplete in a real product?

For a small or fast-changing vocabulary, a trie with counts at the nodes is a reasonable choice. For a large static one, a sorted array or a compressed trie is usually leaner and just as quick, so measure both on your data before deciding. To get comfortable with the string problems where prefix thinking pays off, work through the exercises under strings.