Problem Name: Data Structures - Tree: Huffman Decoding

Problem Link:

In this HackerRank in Data Structures - Tree: Huffman Decoding solutions

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. All edges along the path to a character contain a code digit. If they are on the left side of the tree, they will be a 0 (zero). If on the right, they'll be a 1 (one). Only the leaves will contain a letter and its frequency count. All other nodes will contain a null instead of a character, and the count of the frequency of all of it and its descendant characters.

For instance, consider the string ABRACADABRA. There are a total of 11 haracters in the string. This number should match the count in the ultimately determined root of the tree. Our frequencies are A = 5, B =2, R = 2, C = 1 and D = 1. The two smallest frequencies are for C and D, both equal to 1, so we'll create a tree with them. The root node will contain the sum of the counts of its descendants, in this case 1 + 1 = 2. The left node will be the first character encountered, C, and the right will contain D. Next we have 3 items with a character count of 2: the tree we just created, the character B and the character R. The tree came first, so it will go on the left of our new root node. B will go on the right. Repeat until the tree is complete, then fill in the 1's and 0's for the edges. The finished graph looks like:



Input characters are only present in the leaves. Internal nodes have a character value of ϕ (NULL). We can determine that our values for characters are:


A - 0
B - 111
C - 1100
D - 1101
R - 10


Our Huffman encoded string is:


A B    R  A C     A D     A B    R  A
0 111 10 0 1100 0 1101 0 111 10 0


To avoid ambiguity, Huffman encoding is a prefix free encoding technique. No codeword appears as a prefix of any other codeword.


To decode the encoded string, follow the zeros and ones to a leaf and return the character there.


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


Function Description


Complete the function decode_huff in the editor below. It must return the decoded string.


decode_huff has the following parameters:


  • root: a reference to the root node of the Huffman tree
  • s: a Huffman encoded string

Input Format

There is one line of input containing the plain string, s . Background code creates the Huffman tree then passes the head node and the encoded string to the function.



1 <= |s| <= 25

Output Format

Output the decoded string on a single line.

Sample Input



Sample Output



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"




Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

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;
    for(int i = 0; i  <  s.length(); 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 )
    while( pq.size() != 1 ) {
        node * left =;
        node * right =;
        node * comb = new node;
        comb->freq = left->freq + right->freq;
        comb->data = '\0';
        comb->left = left;
        comb->right = right;

void print_codes_hidden(node * root, string code, map < char, string>&mp) {
    if(root == NULL)
    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;
            next = n -> right;
        if(next -> data == '\0'){
            n = next;
            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]];
    return 0;
Copy The Code & Try With Live Editor

#2 Code Example with Java Programming

Code - 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) {
        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) {
            c = root;


public class Solution {
    // input is an array of frequencies, indexed by character code
    public static Node buildTree(int[] charFreqs) {
        PriorityQueue < Node> trees = new PriorityQueue();
        // 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();
    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( + "\t" + leaf.frequency + "\t" + prefix);

        } else if (tree instanceof HuffmanNode) {
            HuffmanNode node = (HuffmanNode)tree;
            // traverse left
            printCodes(node.left, prefix);
            // traverse right
            printCodes(node.right, prefix);
    public static void main(String[] args) {
        Scanner input = new Scanner(;
        String test=;
        // 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())
        // 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);
        Decoding d = new Decoding();
        d.decode(s.toString(), tree);

Copy The Code & Try With Live Editor

#3 Code Example with Python Programming

Code - Python Programming

import queue as Queue

cntr = 0

class Node:
    def __init__(self, freq, data):
        self.freq = freq = 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 ))
    root = q.get()
    root = root[2]#contains root object
    return root

def dfs_hidden(obj, already):
    if(obj == None):
    elif( != '\0'):
        code_hidden[] = already
    dfs_hidden(obj.right, already + "1")
    dfs_hidden(obj.left, already + "0")

"""class Node:
    def __init__(self, freq,data):
        self.freq= freq
        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:
            cur = root
    #Print final array

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

cntr = 0

for ch in ip:
    if(freq.get(ch) == None):
        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)

Copy The Code & Try With Live Editor


[Solved] Cycle Detection solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
[Solved] Swap Nodes [Algo] solution in Hackerrank - Hacerrank solution C, C++, java,js, Python