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

using namespace std;

// Определение структуры узла трай-дерева
struct TrieNode
{
	// Вектор дочерних узлов (размерность 26 для каждой буквы алфавита)
	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]);
		}
		// Удаляем текущий узел
		delete node;
	}

	// Вспомогательный метод для удаления пустых узлов из трай-дерева
	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)
		{
			// Если дочерний узел не равен nullptr, значит он не пустой
			if (child != nullptr)
			{
				// Так как наша задача - удалить все пустые узлы, то если нашли хотя бы один непустой узел,
				// можно сразу вернуть false - текущий узел не является пустым
				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");
	// Удаляем с префиксом "ap"
	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;
}