Huffman tree decoding
You could replace the while with a for-each loop. That will get rid of the otherwise unused pos variable, and make the code slightly more compact and idiomatic.

for (char c : S.toCharArray()) {
    // ...
}


Instead of printing the output in the same function that does the main computation, you could return the string result, to minimize the function's responsibilities.

Other than these minor points, the code is fine.