include<bits/stdc++.h>

using namespace std;

typedef long long ll; typedef double dbl;

define fr(x,a,b) for(ll x=a;x<b;x++)

define PB push_back

define MP make_pair

define mod 1000000007

define gmax LLONG_MAX

define gmin LLONG_MIN

define INF 2e9

define N 26

define MAX(a,b,c) max(max(a,b),c)

define MIN(a,b,c) min(min(a,b),c)

define SZ(x) x.size()

struct Trie{ struct Trie *child[N]; // reference to a to z alphabets(N=26) bool is_EOW; // flag for indicating end of word or not

~Trie(){ cout<<"\nMemory Freed!\n"; } };

struct Trie get_node(){ struct Trie ptr = new Trie;

ptr->is_EOW=false;

fr(i,0,N) ptr->child[i]=NULL;

return ptr; }

// inserts a word in the trie data structure void insert(struct Trie root,string word){ struct Trie ptr=root;

ll pos; fr(i,0,word.size()){ pos=word[i]-'a'; if(ptr->child[pos]==NULL) ptr->child[pos]=get_node(); ptr=ptr->child[pos]; }

ptr->is_EOW=true; }

// checks if the word is present as complete word bool complete_search(struct Trie root,string word){ struct Trie ptr=root;

ll pos; fr(i,0,word.size()){ pos=word[i]-'a'; if(ptr->child[pos]==NULL) return false; ptr=ptr->child[pos]; }

return (ptr!=NULL && ptr->is_EOW==true); }

// checks if the word is present as complete word or prefix of some other word bool prefix_search(struct Trie root,string word){ struct Trie ptr=root;

ll pos; fr(i,0,word.size()){ pos=word[i]-'a'; if(ptr->child[pos]==NULL) return false; ptr=ptr->child[pos]; }

return (ptr!=NULL); }

bool is_leaf(struct Trie *node){ return (node->is_EOW); }

bool is_free(struct Trie *node){ fr(i,0,26) if(node->child[i]!=NULL) return false; return true; }

// delets a word from the true data structure bool delete_word(struct Trie *root,string word,ll ind){ if(root==NULL) return false;

if(ind==SZ(word)){ if(root->is_EOW){ root->is_EOW=false; if(is_free(root)) return true; return false; } } else{ ll pos=word[ind]-'a';

if(root->child[pos]==NULL) return false;

if(delete_word(root->child[pos],word,ind+1)){
  delete root->child[pos];
  //root->child[pos]=NULL;
  return (!is_leaf(root) && is_free(root));
}

}

return false; }

int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

string list[5]={"a","abc","abccd","egh","eghik"};

struct Trie *root=get_node();

fr(i,0,5) insert(root,list[i]);

fr(i,0,5){ if(complete_search(root,list[i])){ cout<<list[i]<<" is found as complete word\n"; } } cout<<"\n";

string new_words[3]={"ab","eghi","a"};

fr(i,0,3){ if(complete_search(root,new_words[i])){ cout<<new_words[i]<<" is found as complete word\n"; } } cout<<"\n";

fr(i,0,3){ if(prefix_search(root,new_words[i])){ cout<<new_words[i]<<" is found as prefix\n"; } } cout<<"\n";

cout<<delete_word(root,"abccd",0)<<"\n"; cout<<complete_search(root,"abccd");

return 0; }