On this page
Description
"How many stored words start with pre?" A basic trie would walk to the prefix's node and then count every word in the subtree below it - potentially the whole dictionary. Keeping the answer on the node itself, and updating it as words come and go, makes the question a walk and a read.
This skill keeps two counters on every node: how many words pass through it and how many end there. Each counter answers one of the two counting questions. Erasing mirrors inserting along the whole path, and overwritten values update the sums by their difference.
We'll go from simple to more technical:
- The pattern: pass and end counters, with insert and erase updating the whole path.
- A second flavor: Map Sum, with prefix sums that handle overwrites by adding the delta.
- Where per-prefix totals show up (suggestion ranking, hierarchical analytics, profilers).
- What breaks it: erasing only the end, mixing up pass and end, overwrites, absent words.
The approach
Java
class TrieNode {
TrieNode[] next = new TrieNode[26];
int pass; // words passing through this node (a prefix count)
int end; // words ending exactly here
}
void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.next[c - 'a'] == null) node.next[c - 'a'] = new TrieNode();
node = node.next[c - 'a'];
node.pass++; // every node on the path
}
node.end++; // only the last node
}
void erase(String word) { // word is known to be present
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.next[c - 'a'];
node.pass--; // undo the whole path, not just the end
}
node.end--;
}
int countWordsEqualTo(String w) { TrieNode n = find(w); return n == null ? 0 : n.end; }
int countWordsStartingWith(String p) { TrieNode n = find(p); return n == null ? 0 : n.pass; }
Python
class TrieNode:
def __init__(self):
self.next = {}
self.pass_count = 0 # words passing through this node (a prefix count)
self.end = 0 # words ending exactly here
def insert(word: str) -> None:
node = root
for c in word:
if c not in node.next:
node.next[c] = TrieNode()
node = node.next[c]
node.pass_count += 1 # every node on the path
node.end += 1 # only the last node
def erase(word: str) -> None: # word is known to be present
node = root
for c in word:
node = node.next[c]
node.pass_count -= 1 # undo the whole path, not just the end
node.end -= 1
def count_words_equal_to(w: str) -> int:
node = find(w)
return 0 if node is None else node.end
def count_words_starting_with(p: str) -> int:
node = find(p)
return 0 if node is None else node.pass_count
Two counters answer two different questions: pass counts every word whose path goes through the node (so it's the prefix count), end counts only words that stop there. Erase must mirror insert along the whole path - decrementing only end leaves every prefix count too high. With duplicates allowed, end is a count, not a boolean.
A second flavor: sums with overwrites
Map Sum: insert(key, val) sets a key's value (replacing any earlier value), and sum(prefix) returns the total value of keys with that prefix. Store a running sum on each node - and when a key is overwritten, add only the change:
Java
void insert(String key, int val) {
int delta = val - values.getOrDefault(key, 0); // an existing key only changes by the difference
values.put(key, val);
TrieNode node = root;
for (char c : key.toCharArray()) {
if (node.next[c - 'a'] == null) node.next[c - 'a'] = new TrieNode();
node = node.next[c - 'a'];
node.sum += delta; // every prefix of key sees the change
}
}
Python
def insert(key: str, val: int) -> None:
delta = val - values.get(key, 0) # an existing key only changes by the difference
values[key] = val
node = root
for c in key:
if c not in node.next:
node.next[c] = TrieNode()
node = node.next[c]
node.sum += delta # every prefix of key sees the change
Adding the full new value instead double-counts: insert("apple", 3), then insert("apple", 2) would make sum("ap") 5 instead of 2. A side map of current values supplies the old value.
Where you'll see it
Search-suggestion systems rank completions by counts stored on trie nodes; analytics over hierarchical keys (URL paths, file paths, product categories) keep per-prefix totals so "traffic under /api/v2" is a single lookup; memory profilers aggregate allocation sizes up a call-path trie.
Which tool for which job?
| You need | Use |
|---|---|
| How many words start with a prefix | a pass counter on every node |
| How many copies of an exact word | an end counter on the last node |
| The total value under a prefix, with overwrites | node sums plus a side map, adding val - old |
| The k-th word in sorted order | skip whole children by their pass counts |
| Top suggestions per prefix, fast | cache the top few on each node |
| A trie that lives through many erases | prune nodes whose pass count reaches 0 |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Erase decrements only end | prefix counts stay too high | decrement pass along the whole path |
| Using pass for exact counts | longer words are counted too | end for exact, pass for prefixes |
| Adding the full value on overwrite | apple=3, app=4, apple=2 gives sum("ap") 9 instead of 6 | add val - old |
| Erasing a word that isn't there | counts go negative | check it exists first |
| Never pruning | 191,231 nodes for 1,480 live words | delete a child when its pass count hits 0 |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. What's the difference between the pass and end counters?
Show answer
pass counts every word whose path goes through the node (the answer for "starts with this prefix"); end counts only words that stop exactly there (the answer for "equal to this word").
2. What goes wrong if erase decrements only the end counter?
Show answer
Every node on the erased word's path still counts it in pass, so countWordsStartingWith stays too high for all its prefixes.
3. In Map Sum, why add val - old rather than val when a key is inserted again?
Show answer
The old value is already included in the sums along the key's path. Adding the full new value leaves the old one in place too; adding the difference replaces it.
Key takeaways
- pass (prefix count) on every node of the path; end on the last node.
- Erase mirrors insert along the whole path.
- Sums with overwrites add the delta, using a side map of current values.
- Every prefix query is O(L): walk, then read a counter.