Overview
MediumPrefix tree · shared prefixes stored once
A trie stores words letter by letter along shared branches, so common beginnings are kept only once.
The idea
A trie stores strings character-by-character down a tree, so words sharing a prefix share a path. Lookups and prefix queries run in O(word length), independent of how many words exist.
Step 1 of 5. The trie already stores "cat" and "car". Insert "cap" — walk down, creating nodes only where they're missing.
1/5
Optimal
timeO(L) per opspaceO(total chars)
One edge per character.
1class TrieNode { children = new Map(); isEnd = false; }2let node = root;3for (const ch of word) {4 if (!node.children.has(ch)) node.children.set(ch, new TrieNode());5 node = node.children.get(ch);6}7node.isEnd = true;Input
- nodes
- 5, 4 edges
Memory
- matched
- —
Output
- created
- —
- inserted
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- insert "cat", "car"
- Output:
- c → a → {t, r}
- Explanation:
- The shared prefix "ca" is stored once. Adding "card" costs one more node, not four.
Example 2
- Input:
- startsWith("ca") vs search("ca")
- Output:
- true, false
- Explanation:
- Both walk the same two nodes; only search also checks the end-of-word flag.
Finished the walkthrough? Add it to your streak.