We can search the trie in O(n) time with n being the length of the word.
Finally, we can implement remove.
To know whether we should remove something, we should first check if the word is in the trie. So first, we'll need to do a search for it and see if we get a depth value returned.
1void remove(std::string val) {
2 int depth = this->search(val);
3 if (depth) {
4 removeHelper(this->head, val, depth);
5 }
6}
7
8TrieNode* remove(TrieNode* root, std::string key, int depth = 0) {
9 TrieNode* pCrawl = root;
10
11 if (!pCrawl)
12 return nullptr;
13
14 if (depth == key.size()) {
15 if (pCrawl->isEndOfWord)
16 pCrawl->isEndOfWord = false;
17
18 if (isEmpty(pCrawl))
19 pCrawl = nullptr;
20
21 return pCrawl;
22 }
23}