> For the complete documentation index, see [llms.txt](https://vikram-bajaj.gitbook.io/cs-gy-6033-i-design-and-analysis-of-algorithms-1/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://vikram-bajaj.gitbook.io/cs-gy-6033-i-design-and-analysis-of-algorithms-1/chapter1/huffman-coding.md).

# 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](https://youtu.be/dM6us854Jk0) for a detailed explanation.