# define ALPHABET_SIZE 26
#include<iostream>
using namespace std;

typedef struct node {
	node* children[ALPHABET_SIZE];
	bool isLeaf;
};

node* newNode() {
	node* pNode = new node;
	pNode->isLeaf = false;
	for (int i = 0; i < ALPHABET_SIZE; i++)
		pNode->children[i] = nullptr;

	return pNode;
}

void insert(node* root, const char* str) {
	node* pCrawl = root;

	while (*str) {
		int index = *str - 'a';
		if (!pCrawl->children[index])
			pCrawl->children[index] = newNode();
		pCrawl = pCrawl->children[index];
		str++;
	}
	pCrawl->isLeaf = true;
}

bool search(node* root, const char* str) {
	node* pCrawl = root;

	while (*str) {
		int index = *str - 'a';
		if (!pCrawl->children[index])
			return false;
		pCrawl = pCrawl->children[index];
		str++;
	}

	return (pCrawl != nullptr && pCrawl->isLeaf);
}

bool hasChildren(node* currNode) {

	for (int i = 0; i < ALPHABET_SIZE; i++) {
		if (currNode->children[i] != nullptr) {
			return true;
		}
	}

	return false;
}

bool deleteKey(node* pNode, const char* str){

	if (pNode == nullptr)
		return false;
	if (*str) {
		int index = *str - 'a';
		if (pNode != nullptr && pNode->children[index]
			&& deleteKey(pNode->children[index], str + 1) && !pNode->isLeaf) {

			if (!hasChildren) {
				delete pNode;
				pNode = nullptr;
				return true;
			}
			else {
				return false;
			}
		}
	}

	if (*str == '\0' && pNode->isLeaf) {
		if (!hasChildren(pNode)) {
			delete pNode;
			pNode = nullptr;
			return true;
		}
		else {
			pNode->isLeaf = false;
			return false;
		}
	}

	return false;
}

int main()
{
	const char* keys[] = { "the", "a", "there",
		"answer", "any", "by",
		"bye", "their" };
	int n = sizeof(keys) / sizeof(keys[0]);

	node *root = newNode();

	for (int i = 0; i < n; i++)
		insert(root, keys[i]);

	search(root, "the") ? cout << "Yes\n" :
		cout << "No\n";
	search(root, "these") ? cout << "Yes\n" :
		cout << "No\n";
	cout << deleteKey(root, "the")<< endl;
	search(root, "the") ? cout << "Yes\n" :
		cout << "No\n";
	search(root, "there") ? cout << "Yes\n" :
		cout << "No\n";
	cout << deleteKey(root, "any") << endl;
	search(root, "any") ? cout << "Yes\n" :
		cout << "No\n";

}