# HackerRank Tree: Huffman Decoding problem solution

In this HackerRank Tree: Huffman Decoding Interview preparation kit problem You are given a pointer to the root of the Huffman tree and a binary coded string to decode. You need to print the decoded string.

## Problem solution in Python programming.

```import queue as Queue

cntr = 0

class Node:
def __init__(self, freq, data):
self.freq = freq
self.data = data
self.left = None
self.right = None
global cntr
self._count = cntr
cntr = cntr + 1

def __lt__(self, other):
if self.freq != other.freq:
return self.freq < other.freq
return self._count < other._count

def huffman_hidden():#builds the tree and returns root
q = Queue.PriorityQueue()

for key in freq:
q.put((freq[key], key, Node(freq[key], key) ))

while q.qsize() != 1:
a = q.get()
b = q.get()
obj = Node(a[0] + b[0], '\0' )
obj.left = a[2]
obj.right = b[2]
q.put((obj.freq, obj.data, obj ))

root = q.get()
root = root[2]#contains root object
return root

if(obj == None):
return
elif(obj.data != '\0'):

"""class Node:
def __init__(self, freq,data):
self.freq= freq
self.data=data
self.left = None
self.right = None
"""

# Enter your code here. Read input from STDIN. Print output to STDOUT
def decodeHuff(root, s):
cur = root
chararray = []
#For each character,
#If at an internal node, move left if 0, right if 1
#If at a leaf (no children), record data and jump back to root AFTER processing character
for c in s:
if c == '0' and cur.left:
cur = cur.left
elif cur.right:
cur = cur.right

if cur.left is None and cur.right is None:
chararray.append(cur.data)
cur = root

#Print final array
print("".join(chararray))

ip = input()
freq = {}#maps each character to its frequency

cntr = 0

for ch in ip:
if(freq.get(ch) == None):
freq[ch] = 1
else:
freq[ch]+=1

root = huffman_hidden()#contains root of huffman tree

code_hidden = {}#contains code for each object

dfs_hidden(root, "")

if len(code_hidden) == 1:#if there is only one character in the i/p
for key in code_hidden:
code_hidden[key] = "0"

toBeDecoded = ""

for ch in ip:
toBeDecoded += code_hidden[ch]

decodeHuff(root, toBeDecoded)```

## Problem solution in Java Programming.

```import java.util.*;

abstract class Node implements Comparable<Node> {
public  int frequency; // the frequency of this tree
public  char data;
public  Node left, right;
public Node(int freq) {
frequency = freq;
}

// compares on the frequency
public int compareTo(Node tree) {
return frequency - tree.frequency;
}
}

class HuffmanLeaf extends Node {

public HuffmanLeaf(int freq, char val) {
super(freq);
data = val;
}
}

class HuffmanNode extends Node {

public HuffmanNode(Node l, Node r) {
super(l.frequency + r.frequency);
left = l;
right = r;
}

}

class Decoding {

/*
class Node
public  int frequency; // the frequency of this tree
public  char data;
public  Node left, right;

*/

void decode(String S, Node root)
{
StringBuilder sb = 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) {
sb.append(c.data);
c = root;
}
}
System.out.print(sb);
}

}

public class Solution {

// input is an array of frequencies, indexed by character code
public static Node buildTree(int[] charFreqs) {

PriorityQueue<Node> trees = new PriorityQueue<Node>();
// initially, we have a forest of leaves
// one for each non-empty character
for (int i = 0; i < charFreqs.length; i++)
if (charFreqs[i] > 0)
trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));

assert trees.size() > 0;

// loop until there is only one tree left
while (trees.size() > 1) {
// two trees with least frequency
Node a = trees.poll();
Node b = trees.poll();

// put into new node and re-insert into queue
trees.offer(new HuffmanNode(a, b));
}

return trees.poll();
}

public static Map<Character,String> mapA=new HashMap<Character ,String>();

public static void printCodes(Node tree, StringBuffer prefix) {

assert tree != null;

if (tree instanceof HuffmanLeaf) {
HuffmanLeaf leaf = (HuffmanLeaf)tree;

// print out character, frequency, and code for this leaf (which is just the prefix)
//System.out.println(leaf.data + "\t" + leaf.frequency + "\t" + prefix);
mapA.put(leaf.data,prefix.toString());

} else if (tree instanceof HuffmanNode) {
HuffmanNode node = (HuffmanNode)tree;

// traverse left
prefix.append('0');
printCodes(node.left, prefix);
prefix.deleteCharAt(prefix.length()-1);

// traverse right
prefix.append('1');
printCodes(node.right, prefix);
prefix.deleteCharAt(prefix.length()-1);
}
}

public static void main(String[] args) {
Scanner input = new Scanner(System.in);

String test= input.next();

// we will assume that all our characters will have
// code less than 256, for simplicity
int[] charFreqs = new int[256];

// read each character and record the frequencies
for (char c : test.toCharArray())
charFreqs[c]++;

// build tree
Node tree = buildTree(charFreqs);

// print out results
printCodes(tree, new StringBuffer());
StringBuffer s = new StringBuffer();

for(int i = 0; i < test.length(); i++) {
char c = test.charAt(i);
s.append(mapA.get(c));
}

//System.out.println(s);
Decoding d = new Decoding();
d.decode(s.toString(), tree);

}
}```

### Problem solution in C++ programming.

```//
//  main.cpp
//  Huffman
//
//  Created by Vatsal Chanana

#include<bits/stdc++.h>
using namespace std;

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

struct deref:public binary_function<node*, node*, bool> {
bool operator()(const node * a, const node * b)const {
return a->freq > b->freq;
}
};

typedef priority_queue<node *, vector<node*>, deref> spq;

node * huffman_hidden(string s) {

spq pq;
vector<int>count(256,0);

for(int i = 0; i < s.length(); i++ ) {
count[s[i]]++;
}

for(int i=0; i < 256; i++) {

node * n_node = new node;
n_node->left = NULL;
n_node->right = NULL;
n_node->data = (char)i;
n_node->freq = count[i];

if( count[i] != 0 )
pq.push(n_node);

}

while( pq.size() != 1 ) {

node * left = pq.top();
pq.pop();
node * right = pq.top();
pq.pop();
node * comb = new node;
comb->freq = left->freq + right->freq;
comb->data = '\0';
comb->left = left;
comb->right = right;
pq.push(comb);

}

return pq.top();

}

void print_codes_hidden(node * root, string code, map<char, string>&mp) {

if(root == NULL)
return;

if(root->data != '\0') {
mp[root->data] = code;
}

print_codes_hidden(root->left, code+'0', mp);
print_codes_hidden(root->right, code+'1', mp);

}

/*
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)
{
string ans = "";
node* n = root;
for(auto itr = s.begin(); itr != s.end();itr++){
node* next;
if(*itr == '0'){
next = n -> left;
}
else{
next = n -> right;
}
if(next -> data == '\0'){
n = next;
}
else{
ans += next -> data;
n = root;
}
}
cout << ans << endl;
}

int main() {

string s;
std::cin >> s;

node * tree = huffman_hidden(s);
string code = "";
map<char, string>mp;

print_codes_hidden(tree, code, mp);

string coded;

for( int i = 0; i < s.length(); i++ ) {
coded += mp[s[i]];
}

decode_huff(tree,coded);

return 0;
}    ```