# Tree: Huffman Decoding – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

# Solutions of Algorithms Data Structures Hard HackerRank:

## Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts

# C++ Tree: Huffman Decoding HackerRank Solution

#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; }

# Java Tree: Huffman Decoding HackerRank Solution

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); } }

# Python 3 Tree: Huffman Decoding HackerRank Solution

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 def dfs_hidden(obj, already): if(obj == None): return elif(obj.data != '\0'): code_hidden[obj.data] = already dfs_hidden(obj.right, already + "1") dfs_hidden(obj.left, already + "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): #Enter Your Code Here 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)

## Leave a comment below