TRIE

#include<bits/stdc++.h>
using namespace std;

#define alphabet_size 26

struct TrieNode {
	TrieNode* alphabet[26];
	bool isLeaf;
	TrieNode(){
		for(int i=0;i<26;i++){
			alphabet[i]=NULL;
		}
		isLeaf = false;
	}

};

class TRIE {
	TrieNode* root;
	void delNodes(TrieNode* cur);
public:
	TRIE();
	~TRIE();
	TRIE(bool h);
	void insert(string word);
	bool search(string word);
};

TRIE::TRIE(){
	root = new TrieNode();
}

void TRIE::delNodes(TrieNode *cur){
	for(int i=0;i<alphabet_size;i++){
		if(cur->alphabet[i]!=NULL){
			delNodes(cur->alphabet[i]);
		}
	}
	delete(cur);
}

TRIE::~TRIE(){
	TrieNode *cur = root;
	delNodes(cur);
}


TRIE::TRIE(bool h){
	root = new TrieNode();
}

void TRIE::insert(string word){
	TrieNode *cur = root;
	for(int i=0;i<word.size();i++){
		int ch = word[i]-'a';
		if(cur->alphabet[ch]==NULL){
			cur->alphabet[ch] = new TrieNode();
		}
		cur = cur->alphabet[ch];
	}
	cur->isLeaf = true;
}


bool TRIE::search(string word){
	TrieNode *cur = root;
	for(int i=0;i<word.size();i++){
		int ch = word[i]-'a';
		if(cur->alphabet[ch]==NULL){
			return false;
		}
		cur = cur->alphabet[ch];
	}
	return (cur->isLeaf == true);
}




int main(){
	TRIE trie(true);
	trie.insert("hello");
	trie.insert("hel");
	trie.insert("how");

	cout<<trie.search("he")<<endl;
	cout<<trie.search("hello")<<endl;
	cout<<trie.search("she")<<endl;
	return 0;
}