struct Trie {
struct TrieNode {
bool isEnd;
array<TrieNode*, 26> child;
TrieNode() : isEnd(false), child{} {}
bool isEmpty() {
for (int i = 0; i < 26; i++) {
if (this->child[i] != nullptr) {
return false;
}
}
return true;
}
};
TrieNode* root;
Trie () {
root = new TrieNode();
}
void insert (string &word) {
TrieNode* curr = root;
for (int i = 0; i < word.length(); i++) {
int idx = word[i] - 'a';
if (curr->child[idx] == nullptr) {
curr->child[idx] = new TrieNode();
}
curr = curr->child[idx];
}
curr->isEnd = true;
}
bool isPre (string &word, int type) { // type 0 : isPresent, type 1: isPrefix
TrieNode* curr = root;
for (int i = 0; i < word.length(); i++) {
int idx = word[i] - 'a';
if (curr->child[idx] == nullptr) {
return false;
}
curr = curr->child[idx];
}
return (type ? true : curr->isEnd);
}
TrieNode* erase (TrieNode* curr, string &word, int i) {
if (curr == nullptr) {
return nullptr;
}
if (i == word.length()) {
curr->isEnd = false;
if (curr->isEmpty()) {
delete curr;
curr = nullptr;
}
return curr;
}
int idx = word[i] - 'a';
curr->child[idx] = erase(curr->child[idx], word, i + 1);
if (curr->isEnd == false && curr->isEmpty()) {
delete curr;
curr = nullptr;
}
return curr;
}
};
I implemented the following code, but the issue is with the erase function. Specifically, say I insert two elements in the trie and then remove both. Then the isPre() function stops working. I guess when I call the erase to delete the entire trie, it deletes the original root, which is then accessed, and thus the issue.
But I am not sure how to resolve it. I tried adding a nullptr check at the start of the isPre() function but even then, I get the error.
Except for the case where I delete all the trie's nodes after inserting them, the trie is working fine (even when I have not inserted anything).
/* Trie Struct */
string str = "a";
Trie trie;
cout << trie.isPre(str, 0); // Working Fine
trie.insert(str);
cout << trie.isPre(str, 0); // Working Fine
trie.erase(trie.root, str, 0);
cout << trie.isPre(str, 0); // Creates the Error
Error:
==22==ERROR: AddressSanitizer: heap-use-after-free on address 0x611000000350 at pc 0x00000034e11e bp 0x7ffdd3c379e0 sp 0x7ffdd3c379d8
READ of size 8 at 0x611000000350 thread T0
Edit: As, I had suspected the error was caused due to the root node being delete. So, I just added a condition that root shouldn't be deleted. It worked fine. Here is the implementation. But, I am not sure if this is the way to go, I would be glad if anyone can suggest a better trie implementation
Indeed your code performs a delete on the root node, which should never happen. A quick fix is to only perform the delete when i > 0. Alternatively you could only perform a delete on a child (one level up in the recursion tree) -- that way the target will never be the root. This also means you don't need the return value to be a node pointer, and can instead use the return value to indicate success (if the word was found) or failure (nothing to delete):
// Now curr is assumed to never be nullptr
bool erase (TrieNode* curr, string &word, int i) {
if (i == word.length()) {
bool success = curr->isEnd;
curr->isEnd = false;
return success;
}
int idx = word[i] - 'a';
TrieNode* child = curr->child[idx];
bool success = child && erase(child, word, i + 1);
if (success && !child->isEnd && child->isEmpty()) {
delete child;
curr->child[idx] = nullptr;
}
return success;
}