// Дано бинарное дерево с выделенным корнем, в каждой вершине которого записано по одной букве A-Z.
// Две вершины считаются эквивалентными, если поддеревья этих вершин содержат одинаковое
// множество (т.е. без учета частот) букв.
// нужно найти любую пару эквивалентных вершин.


struct TNode {
    char Value;  // [A-Z]
    TNode* Left;
    TNode* Right;
};

using TLetterSet = std::array<bool, 26>;

std::string GenerateKey(const TLetterSet &letters)
{
    std::string result;
    for (size_t i = 0; i < letter.size(); ++i)
    {
        if (letters[i])
        {
            result += ('A' + i);
        }
    }

    return result;
}

TLetterSet GenerateLettersForSubTree(const TNode *node, std::unordered_map<std::string, std::vector<TNode *>> &nodesKeys)
{
    if (!node)
    {
        TLetterSet falseSet;
        for (size_t i = 0; i < falseSet.size(); ++i)
        {
            falseSet[i] = false;
        }

        return falseSet;
    }

    const auto leftLetters = GenerateLettersForSubTree(node->Left);
    const auto rightLetters = GenerateLettersForSubTree(node->Right);

    TLetterSet nodeLetters;
    for (size_t i = 0; i < nodeLetters.size(); ++i)
    {
        nodeLetters[i] = leftLetters[i] || rightLetters[i];
    }
    nodesLetters[node->Value - 'A'] = true;

    const auto nodeKey = GenerateKey(nodeLetters);
    nodesKeys[nodeKey].push_back(node);

    return nodesLetters;
}

std::pair<TNode*, TNode*> FindEquivalentSubtrees(TNode* root)
{
    std::unordered_set<std::string, std::vector<TNode *>> nodesKeys;
    GenerateLettersForSubTree(root, nodesKeys);

    for (const auto &[key, nodes] : nodesKeys)
    {
        if (nodes.size() > 1)
        {
            return {nodes[0], nodes[1]};
        }
    }

    return {nullptr, nullptr};
}