So,I was looking for the non-recursive version of Trie data structures deletion in the internet. I couldn’t find one. The best I could manage to find was a recursive implementation of trie in this website. Looking at the code for sometime, I thought that I could make the recursive version of the deletion to non-recursive one. Here is my take on it. Remember, I am worried whether I have done effective memory cleanup. Any insight on the overall code structure will also be helpful. Thanks.

`#include<iostream> using namespace std; struct node{ bool isWord=false; node* previous; node* children[27]; }; void insert(node*& root, string key){ node *temp = root; temp->previous = NULL; int keyLen = key.length(); for(int i=0; i<keyLen; ++i){ int index = key[i]-'a'; //If i is the last element if(i==keyLen-1){ //then take notice of it //and change isWord to true temp->isWord=true; temp->children[index] = NULL; } //If there is no node at a given index if(!temp->children[index]){ //Form a new node temp->children[index] = new node; //Take notice of the node that it is coming from (temp->children[index])->previous = temp; } //Traverse along the children node temp = temp->children[index]; } } bool search(node*&root, string key){ node*temp = root; int keyLen = key.length(); for(int i=0; i<keyLen; ++i){ int index = key[i] -'a'; //If i is at string length //and the end the end it finds //itself to be true if(i==keyLen-1 && temp->isWord==true) { return true; } //If a character does not exist //in the traversal if(!temp->children[index]){ return false; } temp = temp->children[index]; } //If the string is longer then expected return false; } bool hasNoChildren(node* root){ for(int i=0; i<27; ++i){ //If the root has at least one child //then return false if(root->children[i])return false; } //else return true return true; } void remove(node*& root, string key){ if(!search(root,key)) return ; node*temp = root; int keyLen = key.length(); for(int i=0; i<keyLen; ++i){ int index = key[i]-'a'; /*If i reaches the length of the string temp is turned to false is turned to false Which means if day word 'foo' is part of longer word 'football', 'foo' does not exist as a seperate word. And if only 'foo' exist in the dictionary, it also signals for it get removed in the next for loop.*/ if(i==keyLen-1){ temp->isWord = false; } temp = temp->children[index]; } /*The pointer temp in the above for loop manages to reach to the end of the string Since, the previous pointer is being tracked it is easy to retract , if it is so required.*/ for(int i=keyLen-1; i>=0; --i){ /*If the temp isWord variable is false and it happens to have not children then it is being removed. Not this removal happens in the bottom up fashion, which allows effective memory deletion.*/ if(temp->isWord == false && hasNoChildren(temp)){ node*p = temp; temp = temp->previous; delete p; } else temp= temp->previous; } } int main(){ node* a = new node; string keys[] = { "the", "a", "there", "answer", "any", "by", "bye", "their", "hero", "heroplane" }; for (int i = 0; i < 10; i++) insert(a, keys[i]); search(a, "the") ? cout << "Yes\n" : cout << "No\n"; search(a, "these") ? cout << "Yes\n" : cout << "No\n"; remove(a,"heroplane"); search(a, "hero") ? cout << "Yes\n" : cout << "No\n"; return 0; } `