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

struct TrieNode
{
	TrieNode *child[26]={}; //if string contains alphabets only
	bool word=0;
};

void insert(struct TrieNode *root, string key)
{
	TrieNode *it = root;
	for (int i = 0; i < key.size(); i++)
	{
		int index = key[i] - 'a';
		if (!it->child[index]) it->child[index] = new TrieNode();
		it = it->child[index];
	}
	it->word = 1;
}

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

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

	TrieNode *root = new TrieNode();

	// Construct trie
	for (int i = 0; i < keys.size(); i++)
		insert(root, keys[i]);

	// Search for different keys
	char output[][32] = {"Not present in trie", "Present in trie"};

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