Counting prefixes and deleting words

Why this matters

Real tries need two features beyond insert and search. The first is a count: "how many stored words start with these letters?" A search box might say "12 results" before it shows any of them. The second is removal: a user deletes a word from a personal dictionary, or a system expires old entries. Both features are small in code, but each has traps that interviewers like to probe. A delete that removes too much breaks other words. A count that is not updated on delete reports numbers that are wrong. A duplicate insert that is counted twice gives an answer that is off by one.

This lesson adds both features in a careful order. You will see why a naive count is slow, how a pass counter fixes it, and why deleting a word is really a question about which nodes are still needed. Each step has a runnable program, and each program shows the output you should expect.

The naive count and why it is slow

Suppose you want to count the words with prefix "ca" in the trie from lesson one, which holds car, card, care and cat. The method you already know is to walk to the "ca" node, then count every word-end node below it with the depth-first search from lesson two. That gives the right answer: 4. But the cost is the size of the subtree under the prefix. If the prefix matches 100,000 words, you visit at least 100,000 nodes on every count request. For a search box that refreshes on every keystroke, that is too slow.

The better idea is to store the answer in advance. If every node knows how many words pass through it, then the count for any prefix is a single value. You only need to walk to the prefix node and read the number. The walk costs the length of the prefix, not the number of matches.

To keep these numbers correct, every insert has to update every node on the path. That is a small price. An insert already walks the path, so adding one more operation per node costs nothing extra in big-O terms.

The pass counter

Add one integer to each node. Call it pass, meaning "how many stored words pass through this node". A word passes through a node when that node lies on the path from the root to the word's final node. The root is on every word's path, but it is not a letter, so we will not count it.

When you insert a new word, add 1 to the pass of every node you walk through, from the first letter's node down to the last letter's node. When you reach the end, set the flag. After a set of inserts, the pass of a node equals the number of stored words that begin with the letters on its path.

Here is the trace for three inserts: car, card and cat. The table shows the pass value of each node after each insert.

Read the table by column. After car, the nodes c, a and r each have pass 1, because car passes through them. The d and t nodes do not exist yet, so they have no value. After card, the nodes c, a and r each have pass 2 and the new d node has pass 1. After cat, the c and a nodes have pass 3, because all three words start with c and a. The r node stays at 2, because cat does not pass through r. The t node has pass 1.

Now the answer to "how many words start with ca?" is the pass of the a node, which is 3. The answer to "how many start with car?" is the pass of the r node, which is 2. Both are one walk each.

A trie for car, card and cat, with the pass count written on each node

The diagram above shows the same numbers for the final state. Read each node's pass count as "words through this node". The word-end flags are not shown; they still matter for exact-word checks.

The code for insert with counts

The insert changes only one line from lesson one: the pass++ inside the loop.

void insert(const string& w) {
    Node* cur = root;
    for (char c : w) {
        int i = c - 'a';
        if (!cur->next[i]) cur->next[i] = new Node();
        cur = cur->next[i];
        cur->pass++;
    }
    cur->isEnd = true;
}

Notice that pass++ happens after the move, so it increments the child you just entered. Each node on the path is therefore incremented once, and the root is never incremented. If you increment before the move, you increment the wrong node, and every count is off by one letter.

The count for a prefix is read from the prefix's last node.

int countPrefix(const string& p) {
    Node* cur = root;
    for (char c : p) {
        cur = cur->next[c - 'a'];
        if (!cur) return 0;
    }
    return cur->pass;
}

For a prefix that is not in the trie, the walk fails and the answer is 0. For an empty prefix, the loop does nothing, and the code returns the root's pass. The root is never incremented, so it stays 0, which is wrong. The fix is to keep a separate total count, as the program later in this lesson does.

The duplicate trap

The pass counter counts insert calls, not distinct words. Insert "car" twice and the pass of every node on its path becomes 2, while only one word is stored. A count of "words that start with car" would say 2 when the true answer is 1. This trap is easy to fall into, and interviewers often add a duplicate on purpose.

The fix is to check before you insert. If the word is already present, return without changing anything. The check is a search, which costs O(L), the same as the insert itself. Then the count only increases when a new word is added.

