That was a year ago- so it's probably irrelevant by now- but just in case-
A little hint- what if left/right nodes got a left/right node of its own?

Like how you used the numeric value of the char as an index :)

I know it can't be changed anymore- but for the C++ version- it would be more practical if the order of the categories at the return string didn't matter.
The most obvious data structure to use in C++ is map.
If you use map- it orders it alphabaticaly, if you use unorderd_map- you don't know what order you are going to get.
of course- you can use vector of pairs that will keep the insertation order- but then you'll have to write the Unique key as an element thing.