> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/greedy-algorithms/12.huffman-coding.md).

# 12.Huffman Coding

Huffman coding is a **lossless data compression algorithm.**

**Consider the string *****ABRACADABRA*****.**

![image](https://s3.amazonaws.com/hr-assets/0/1528128577-d4e3a24f3e-huffmanExample.png)

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
or
01111001100011010111100
```

## Huffman Decoding

```cpp
void decode_huff(node *root, string s)
{

    string res = "";
    int n = s.length();
    int i = 0;
    while (i < n)
    {
        node *t = root;
        queue<node *> q;
        q.push(t);

        while (!q.empty())
        {
            t = q.front();
            q.pop();

            if (!t->left && !t->right)
            {
                res += t->data;
                break;
            }

            if (s[i] == '0')
            {
                q.push(t->left);
            }
            else if (s[i] == '1')
            {
                q.push(t->right);
            }
            
            i++;
        }
    }
    cout << res;
}
```