Huffman Coding

This problem can be solved using the Greedy Approach.

Huffman Coding is a lossless data compression algorithm.

Goal: Assigning codes to characters, based on their frequency of occurrence (the most frequent character gets the smallest code and the least frequent character gets the largest code); also, no code must be a prefix of a code assigned to another character

There are mainly two major parts in Huffman Coding:

1. Build a Huffman Tree from input characters

2. Traverse the Huffman Tree and assign codes to characters

See this video for a detailed explanation.