Tree: Huffman Decoding

Hello World!

Let’s solve the Tree: Huffman Decoding problem on HackerRank. You may click on the title to read the problem statement. So let’s start…

In this problem, we need to implement the decodeHuff function. We will be provided with the root node of Huffman Tree and the Huffman Code in string format. We basically need to decode the string and print the original text.

Huffman encoding is a prefix free encoding technique. You may observe in the below figure that when you encounter a zero, you need to move to the left child and when you encounter a one, you need to move to the right child.

So start with declaring a variable to keep track of index in the string, say ‘idx’ and a variable to traverse the tree, say ‘current’. Initialize idx to zero. Now, iterate until the index variable is of the size of length of the Huffman code string. Further in the loop, iterate until you reach any leaf node i.e. while ‘current’ node is not a leaf node. If the character at ‘idx’ in the string is zero, move ‘current’ to left else if the character at the ‘idx’ in the string is one, move ‘current’ to right. Also increment ‘idx’ by one each time you move ‘current’. When you reach the leaf node, append the data of ‘current’ to a list(you may name it anything you want). Reset the ‘current’ to root node again to find the next character. Print the string at the end.

Open for suggestions. The code for this problem in Python3 can be found here.

Happy coding…