The Core Idea
A Tree Where Every Edge Is a Letter
A trie (pronounced 'try,' short for retrieval tree) is a tree specialized for storing strings, where each edge from a node to its child represents a single character, and a path from the root down to a marked node spells out a complete stored word. The critical insight is that words sharing a common prefix literally share the same initial path through the tree — 'cat,' 'car,' and 'card' all share the 'c' → 'a' path before branching apart at the third character.
This shared-prefix structure is what makes tries so effective for anything involving prefixes: instead of comparing a search term against every stored word individually (as you'd need to with a plain list), you walk the trie one character at a time, and the tree structure itself immediately tells you which words are even possible matches.
💡 Memory Trick
Picture a hotel corridor where each door represents one letter, and rooms only exist where a valid word ends. Walking down the 'C' door, then the 'A' door, then the 'T' door leads you to a room marked 'end of word: CAT.' If you instead take 'C' then 'A' then 'R', you're now in a different room ('end of word: CAR'), but notice you walked through the exact same first two doors as you did for CAT — that shared corridor is exactly what a trie exploits.
The Core Operations
Insert and Search, One Character at a Time
1
Insert — O(m), where m is the word's length
Starting at the root, for each character in the word, check if a child edge for that character already exists. If it does, follow it. If it doesn't, create a new child node for that character and follow it. After processing the last character, mark that final node as 'end of word.'
Example: inserting 'car' after 'cat' already exists reuses the 'c' and 'a' nodes, only creating a new node for 'r'.
2
Search — O(m)
Starting at the root, for each character in the target word, follow the corresponding child edge if it exists. If at any point the needed edge doesn't exist, the word is definitely not in the trie. If you successfully consume every character AND the final node is marked 'end of word,' the word is present.
3
Prefix Search — O(p), where p is the prefix's length
To check whether ANY stored word starts with a given prefix, simply walk the trie following the prefix's characters — if you can successfully walk the entire prefix without hitting a missing edge, at least one word with that prefix exists (regardless of whether the prefix itself is marked as a complete word).
Why It Beats Alternatives for Prefix Tasks
Independent of How Many Words Are Stored
The critical performance property is that trie search and insertion depend only on the length of the word (m) being searched or inserted — not on how many total words are stored in the trie. Searching for a 5-letter word takes the same 5 steps whether the trie holds 100 words or 100 million words, which is a much stronger guarantee than a hash table's average O(1) or a sorted list's O(log n), both of which at least implicitly depend on how many items are stored.
This is exactly why tries power autocomplete (walk to the end of what's typed so far, then explore every path below that point to suggest completions), spell-check (a failed search immediately identifies a misspelling), and IP routing tables (matching the longest valid prefix of an IP address). The trade-off is memory: a trie with many short, dissimilar words can use considerably more memory than a hash table storing the same words, since every distinct character path requires its own node.
🖥️ Applied Scenario
You're building a search bar autocomplete feature that must suggest all possible word completions as the user types each letter, from a dictionary of 500,000 words.
1
You reject scanning all 500,000 words on every keystroke to find ones starting with the typed prefix — that would be O(n) per keystroke, needlessly slow and repeated on every letter typed.
2
You store the dictionary in a trie instead, so walking down to the node representing the currently-typed prefix takes only as many steps as characters typed so far — independent of dictionary size.
3
Once at that prefix's node, you explore every path beneath it (a small local subtree, not the whole trie) to gather all valid completions, since every word below that node shares the typed prefix by construction.
4
Conclusion: the trie's shared-prefix structure means each keystroke only costs work proportional to what's been typed, not to the size of the entire dictionary — exactly the scaling behavior autocomplete needs.
📌 Exam Application
Exam questions often ask you to insert a small list of words into a trie and draw the resulting structure, explicitly showing which nodes are shared between words and which are marked 'end of word.' You may also be asked to explain why trie search/insert complexity depends on word length rather than the number of stored words — the expected answer references walking one character-edge per step, regardless of what else is stored elsewhere in the tree.
⚠️ Most Common Tries Mistakes
The most common mistake is forgetting to distinguish 'a valid prefix exists in the trie' from 'a complete word exists in the trie' — successfully walking to a node doesn't mean a word ends there unless that node is explicitly marked 'end of word'; searching for 'car' when only 'card' was ever inserted would walk successfully to the 'r' node but must still fail, since that node isn't marked as a complete word. Another frequent error is assuming tries are always more memory-efficient than hash tables — for large sets of long, dissimilar words with little shared prefix structure, a trie can actually use considerably more memory per stored word.
✓ Quick Self-Test
Can you insert the words 'cat,' 'car,' 'card,' and 'dog' into a trie by hand and draw the resulting structure, marking which nodes are 'end of word'? Can you explain why trie operations are O(word length) rather than depending on the total number of stored words?
Next Lesson
Balanced Binary Trees
→
← All Data Structures Lessons