Tree: Huffman Decoding Hackerrank problem solution

Tree: Huffman Decoding Hackerrank

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.

For example :

{ϕ,5}
0 / \ 1
{ϕ,2} {A,3}
0/ \1
{B,1} {C,1}

Input characters are only present on the leaves. Internal nodes have a character value of ϕ. Codewords:

A - 1
B - 00
C - 01

No codeword appears as a prefix of any other codeword. Huffman encoding is a prefix free encoding technique.

Encoded String “1001011” represents the string “ABACA”

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.

Input Format

You are given a function,

void decode_huff(node * root, string s)
{

}
The structure for node is defined as :

struct node
{
int freq;
char data;
node * left;
node * right;

}node;

Note:
Internal nodes have data=’\0′(ϕ )

Output Format

Output the decoded string on a single line.

Sample Input

{ϕ,5}
0 / \ 1
{ϕ,2} {A,3}
0/ \1
{B,1} {C,1}

S=”1001011″
Sample Output

ABACA
Explanation

S=”1001011″
Processing the string from left to right.
S[0]=’1′ : we move to the right child of the root. We encounter a leaf node with value ‘A’. We add ‘A’ to the decoded string.
We move back to the root.

S[1]=’0′ : we move to the left child.
S[2]=’0′ : we move to the left child. We encounter a leaf node with value ‘B’. We add ‘B’ to the decoded string.
We move back to the root.

S[3] = ‘1’ : we move to the right child of the root. We encounter a leaf node with value ‘A’. We add ‘A’ to the decoded string.
We move back to the root.

S[4]=’0′ : we move to the left child.
S[5]=’1′ : we move to the right child. We encounter a leaf node with value C’. We add ‘C’ to the decoded string.
We move back to the root.

S[6] = ‘1’ : we move to the right child of the root. We encounter a leaf node with value ‘A’. We add ‘A’ to the decoded string.
We move back to the root.

Decoded String = “ABACA”

Solution

Suppose you are currently in the root node. Traverse the encoded string from left to right. Whenever you encounter a ‘0’, move the current pointer to left,wWhenever you encounter a ‘1’, move the current pointer to right. After every move, check if you reached a leaf node (a node without any child). When you reach a leaf node, you found a new character in the decoded string. Append the character with the answer and move the current pointer to the root again.
The complexity is O(n) where n is the length of the encoded string.

/* 
The structure of the node is

typedef struct node
{
    int freq;
    char data;
    node * left;
    node * right;
    
}node;

*/

void decode_huff(node * root,string s)
{
node* np=root;
for(int i=0;i<s.size();i++) {
int n= s[i] - '0';
if(n==0) {
np=np->left;
if(np->left ==nullptr && np->right==nullptr) {
cout<<np->data;
np=root;
}
}
else {
np=np->right;
if(np->left ==nullptr && np->right==nullptr) {
cout<<np->data;
np=root;
}
}
}
}
void decode(String S, Node root)
{
    StringBuilder output = new StringBuilder();
    Node c = root;
    for (int i = 0; i < S.length(); i++) {
        c = S.charAt(i) == '1' ? c.right : c.left;
        if (c.left == null && c.right == null) {
            output.append(c.data);
            c = root;
        }
    }
    System.out.print(output);
}

A recursive solution in java:
//Thank you mduarte


public Node originalNode;

void decode(String S, Node root) {
    originalNode = root;
    decodeHelper(S, root);
}

void decodeHelper(String S ,Node root) {
    if(S.isEmpty()) {
        if(root.data != '\0') 
            System.out.print(root.data);
    }
    else {
        if(root.data != '\0') {
            System.out.print(root.data);
            decodeHelper(S, originalNode);
        }
        else {
            char c = S.charAt(0);
            if(c == '0') {
                decodeHelper(S.substring(1), root.left);
            }
            else {
                decodeHelper(S.substring(1), root.right);
            }
        }
    }
}
void decode_huff(node * root,string s)
{
    string ans="";
    node *curr=root;
    for(int i=0;i<s.size();i++){
        if(s[i]=='0') curr = curr->left;
        else curr = curr->right;
        if(!curr->left and !curr->right){ //reached leaf node
            ans=ans + curr->data;
            curr=root;
        }
    }
    cout<<ans<<endl;
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.