LearnAbout

Tries

On this page
Quick reference
insert(word)O(L)
search(word)O(L)
startsWith(prefix)O(L)
Total space, all inserted words—
The Idea

Picture a dictionary organized letter by letter instead of alphabetically on a page. Every word starting with "ca" shares the same first two branches — c, then a — and only splits apart where the words actually differ: "cat" and "car" share the c-a path and diverge at the third letter. A trie (short for reTRIEval, usually said "try") is exactly that shape, built for strings: every path from the root spells out a prefix, and any two words sharing a prefix share the same path for as long as they agree.

That shared-path structure is the whole point. Asking "does any stored word start with 'ca'" doesn't require checking every stored word one at a time — it's just: 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.

A trie node looks like Binary Trees' Node with one change scaled up: instead of two fixed slots (left, right), it has one slot per possible next character. Same branching idea — a node points to more nodes — just no longer capped at two children.
Build It
The node
structure TrieNode:
    // one entry per character actually 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 prefix
insert — 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 it
search — 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          // path doesn't exist at all — word was never inserted
        node = node.children[ch]
    return node.isEndOfWord       // path exists, but only a real match if a word ends HERE
startsWith — 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                   // just reaching the end of the path is the whole answer
search and startsWith are the same walk with one different last line: search asks "is node.isEndOfWord true," startsWith asks nothing more than "did I make it here at all." Confusing which question each one answers is the single most common trie bug — see Break It.
Know It

L is the length of the word or prefix being inserted or checked — not the number of words already stored. insert, search, and startsWith all cost O(L) regardless of whether the trie holds ten words or ten million, because each one is just a walk down a single path, one character per step. A hash set gives O(L) average for exact search too — hashing a string still costs one pass over its characters — but a hash set cannot answer startsWith at all without scanning every stored string to check which ones happen to begin with the prefix. That's the trie's real advantage: it isn't faster at the thing a hash set already does, it does a thing a hash set structurally can't.

OperationTimeSpaceWhy
insert(word)O(L)O(L) worst caseWalks or creates exactly one node per character of the word; a brand-new word with no shared prefix creates L new nodes.
search(word)O(L)O(1)One walk down the path spelled out by word, then a single isEndOfWord check.
startsWith(prefix)O(L)O(1)Identical walk to search — the only difference is which question gets asked once the walk ends.
Total space, all inserted words—O(total characters)Worst case (no shared prefixes at all) is one node per character across every word. Real text shares prefixes constantly, so actual usage runs well under that ceiling.
Break It

search vs. startsWith — the classic mix-up

code checks only "does the path exist" when it needed "does a word end exactly here", or the reverse

The path for "car" existing in a trie that has "card" stored does NOT mean "car" itself was ever inserted as a word — walking the path only proves "car" is a valid prefix of something. search("car") must fail here unless "car" was separately inserted and its isEndOfWord flag set. This single distinction — path exists vs. path ends in a real word — is the one to get exactly right; almost every trie bug traces back to blurring it.

Forgetting to set isEndOfWord

insert() builds the whole character path but the final line never runs, or runs on the wrong node

Every character of the word gets a node, walking or creating the path correctly — and then search() on that exact word still returns false, because nothing ever marked the last node as a real word ending. The path being fully built is necessary but not sufficient; the flag on the final node is what search actually reads.

Empty string as input

insert("") or search("") — a word or query with zero characters

The loop body never runs for an empty string, so node stays at trie.root the entire 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 will mishandle this without a crash — it'll just silently give the wrong answer for the one input that never enters the loop.

Character-set assumptions baked into the structure

children is implemented as a fixed-size array (say, 26 slots for lowercase a-z) instead of a map

A 26-slot array is faster and uses less memory than a map when the input really is guaranteed lowercase-only — but the moment uppercase letters, digits, spaces, or Unicode characters show up, indexing 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.

Use It
Implement Trie (Prefix Tree)
insert / search / startsWith from Build It, verbatim — this is the reference exercise for the structure itself.
Medium
Design Add and Search Words Data Structure
search() from Build It, but a '.' character means "try every child at this position" — branch into all of node.children instead of one, same DFS-over-a-tree shape as Binary Trees.
Medium
Longest Word in Dictionary
insert() every word, then DFS from the root but only step into a child whose isEndOfWord is already true — a word only counts if every prefix that builds it was also inserted as a complete word.
Medium
Replace Words
insert() every root word into a trie; for each word in the sentence, walk down the trie until isEndOfWord is hit (the shortest matching root) or the path runs out (no root — keep the original word).
Medium
Map Sum Pairs
insert() as usual but store a value at each word's end node; sum(prefix) walks to the end of the prefix's path, then DFS's the subtree beneath it summing every isEndOfWord value found.
Medium
Search Suggestions System
insert() every product; for each growing prefix of the search word, walk to that prefix's node then DFS its subtree collecting complete words, keeping the 3 lexicographically smallest.
Medium
Index Pairs of a String
insert() every word into a trie; for each starting index in text, walk the trie as far as characters keep matching, recording [start, current] every time isEndOfWord is true along the way.
Easy
Camelcase Matching
Not a trie build, but the same discipline as walking one — for each query, walk pattern and word together: every pattern character must appear in order, and every skipped word character must be lowercase.
Medium