#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct TrieNode
{
	vector<TrieNode*> children;
	bool isEndOfWord;

	TrieNode()
	{
		children = vector<TrieNode*>(26, nullptr);
		isEndOfWord = false;
	}
};

class Trie
{
private:
	TrieNode* root;

public:
	Trie()
	{
		root = new TrieNode();
	}

	void insert(const string& word)
	{
		TrieNode* node = root;
		for (char c : word)
		{
			if (node->children[c - 'a'] == nullptr)
			{
				node->children[c - 'a'] = new TrieNode();
			}
			node = node->children[c - 'a'];
		}
		node->isEndOfWord = true;
	}

	bool search(const string& word)
	{
		TrieNode* node = root;
		for (char c : word)
		{
			if (node->children[c - 'a'] == nullptr)
			{
				return false;
			}
			node = node->children[c - 'a'];
		}
		return node != nullptr && node->isEndOfWord;
	}

	bool startsWith(const string& prefix)
	{
		TrieNode* node = root;
		for (char c : prefix)
		{
			if (node->children[c - 'a'] == nullptr)
			{
				return false;
			}
			node = node->children[c - 'a'];
		}
		return node != nullptr;
	}

	void removePrefix(const string& prefix)
	{
		removePrefixHelper(root, prefix, 0);
		deleteEmptyNodes(root);
	}

private:
	void removePrefixHelper(TrieNode* node, const string& prefix, int index)
	{
		if (node == nullptr)
		{
			return;
		}
		if (index == prefix.length())
		{
			removeWords(node);
			return;
		}
		removePrefixHelper(node->children[prefix[index] - 'a'], prefix, index + 1);
	}

	void removeWords(TrieNode* node)
	{
		if (node == nullptr)
		{
			return;
		}
		node->isEndOfWord = false;
		for (int i = 0; i < node->children.size(); i++)
		{
			removeWords(node->children[i]);
		}
	}

	void deleteEmptyNodes(TrieNode* node)
	{
		if (node == nullptr)
		{
			return;
		}
		for (int i = 0; i < node->children.size(); i++)
		{
			if (node->children[i] != nullptr)
			{
				if (node->children[i]->isEndOfWord == false && isNodeEmpty(node->children[i]))
				{
					delete node->children[i];
					node->children[i] = nullptr;
				}
				else
				{
					deleteEmptyNodes(node->children[i]);
				}
			}
		}
	}

	bool isNodeEmpty(TrieNode* node)
	{
		for (TrieNode* child : node->children)
		{
			if (child != nullptr)
			{
				return false;
			}
		}
		return true;
	}
};


int main()
{
	Trie trie;
	trie.insert("apple");
	trie.insert("banana");
	trie.insert("app");
	trie.insert("apartment");
	trie.insert("baby");
	trie.insert("book");
	trie.removePrefix("ap");
	cout << (trie.search("apple") ? "apple found" : "apple not found") << endl;
	cout << (trie.search("banana") ? "banana found" : "banana not found") << endl;
	cout << (trie.search("app") ? "app found" : "app not found") << endl;
	cout << (trie.search("apartment") ? "apartment found" : "apartment not found") << endl;
	cout << (trie.search("baby") ? "baby found" : "baby not found") << endl;
	cout << (trie.search("book") ? "book found" : "book not found") << endl;
	return 0;
}