Delete
Lesson 8 of 14 in Coddy's Tries - Data Structures Series #8 course.
Deleting from a trie has two parts. The simple part: find the terminal node for the word and set its isEndOfWord back to false. After that the word is no longer reported by search, which is what users care about.
The trickier part: prune nodes that are now useless. A child node is useless if it has no children of its own and is not itself the end of some other word - it cannot be reached by any future search or prefix walk. We discover those nodes by recursing down, then trimming on the way back up.
Be careful with two cases. If you try to delete a word that was never inserted, do nothing. If the word you delete is a prefix of another stored word (deleting "car" when "card" is also in the trie), you must clear the flag but keep all the nodes - those nodes are still reachable by "card".
Challenge
MediumAdd a method delete to the Trie class.
It gets a string word:
- If
wordis stored in the trie, unmark its terminal node (isEndOfWord = false) and remove any now-orphan nodes on the way (nodes with no children and not the end of another word). - If
wordis not in the trie, do nothing.
A clean way to implement the pruning is a recursive helper that returns a boolean telling the caller whether the current child can be removed.
Try it yourself
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "delete") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_delete(&t, arg); }
}
return 0;
}