Trie Implementation and Advanced Operations
HardCounts at every node
Problem
Extend a trie to also count how many words equal a given word and how many words start with a given prefix, plus erase words.
Store counts at each node so you can tally exact words and prefixes, and remove them.
The idea
Keep two counters per node: how many words end here, and how many words pass through here. Then countWordsEqualTo and countWordsStartingWith are single lookups, and erase just decrements both counters along the path instead of unlinking nodes.
The trick
- `endsWith` counts words finishing at this node; `prefixCount` counts words passing through.
- Erase by decrementing counters, not by deleting nodes — far simpler and still correct.
- Both queries stay O(word length).
Step 1 of 5. The trie already stores "cat" and "car". Insert "cap" — walk down, creating nodes only where they're missing.
Descend one node per letter.
1insert(word) {2 let node = this.root;3 for (const ch of word) {4 if (!node.children.has(ch)) node.children.set(ch, new TrieNode());5 node = node.children.get(ch);6 }7 node.isEnd = true;8}Input
- nodes
- 5, 4 edges
Memory
- matched
- —
Output
- created
- —
- inserted
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- insert 'apple' x2; countWordsEqualTo 'apple'
- Output:
- 2
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.