Implement Trie (Prefix Tree): Insert, Search, and startsWith from Scratch
Build a trie from scratch — insert words character by character, then search and prefix-check by walking the tree. JavaScript code, a worked trace, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A trie is what you reach for the moment "which words start with ca?" becomes a hot path. A hash set of words can tell you whether card exists, but it can't answer prefix questions without scanning every key. A trie stores words as paths through a tree of characters, so a prefix query is just a short walk down that tree.
This problem asks you to build the structure itself: a class with three methods — insert, search, and startsWith. Once you see how the three share the exact same walk, the whole thing collapses into about thirty lines.
Master this and you've built the engine behind autocomplete, spell-check, IP routing tables, and half the harder string problems on any interview list.
The problem
Implement a Trie class supporting three operations:
insert(word)— addwordto the trie.search(word)— returntrueonly if the exactwordwas inserted earlier.startsWith(prefix)— returntrueif any inserted word begins withprefix.
The distinction between the last two is the whole point: search needs a complete word, startsWith only needs the path to exist.
insert("apple")
insert("app")
search("app") -> true // "app" was inserted as a full word
search("appl") -> false // the path exists, but "appl" was never a word
startsWith("ap") -> true // "apple" and "app" both begin with "ap"That search("appl") -> false while startsWith("appl") -> true case is where naive implementations break. The path a → p → p → l exists in the tree, but no one ever marked l as the end of a word.
The brute force baseline
Store every inserted word in an array (or set) and answer queries by scanning.
class Trie {
constructor() {
this.words = [];
}
insert(word) {
this.words.push(word);
}
search(word) {
return this.words.includes(word);
}
startsWith(prefix) {
return this.words.some((w) => w.startsWith(prefix));
}
}This is correct but slow where it matters. With n stored words averaging length L, every search and startsWith is O(n · L) — you touch each stored word and compare characters. A dictionary with 100,000 words makes each prefix check a 100,000-word linear scan. Prefix queries are supposed to be the fast operation, and here they're the slowest.
The waste is structural: apple and app share the prefix app, but the array stores those three letters twice and compares them separately every query. A trie stores that shared prefix once.
The key insight
Model each word as a path down a tree where every edge is one character. Words that share a prefix share the top of their path and only branch where they differ.
A node needs just two things:
children— a map from a character to the next node.isEndOfWord— a flag marking that some inserted word ends here.
That flag is the trick that separates search from startsWith. Both walk the same edges; search additionally demands that the final node has isEndOfWord === true, while startsWith is satisfied the moment the walk completes without hitting a missing child.
The root is a sentinel — it holds no character and just anchors every path. All three methods start there and follow one child per character.
The optimal solution
Here is the exact structure the visualizer teaches: a TrieNode holding children and isEndOfWord, and a Trie whose three methods all share the same character walk.
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let curr = this.root;
for (let char of word) {
if (!curr.children[char]) {
curr.children[char] = new TrieNode();
}
curr = curr.children[char];
}
curr.isEndOfWord = true;
}
search(word) {
let curr = this.root;
for (let char of word) {
if (!curr.children[char]) {
return false;
}
curr = curr.children[char];
}
return curr.isEndOfWord;
}
startsWith(prefix) {
let curr = this.root;
for (let char of prefix) {
if (!curr.children[char]) {
return false;
}
curr = curr.children[char];
}
return true;
}
}Read the three methods side by side and the pattern jumps out. Every one starts curr = this.root and loops character by character.
insertcreates a node when a child is missing, then keeps walking, and finally setsisEndOfWord = true.searchbails out false when a child is missing, and at the end returnscurr.isEndOfWord.startsWithis identical tosearchexcept the final line isreturn true— it doesn't care whether the node is a word ending.
The only differences are what you do when a child is absent (create vs. return false) and what you check at the end (mark, read the flag, or nothing).
Walkthrough
Trace insert("cat"), insert("car"), then search("car") and search("care"). The shared prefix ca matters here.
After the two inserts, the tree looks like this — t and r both hang off the shared ca spine, and both are marked as word endings:
root
└─ c
└─ a
├─ t* (isEndOfWord)
└─ r* (isEndOfWord)Now the two searches, walking one character per row from the root:
| Operation | char | curr before | child exists? | curr after | Result |
|---|---|---|---|---|---|
| search("car") | c | root | yes | c | continue |
| search("car") | a | c | yes | a | continue |
| search("car") | r | a | yes | r | end reached |
| search("car") | — | r | — | — | r.isEndOfWord = true → true |
| search("care") | c | root | yes | c | continue |
| search("care") | a | c | yes | a | continue |
| search("care") | r | a | yes | r | continue |
| search("care") | e | r | no | — | missing child → false |
search("car") walks c → a → r, finds the node marked as a word end, and returns true. search("care") follows the same three edges but then asks r for a child e, finds none, and returns false immediately — it never even reaches the isEndOfWord check. That early exit on a missing child is what makes tries fast.
Complexity
Let L be the length of the word or prefix, and n the number of inserted words.
| Operation | Time | Space | Why |
|---|---|---|---|
| insert | O(L) | O(L) | one node per new character, at most L nodes created |
| search | O(L) | O(1) | walk L edges, constant work per character |
| startsWith | O(L) | O(1) | same walk, no allocation |
| Total structure | — | O(total characters) | shared prefixes stored once |
Every operation is O(L) — proportional to the length of the string you pass in, and completely independent of how many words the trie already holds. That's the payoff over the array baseline's O(n · L) scans: a prefix check on a million-word trie costs the same as on a ten-word trie.
Space is bounded by the total number of characters across all inserted words, minus the savings from shared prefixes. apple and app together use five nodes, not eight.
Common mistakes
- Forgetting
isEndOfWord. Without the flag,searchcan't tell a real word from a prefix. Insertingapplewould makesearch("appl")wrongly returntruebecause the path exists. - Making
searchandstartsWithidentical. They share the walk but not the ending.searchreturnscurr.isEndOfWord;startsWithreturnstrue. Copy-pasting one into the other silently breaks the distinction. - Creating nodes during
search.insertallocates a node for a missing child;searchandstartsWithmust return false instead. Auto-creating on read pollutes the trie with phantom paths that make later searches lie. - Not re-anchoring
currat the root. Each method must start fresh atthis.root. Reusing a stale pointer from a previous call walks into the middle of the tree. - Assuming a lowercase alphabet. The
children = {}map handles any character. A fixed-size 26-slot array is a valid optimization, but only if the input is guaranteed to be lowercasea–z.
Where this pattern shows up next
The trie is the backbone of any prefix-driven feature: autocomplete dropdowns, dictionary word-break solvers, longest-common-prefix queries, and the "add and search word" variant where . matches any character (a small DFS tweak on this same tree). Once you're comfortable creating nodes on insert and short-circuiting on a missing child, those all read as variations of the three methods here.
You can also step through the trie interactively to watch nodes get created on insert and the traversal path light up character by character during search.
FAQ
What is the difference between search and startsWith in a trie?
Both walk the tree one character at a time from the root and return false the instant a required child node is missing. The difference is only what happens when the walk completes: search returns curr.isEndOfWord, demanding that the final node was explicitly marked as the end of an inserted word, while startsWith returns true unconditionally because it only needs the prefix path to exist. That's why search("appl") is false but startsWith("appl") is true after inserting apple — the path exists, but no word ends at l.
Why is a trie faster than storing words in a hash set?
A hash set answers exact-match queries in O(L) too, but it cannot answer prefix questions without scanning every stored key, making startsWith an O(n · L) operation over n words. A trie stores shared prefixes as a shared path, so any prefix query is just an O(L) walk down that path regardless of how many words the trie holds. The trie also deduplicates storage: apple and app share their first three nodes instead of storing those letters twice.
What does isEndOfWord do and why is it necessary?
isEndOfWord is a boolean on each node that marks whether some inserted word ends exactly at that node. It's necessary because a trie stores paths, not words — after inserting apple, every prefix (a, ap, app, appl) exists as a path even though none of them is a real word. Without the flag, search would have no way to distinguish a complete inserted word from an intermediate character along a longer word's path, and it would return true for prefixes that were never inserted.
What is the time complexity of trie operations?
All three operations — insert, search, and startsWith — run in O(L) time, where L is the length of the word or prefix being processed. Crucially, this is independent of n, the number of words already stored, because you only ever walk one path of length L. insert uses O(L) extra space in the worst case (one new node per character), while search and startsWith use O(1) extra space since they only move a single pointer. The whole structure uses space proportional to the total number of characters across all words, reduced by whatever prefixes are shared.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.