The output below comes from a program that skips the check. It inserts "car" twice and prints the count, then shows a second bug.

count car after two inserts of car: 2

The correct answer is 1. The duplicate insert doubled the pass counts on the path. Every count below that path is now too high by the number of duplicates. This is why the real insert from the next section returns false for a word that already exists.

Deleting a word: the idea

Deleting a word is harder than inserting, because a delete can break other words. Suppose you delete "car" from a trie that also holds "card". If you remove the nodes for c, a and r, the d node becomes unreachable and "card" disappears too. The rule that prevents this is simple to state:

A node can be removed only when no stored word passes through it.

This rule is exactly what the pass counter tells you. A node with pass 0 is on no word's path, so nothing needs it. A node with pass 1 or more is still needed by some word.

The delete algorithm has three steps.

1. Check that the word exists. If it does not, return at once. Deleting a missing word must not change the trie.
2. Walk the word's path from the root. For each node on the path, subtract 1 from its pass. Then clear the word-end flag on the final node.
3. Walk back up the path from the last letter's node toward the root. For each node, if its pass is now 0, delete it and set its parent's pointer to null. Stop at the first node whose pass is above 0, because every node above it is still needed by that word.

This is the same as the recursive pruning in lesson one's erase, but written with pass counts instead of checking children. The pass count makes the rule simple: there is no need to look at the children of each node, because the count already answers whether a word still goes through it.

Here is a trace. The trie holds car and card, so the pass values are c 2, a 2, r 2, d 1. Delete "card".

• Step 1: "card" exists. Continue.
• Step 2: subtract 1 from c, a, r and d. Their passes become c 1, a 1, r 1, d 0. Clear the flag on the d node.
• Step 3: walk up from d. Its pass is 0, so delete the d node and set r's pointer for d to null. Next, r. Its pass is 1, which is above 0, so stop.

The result: the trie holds only car. The r node is still there because car needs it, and the d node is gone because nothing needs it. Now delete "car" as well.

• Step 2: subtract 1 from c, a and r. Their passes become c 0, a 0, r 0. Clear the flag on r.
• Step 3: walk up from r. Pass 0, delete r. Next, a. Pass 0, delete a. Next, c. Pass 0, delete c. Stop at the root, which we never delete.

The trie is empty, and every node except the root was freed. The root stays, because the trie object itself needs one node to start from.

The steps of erasing card from a trie that also holds car, with the pass count of each node before and after

The diagram follows the same two passes: first the count goes down along the path, then the nodes with zero pass are removed from the bottom up.

Worked example 1: the recursive delete from lesson one

The first program uses a recursive delete that checks children instead of counting passes. It is the version from lesson one, with a pass counter added to insert and to the count function. The program deletes card, checks the words, deletes car, then checks again. It is a complete program, so the Run button can execute it directly.

Output:

2
3
0
1
0
1

Trace the first two lines. "car" has two stored words under it, car and card, so its pass is 2. "ca" has three, because cat is also under it. After the delete of card, the search for "card" is 0 because it no longer exists, and the search for "car" is 1 because it still does. The final erase removes car, so the search for "car" is 0. The search for "cat" is 1, because cat was never touched.

Look closely at what this version does not do. It removes the nodes correctly, so the search answers are right. But it never subtracts from pass. After erasing card, the pass of the a node is still 3, and the pass of the r node is still 2. A count query would then report a number that includes the deleted word.

The program does not print that count, so the bug is hidden. Here is the version that does print it. It runs the same deletes, then asks the count of "car" and the count of "ca".

count car after erasing card: 2
search card: 0

The correct count after erasing card is 1, because only car remains under car. The printed 2 is stale. The lesson is that every operation that changes the words must update the counts too. The next worked example does that.

Worked example 2: a command program with counts

This program reads commands from standard input. Each command starts with a letter: I inserts a word, D deletes it, and C prints the count of words with a prefix. Inserts of stored words and deletes of missing words change nothing. The program keeps the counts correct because it uses the pass counter and the rule from the delete section.

Type this as input. It has seven commands:

