Huffman coding assigns variable length codewords to fixed length input characters based on their frequencies. More frequent characters are assigned shorter codewords and less frequent characters are assigned longer codewords. A Huffman tree is made for the input string and characters are decoded based on their position in the tree. We add a '0' to the codeword when we move left in the binary tree and a '1' when we move right in the binary tree. We assign codes to the leaf nodes which represent the input characters.

You have to decode an encoded string using the Huffman tree.

You are given pointer to the root of the Huffman tree and a binary coded string. You need to print the actual string.


void decode(String S ,Node root)
        if (root == null) return;
        StringBuilder sb = new StringBuilder();
        int pos = 0;
        Node current = root;
        char[] chars = S.toCharArray();
        while (pos < chars.length) {
            char c = chars[pos];
            if (c == '0' && current.left != null) {
                current = current.left;
            else if (c == '1' && current.right != null) {
                current = current.right;
            if (current.left == null && current.right == null) {
                current = root;
  • \$\begingroup\$ Did you write unit tests for that code ? This could be an improvment and also a facilitation for people wanting you help you reviewing your code. \$\endgroup\$ – Spotted Dec 21 '16 at 9:43

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.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.