Trie

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int ALPHABET_SIZE = 26;

// trie node
class TrieNode
{
	public:
		vector<TrieNode*> children;

		bool isEndOfWord;                 // true means that the node represents end of a word

		TrieNode(){
		    children.resize(ALPHABET_SIZE);
		}
};


// Returns new trie node (with all children initialized to NULLs)
TrieNode* createNewNode() {
	TrieNode *node = new TrieNode();

	node->isEndOfWord = false;

	for (int i = 0; i < ALPHABET_SIZE; i++){
		node->children[i] = NULL;
	}

	return node;
}


// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void insert(TrieNode* root, string key)
{
	TrieNode *itr = root;

	for (int i = 0; i < key.length(); i++)
	{
		int index = key[i] - 'a';
		if (!itr->children[index]){
		    TrieNode* newNode = createNewNode();
			itr->children[index] = newNode;
		}

		itr = itr->children[index];
	}

	// mark last node as leaf
	itr->isEndOfWord = true;
}


bool search(TrieNode* root, string key)
{
	TrieNode* itr = root;
 
	for (int i = 0; i < key.length(); i++)
	{
		int index = key[i] - 'a';
		
		if (!itr->children[index]){
			return false;
		}

		itr = itr->children[index];
	}

	return (itr->isEndOfWord);
}

// Driver
int main()
{
	// Input keys (use only 'a' through 'z' and lower case)
	vector<string> keys = {"the", "a", "there", "answer", "any", "by", "bye", "their" };
	
	int n = keys.size();

	TrieNode *root = createNewNode();

	// Construct trie
	for (int i = 0; i < n; i++){
		insert(root, keys[i]);
	}

	// Search for different keys
	cout << "the :: "  << search(root, "the")     << endl;
	cout << "these :: " << search(root, "these")  << endl;
	cout << "their :: " << search(root, "their")  << endl;
	cout << "thaw :: " << search(root, "thaw")    << endl;
	
	
	return 0;
}