7
I car
I card
I car
C ca
D card
C ca
D dog

The third command inserts "car" again, which is a duplicate. The last command deletes "dog", which was never stored.

Output:

2
1

Trace the seven commands. The first two inserts store car and card, so the pass of a is 2. The third insert finds car already there, so insert returns false and changes nothing. The first count prints 2, which is right: car and card. Then D card finds the word, subtracts 1 from c, a, r and d, and the d node drops to 0, so it is deleted. The second count prints 1, because only car remains. D dog finds no word and returns false, so the trie is not touched.

The design choice here is that insert and erase both start with a check. Each check is a search, which costs O(L). That is the same order as the change itself, so the checks do not change the big-O cost. They do make the counts trustworthy.

The vector<Node*> parents holds the path. It stores the parent of each letter node, so the pruning loop can set the parent's pointer to null after it deletes the child. Without the parent, you would have the child but no way to clear the pointer that refers to it. A pointer left behind after delete is a dangling pointer, which is a pointer to freed memory. Using it causes the bug shown in the common mistakes section.

Worked example 3: watching the node count fall

The next program inserts car, card and cat, then deletes card, car and cat, printing the number of nodes after each step. The count shows the pruning rule working. Nodes disappear only when no word needs them.

Output:

6
5
4
1

Trace the counts. Three words give six nodes, root included: root, c, a, r, d and t. Erasing card removes only d, because r is still needed by car. That leaves five. Erasing car removes r, because its pass drops to 0. The a node stays, because cat passes through it, leaving four: root, c, a and t. Erasing cat removes t, a and c in that order, from the bottom up. Only the root remains, so the count is 1.

Notice that each erase removed exactly the nodes that were no longer needed, and no others. The root was never removed, because the code never tries to delete it. The loop runs from the last letter toward the first, and it stops at the first node that is still needed.

Worked example 4: a trap with a prefix word

Lesson one showed that a word can be a prefix of another word. Deleting such a word needs care, because the node for the prefix must stay while the longer word still uses it. The next program inserts "a" and "ab", deletes "a", then checks what remains.

Output:

0
1
1

Trace it. Inserting "a" sets pass 1 on the a node and its flag. Inserting "ab" raises the a node's pass to 2 and creates the b node with pass 1. Erasing "a" finds the word, subtracts 1 from the a node, leaving pass 1, and clears the a node's flag. The pruning loop checks the a node: its pass is 1, which is above 0, so the node stays. The answer for search("a") is 0, because the flag is cleared. The answer for search("ab") is 1, because the b node is untouched. The count for "a" is 1, which is the word "ab".

This trap is the reason the pruning rule uses pass and not the flag. A node with its flag cleared can still be needed, and a node with its flag set can be needed by longer words. Only the pass tells you whether any word still goes through it.

What happens inside memory when a node is deleted

A delete call returns the memory of one heap block to the allocator, which is the part of the runtime that hands out heap memory. The block can be reused for a later new. The pointer you held to it still holds the old address, and that address now belongs to nothing, or to a different object later. A pointer to memory that has been freed is called a dangling pointer. Reading or writing through one is undefined behaviour.

The bug is easy to create. Suppose the delete loop forgets to set the parent's pointer to null. The parent still holds the old address. A later search follows it and reads memory that may have been reused. Sometimes the program prints a wrong answer. Sometimes it crashes. The address sanitizer reports the first access precisely. Here is the report for a short program that deletes a node and then reads its flag:

ERROR: AddressSanitizer: heap-use-after-free on address 0x7695d25e0110
READ of size 1 at 0x7695d25e0110 thread T0

The words "heap-use-after-free" name the bug. "READ" means the program read the memory. The stack trace below these lines shows the line that did the read. Find the delete that happened earlier, and check why a pointer still points at that node.

Deleting the same block twice is also undefined behaviour. The sanitizer reports the mistake as a double free:

ERROR: AddressSanitizer: attempting double-free on 0x6e07909e0040 in thread T0:

A double free usually happens when two code paths both think they own a node. The fix is to make one path the only owner, and to set the pointer to null after the delete. A null pointer can be deleted safely, because delete nullptr does nothing. That is one reason the pruning loop sets the parent's pointer to null.

