← Learn DSA · Lesson 8 of 9
Tries
A tree where the path spells the key, so shared prefixes are stored once.
The idea
A trie stores keys in the shape of the tree rather than inside the nodes. To
look up "car", you start at the root and follow the edge labelled c, then
a, then r. The key is the path.
Two consequences follow immediately.
Shared prefixes are stored once. "car", "card" and "care" occupy one chain of three nodes plus two leaves. A hash set of the same three words stores all thirteen characters, three times over.
Prefix questions become cheap. "Which words start with 'car'?" is a walk of three edges followed by whatever hangs below — a hash set cannot answer it at all without scanning every key it holds. That is the one thing a trie does that nothing else does well, and it is the reason to reach for one.
Lookup costs O(length of the key), independent of how many keys are stored. That sounds better than a hash map's O(1) until you notice the hash also has to read the whole key to hash it — the two are closer than the notation suggests, and the hash map usually wins on constants and memory.
The walkthrough below uses a binary trie: the same idea with an alphabet of two, where each level is one bit of the key. It is a real and widely used variant — XOR and maximum-pair problems run on it — and it is small enough to see whole.
Walkthrough
A binary trie, one bit per level. The path taken *is* the key — watch the walk turn left or right according to the next bit rather than comparing values.
What it costs
- time
- O(k) for insert, lookup, or prefix search, where k is the key length
- space
- O(total characters stored), which shared prefixes reduce
Independent of how many keys are held — a million words cost the same per lookup as ten. The space constant is the weak point: a node per character with a child slot per alphabet letter is heavy, which is why real implementations compress chains.
When to reach for it
- You need prefix queries: autocomplete, "all words starting with…", longest common prefix.
- Your keys share long prefixes, so storing each in full would repeat the same characters many times.
- You need keys in sorted order for free — an in-order walk of a trie yields exactly that.
- Bitwise problems about maximum or minimum XOR pairs, which are a binary trie in disguise.
Rather than the obvious alternative
A hash set or hash map
The right default for exact-match lookup: simpler, less memory, and faster in practice. It cannot answer prefix questions at all without scanning every key, which is the only reason to give it up.
A sorted array with binary search
It does support prefix queries, in O(log n · k), and uses far less memory. Prefer it when the set is static; prefer the trie when keys are inserted and removed as you go.
How to spot it
- The problem says "prefix", "starts with", "autocomplete", or "dictionary".
- You are matching many keys against one text, or one key against many stored keys.
- The input is a set of words with heavy overlap.
- The problem is about XOR of pairs, which becomes a walk down a binary trie.
Where it goes wrong
Forgetting the end-of-word marker
Reaching a node does not mean a word ends there. Without an explicit flag, "car" is reported as present in a trie that only holds "card".
Confusing "prefix exists" with "word exists"
These are different queries and most trie bugs are one answering as the other. Decide which you need before writing the walk.
A child array per node, for a large alphabet
26 slots per node is already wasteful; Unicode is impossible. Use a map per node, or compress chains, once the alphabet grows.
Try it
Two short checks. They run the same way the practice problems do — write the function, press Run.
Given two equal-length arrays of character codes, return how many leading positions match — the depth their paths would share in a trie.
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| sharedPrefix([99,97,114], [99,97,116]) | partial overlap | 2 | — |
| sharedPrefix([1,2], [3,4]) | no overlap | 0 | — |
| sharedPrefix([5,6,7], [5,6,7]) | identical | 3 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Hints
Stuck? Hints open one at a time, each giving a little more away.
2 hints left
Build it
The problems above are one function each. These assemble the same ideas into a working thing across several files.