#include <iostream>
#include <set>
#include <sstream>

class HuffmanNode
{
public:

    char letter; // '\0' for non-leaf nodes
    int freq;

    HuffmanNode *leftChild;
    HuffmanNode *rightChild;

    HuffmanNode(char letter, int freq, HuffmanNode *leftChild = nullptr, HuffmanNode *rightChild = nullptr)
            : letter(letter), freq(freq), leftChild(leftChild), rightChild(rightChild)
    {}

    HuffmanNode(const HuffmanNode &node)
            : letter(node.letter), freq(node.freq), leftChild(node.leftChild), rightChild(node.rightChild)
    {}

    bool operator<(const HuffmanNode &node) const
    {
        return this->freq <= node.freq;
    }
};


void huffmanCode(std::multiset<HuffmanNode> &multiset)
{
    while (multiset.size() > 1)
    {
        HuffmanNode *n1 = new HuffmanNode(*(multiset.begin()));
        multiset.erase(multiset.begin());
        HuffmanNode *n2 = new HuffmanNode(*(multiset.begin()));
        multiset.erase(multiset.begin());


        multiset.insert(HuffmanNode('\0', n1->freq + n2->freq, n1, n2));
    }

}

void postOrderPrint(HuffmanNode *node, const std::string &s)
{
    if (!node)
        return;
    postOrderPrint(node->leftChild, s + "0");
    postOrderPrint(node->rightChild, s + "1");

    if (node->letter != '\0')
        std::cout << node->letter << ": " << s << "\n";
}

int main()
{
    std::multiset<HuffmanNode> s = {
                                    {'D', 1},
                                    {'C', 1},
                                    {'R', 2},
                                    {'B', 2},{'A', 5}}; // for the example ABRACADABRA

    huffmanCode(s);
    HuffmanNode root = *(s.begin());


    postOrderPrint(&root, "");

    return 0;
}