Compare this with the node count. Deleting a node does not change the size of the parent array. The 26 slots stay in the parent, and only the pointer in one slot changes. So the memory saved by deletion is one node at a time, which is about 216 bytes per node in our layout. A trie that holds many words and deletes many of them can still keep a lot of memory if it is never rebuilt. Some systems rebuild the trie once in a while to release the memory of old nodes.

Complexity

Let L be the length of a word, and let P be the length of a prefix.

• Count by prefix: O(P) time, one walk. The stored counts make the answer a single read.
• Insert with the duplicate check: O(L) time, one search and one walk. Space is at most L new nodes.
• Erase with the duplicate check: O(L) time for the search, the walk that subtracts pass counts, and the pruning walk back up. Each step touches one node, so the total is O(L).
• Space: the trie holds at most one node per distinct prefix of the stored words. Deleting releases nodes, so the space shrinks as words leave.

The main cost is still the number of letters, not the number of words. That is the property that makes tries useful. The pruning loop stops early, so an erase often touches only the bottom few nodes of the path.

Note that the pass count needs one integer per node. For a trie of 800,000 nodes, that is 3.2 MB more, which is small compared with the 26 pointers in each node. The count is worth its cost whenever a prefix count is asked often.

Common mistakes and the messages they produce

Mistake 1: subtracting pass on the wrong node

If you subtract from the node before you move, every count is off by one level. The count for the first letter becomes the count for the whole word. Test with two words that share one letter. The count for the shared prefix should be 2. If it is 0 or 1, check the order of the move and the subtract.

Mistake 2: forgetting to subtract pass on delete

This is the stale count bug, which the first worked example shows. The words are deleted correctly, so search answers are right, but countPrefix reports a number that includes the deleted word. The fix is the pass-- line in the walk. Check it with a count after each delete, not only with search.

Mistake 3: deleting a node that another word still needs

If the pruning loop deletes a node without checking its pass, a word that shares the node loses its path. Search for that word then returns false, or the program crashes when it walks into a null pointer. The check if (child->pass > 0) break; is the protection. Without it, the trie quietly loses words.

Mistake 4: a pointer left behind after delete

If the pruning loop deletes a child but does not set the parent's pointer to null, the parent holds a dangling pointer. The next search may read freed memory. The sanitizer reports this as heap-use-after-free, with a READ or WRITE line and a stack trace. The fix is the line parents[k]->next[...] = nullptr; after the delete.

Mistake 5: the same word inserted twice

This is the duplicate trap from the start of this lesson. The pass counts double, and the count is wrong. The output for a test with two inserts of "car" is 2 where 1 is correct. Check the insert with a search first.

Mistake 6: erasing a word that is missing

If erase skips the check, a missing word leads to a walk that fails partway. Then cur is null, and the loop cur->pass-- crashes. Return false before any change. The check costs one search, and it keeps the counts from going negative.

Mistake 7: decreasing a count below zero

If the counts are wrong, a pass can go negative. A node that reaches a negative value is no longer pruned, and it may stay in the trie forever. A negative count is a sign that an earlier delete or insert went wrong. Add a debug check that counts never go below zero.

Debugging walkthrough: the counts drift

Suppose the program reports counts that grow over time, even though the number of words stays the same. Counts that drift are usually a duplicate-insert bug or a missing subtract. Use this order.

Step 1: check the invariant. For any node, the pass equals the number of word ends in its subtree. Equivalently, the pass of a node equals the flag of the node plus the sum of the passes of its children. You can write a checker that walks the whole trie and reports any node that breaks this rule. Run it after each command in a test.

Step 2: find the first command that breaks the rule. Print the checker's result after every command. The first failure tells you which operation caused it. Read that command's code.

Step 3: test the operation alone. Make a small input with the failing command, starting from an empty trie. If an insert of a duplicate breaks it, the check in insert is missing. If a delete breaks it, the subtract or the pruning order is wrong.

Step 4: confirm with the expected output. Write the expected count by hand for the small input, then compare. The count you expect and the count you see should match exactly.

