#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

const int AlphabetLength = 26;

struct TrieNode
{
	TrieNode *child[AlphabetLength];
	bool IsEnd;
	size_t height;
};


TrieNode* MakeNode()
{
	TrieNode *newnode = new TrieNode;
	newnode->IsEnd = false;
	for (int i = 0; i < AlphabetLength; i++)
	{
		newnode->child[i] = NULL;
	}
	return newnode;
}


void add(TrieNode *root, string key)
{
	TrieNode *current = root;
	for (size_t i = 0; i < key.length(); i++)
	{
		int letter = key[i] - 'a';
		if (!current->next[letter])
		{
			cout << key[i];
			current->next[letter] = MakeNode();
			current->next[letter]->height = current->height += 1;
		}

		current = current->next[letter];
	}
	current->IsEnd = true;
}



void compare(TrieNode *root, size_t key, int& more, int& less, int& equal)
{
    for (int i = 0; i < AlphabetLength; i++) //Проходим по алфавиту
    {
        TrieNode* child = root->next[i];
        if (!child) continue;                //Если встречаем NULL, то переходим к следующей букве
        if (child->IsEnd)
        {
             if (cur->Is_end && cur->height > key) more = more + 1;
             if (cur->Is_end && cur->height < key) less = less + 1;
             if (cur->Is_end && cur->height == key) equal = equal + 1;
        }
        compare(child);                      //рекурсивно вызываем функцию независимо от того, встретился ли конец слова.
    }                                        //Это помогает избежать такого случая: если в дереве есть слова app и apple,
                                             //то он обработает оба, не потеряв конец слова apple
}