Tries
Quick reference
| insert(word) | O(L) |
| search(word) | O(L) |
| startsWith(prefix) | O(L) |
| Total space, all inserted words | — |
Imagine a dictionary organized letter by letter instead of alphabetically on a page. Every word that starts with "ca" shares the same first two branches (c, then a). The words split apart only where they actually differ. "cat" and "car" share the c-a path and split at the third letter. A trie (short for reTRIEval, usually said "try") is this exact shape, built for strings. Every path from the root spells out a prefix. Any two words that share a prefix share the same path for as long as they agree.
This shared-path structure is the whole point. To ask "does any stored word start with 'ca'" does not need a check of every stored word one at a time. The question is only this: does the path c, then a, exist in the tree? If it does, every word down that branch starts with "ca", whether there are two of them or two thousand.
The node
structure TrieNode:
// one entry per character that is present, not one slot per possible character
children: map from character -> TrieNode
isEndOfWord: boolean // true only if some inserted word ends exactly at this node
structure Trie:
root: TrieNode (empty children, isEndOfWord = false) // the root represents the empty prefixinsert — walk or create, one character at a time — O(L)
function insert(trie, word):
node = trie.root
for ch in word:
if ch not in node.children:
node.children[ch] = new TrieNode()
node = node.children[ch]
node.isEndOfWord = true // mark the END of the path, not every node along itsearch — exact word, must end exactly here — O(L)
function search(trie, word):
node = trie.root
for ch in word:
if ch not in node.children:
return false // the path does not exist: the word was never inserted
node = node.children[ch]
return node.isEndOfWord // the path exists, but it is a real match only if a word ends HEREstartsWith — prefix only, path existing is enough — O(L)
function startsWith(trie, prefix):
node = trie.root
for ch in prefix:
if ch not in node.children:
return false
node = node.children[ch]
return true // to reach the end of the path is the whole answerL is the length of the word or prefix that you insert or check, not the number of words already stored. insert, search, and startsWith all cost O(L), whether the trie holds ten words or ten million, because each one is a walk down a single path, one character per step. A hash set gives O(L) average for exact search too (to hash a string still costs one pass over its characters). But a hash set cannot answer startsWith at all without a scan of every stored string to check which ones begin with the prefix. This is the real advantage of the trie. It is not faster at the thing a hash set already does. It does a thing that a hash set structurally cannot do.
| Operation | Time | Space | Why |
|---|---|---|---|
| insert(word) | O(L) | O(L) worst case | It walks or creates exactly one node per character of the word. A new word with no shared prefix creates L new nodes. |
| search(word) | O(L) | O(1) | This is one walk down the path spelled out by the word, then one isEndOfWord check. |
| startsWith(prefix) | O(L) | O(1) | This is the same walk as search. The only difference is which question is asked once the walk ends. |
| Total space, all inserted words | — | O(total characters) | The worst case (no shared prefixes at all) is one node per character across every word. Real text shares prefixes often, so actual usage is well below that ceiling. |
search vs. startsWith — the classic mix-up
If the path for "car" exists in a trie that has "card" stored, this does not mean that "car" itself was ever inserted as a word. To walk the path only proves that "car" is a valid prefix of something. search("car") must fail here unless "car" was inserted separately and its isEndOfWord flag was set. This one distinction (the path exists versus the path ends in a real word) is the one to get exactly right. Almost every trie bug comes from a blur of this distinction.
Forgetting to set isEndOfWord
Every character of the word gets a node, so the path is walked or created correctly. But then search() on that exact word still returns false, because nothing marked the last node as a real word ending. A fully built path is necessary but not sufficient. The flag on the final node is what search actually reads.
Empty string as input
The loop body never runs for an empty string, so node stays at trie.root the whole time. insert("") should mark the root itself as isEndOfWord = true (the empty string was "inserted"). search("") should then return true. Code that assumes every word touches at least one child node handles this wrong with no crash. It gives the wrong answer for the one input that never enters the loop.
Character-set assumptions baked into the structure
A 26-slot array is faster and uses less memory than a map when the input really is guaranteed to be lowercase only. But when uppercase letters, digits, spaces, or Unicode characters appear, an index by (char - 'a') either writes to the wrong slot or throws on a negative or out-of-range index. A children map has no such ceiling. It costs a little more per node, but it never has to know the alphabet in advance.
Sign in to mark problems done — progress syncs across devices.