The invariant check is the most useful tool here. It turns a vague symptom into a specific node that breaks a specific rule. Writing it takes about ten lines, and it catches bugs that the search answers alone would hide.

Variations and edge cases

• Delete the only word. The trie becomes empty, and the root is the only node left. Insert a new word afterwards and check that it works. The root must still exist, because the code never deletes it.
• Delete a word that is also a prefix. Worked example 4 shows that the node stays when a longer word needs it.
• Delete, then insert the same word. The second insert recreates the nodes the delete removed. Their pass counts start at zero, so the counts are correct again.
• Count the empty prefix. The root's pass is never incremented, so the count must come from a separate total. Keep an integer total that increases on insert and decreases on delete.
• Many duplicates. Each duplicate costs a search. If the input has many duplicates, the cost is still O(L) per command, so the duplicates do not change the big-O cost.
• Words of different lengths. The pruning loop uses the word length, so a short word and a long word are pruned on their own paths. Test both.

Interview and real-world uses

The patterns in this lesson come up in several interview questions.

• Design a dictionary that supports insert, delete and count by prefix. The answer is the trie with pass counts, plus the duplicate check and the pruning rule.
• Count words with a given prefix in a stream that changes. The pass counter gives the answer in O(P) time after each change.
• Find out whether deleting a word would break any other word. The answer is the pass check on each node along the path.
• Explain why a count can be wrong after a delete. The stale pass is the answer, and the fix is the subtract on the path.

When you explain your design, name the two invariants: the pass of a node equals the number of words through it, and the flag marks a stored word end. Those two facts justify each line of the code.

Practice

Try each exercise before you open the solution. The first three exercises change the code above. The next four ask you to predict or reason about output. The last three build something new.

1. Add a total counter to the command program so that C with an empty prefix prints the number of stored words. Predict the output of the seven-command input from worked example 2 with an extra C at the end.

2. Write a function bool validate(Node* n) that returns true when, for every node, pass equals the flag as 0 or 1 plus the sum of the children's pass values. Hint: the root is special, so skip its check.

bool validate(Node* n) {  // n must not be null
    int sum = n->isEnd ? 1 : 0;
    for (Node* child : n->next) {
        if (child) {
            if (!validate(child)) return false;
            sum += child->pass;
        }
    }
    return sum == n->pass;
}

3. Change erase so it returns false, and prints nothing, when the word was never stored. Test it with D dog in the seven-command input.

4. Predict the pass value of the a node after inserting "ab", "ac", "ad" and then deleting "ac". Then check with the program.

5. A teammate's delete loop removes a node whenever its flag is false, without checking its pass. Give an input that shows the bug and the output that would be wrong.

6. Explain why the empty word cannot be deleted by the code in this lesson, and what you would change to support it.

7. Write a program that reads words and prints, for each delete command, how many nodes were removed. Hint: count the nodes before and after with countNodes.

8. Explain why the pass counter is incremented after the move in insert, not before. What would happen if the order were swapped?

9. A word with a pass of 0 and no flag is still in the trie. Explain how this can happen, and how you would find it.

10. Write the code for a function int countExact(const string& w) that returns 1 when the word is stored and 0 otherwise, using the pass count and not the flag.

int countExact(const string& w) {
    Node* cur = root;
    for (char c : w) {
        cur = cur->next[c - 'a'];
        if (!cur) return 0;
    }
    return cur->isEnd ? 1 : 0;
}

What you now know

• A pass counter on each node counts the stored words that pass through it, so a prefix count is one walk.
• Insert adds to the pass of each child it enters, and it must skip duplicates, or counts double.
• Delete subtracts from the pass along the path, clears the word-end flag, and frees nodes from the bottom up while their pass is 0.
• A node with pass above 0 is still needed by some word, even when its own flag is false.
• Every change must update the counts. A stale count is a silent bug, so test counts after each command.
• Memory is freed one node at a time, and a freed pointer must be cleared, because using it is undefined behaviour.

The next lesson applies these tools to longest common prefixes, word search in a grid, shortest unique prefixes, and a binary trie for bit problems.