Solution

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

struct node{
    node(string , int , node* , node* , node*);
    string str;
    int num;
    node* next;
    node* left;
    node* right;
};

node::node(string s, int i, node* n=0, node* l=0, node* r=0){
    str = s;
    num = i;
    next = n;
    left = l;
    right = r;
}

bool paircmp(pair <string , int> &a, pair <string, int> &b){
    return a.second > b.second;
}

vector <pair <string, int> >  map2VecPair( map < char, int> cimap){
    //returns sorted vector of pairs of leaf nodes in map
    vector < pair<string, int> > nodeVec;
    map<char,int>::iterator i;
    for ( i = cimap.begin(); i != cimap.end(); i++ )
    {
        pair <string, int> pr;
        pr.first=i->first;
        pr.second=i->second;
        nodeVec.push_back(pr);
    }
    sort(nodeVec.begin(), nodeVec.end(), paircmp);
    return nodeVec;
}

void printLL(node* nd){
    //print linked list
    if (nd == 0) return;
    cout<< nd->str <<":"<<nd->num<<" , ";
    printLL(nd->next);
}

int lsize(node* nd){
    //return size of linked list
    if (nd == 0) return 0;
    return 1 + lsize(nd->next);
}

void linsert(node* &p, node* &root){
    //insert node p into linked list (sorted)
    if (root == 0)
    {
        root = p;
        return;
    }
    else if (p->num < root->num)
    {
        node* temp= root;
        root = p;
        root->next = temp;
        return;
    }
    else if (p->num == root->num)
    {
        if (p->str > root->str)
        {
            node* temp= root;
            root = p;
            root->next = temp;
            return;
        }
        else
        {
            linsert(p, root->next);//equal num but str is bigger
            return;
        }
    }
    else //p->num < root->num
    {
        linsert(p, root->next);
        return;
    }
}

void gentree(node* &root){
    //convert first two nodes of linked list into a new binary tree
    //and insert top node of new tree back into linked list (sorted)

    if (lsize(root) < 2)
    {
        return; //safety check
    }

    string concat= root->str + (root->next)->str;
    int sum = root->num + (root->next)->num;

    node* p = new node(concat, sum);
    p->left = root;
    p->right = root->next;

    root = (root->next)->next; //third node is now the new root in the list
    linsert(p, root);

}

void freenode(node* n){
    //free binary tree memory
    if (n == 0)
        return;
    freenode(n->left);
    freenode(n->right);

    delete n;
}

string gencode(string s, node* &root){
    // generate bit string of 1's and 0's that represent path down binary tree
    // to leaf node
    if (s == root->str)
        return ("");
    else if (((root->left)->str).find(s) != string::npos) //found s in left tree
    {
        return "0"+gencode(s, root->left);
    }
    else
    {
        return "1"+gencode(s, root->right);
    }
}


map <char, int> genUniqChars(string text){
    //generate map of key:unique chars with value: associated int occurance
    map < char, int > cimap;
    for (unsigned int x=0; x < text.size() ;x++)
    {
        if ( cimap.find(text[x]) == cimap.end() ) //not found
        {
            cimap[text[x]] = 1;
        }
        else
        {
            cimap[text[x]] = cimap[text[x]] + 1;
        }
    }
    return cimap;
}


void map2LL(node* &root, map <char , int> cimap){
    //convert map of char / int to sorted linked list

    map<char,int>::iterator i;
    for ( i = cimap.begin(); i != cimap.end(); i++ )
    {
        string s(1, i->first);
        //alternate string ctor to fill string with n(arg1) consecutive chars(arg2)
        node* p= new node(s, i->second);
        linsert(p, root);
    }
}


int main(){
    string text("mississippi river");
    //getline(cin, text);
    //cout << text << endl;

    map < char, int > cimap = genUniqChars(text);

    node* root(0);
    map2LL(root, cimap);

    //generate binary tree
    while (lsize(root) >1)
    {
        cout<<"LINKED LIST: ";
        printLL(root);
        cout<<endl;
        gentree(root);
        cout<<endl;
        cout<<"TREE: ";

    }
    printLL(root);
    cout<<endl;

    vector <pair <string, int> > pv = map2VecPair(cimap);

    for (auto it : pv)
    {
        cout << it.first << " " << it.second << " : "<< gencode(it.first, root)<<endl;
    }


    cout<<endl;
    freenode(root);


    return 0;
}