Part $2$: Huffman decoding using recursive functions

We have discussed Huffman encoding for data compression in lecture and tutorial, now we

can implement the Huffman decoding for data extraction to recover the original data.

To decode the encoded data, we require the Huffman tree. We iterate through the binary

encoded data. To find character corresponding to current bits, we use following simple steps.

We start from root and do following until a leaf is found.

If current bit is $0,$ we move to left node of the tree.

If the bit is $1,$ we move to right node of the tree.

If during traversal, we encounter a leaf node, we print character of that particular

leaf node and then again continue the iteration of the encoded data starting from

step $1.$

Your task is to implement the Huffman decoding algorithm from the above steps in a C$++$

program with Huffman decoding function and a main function to decode a compressed string

based on Huffman encoding and display the original string.