# Efficient serialization/deserialization of huffman tree

I have implemented huffman encoding in the form

struct node
{
node * left;
node * right;
double freq; // the frequency
string letter;
string binary_code; // the variable length code
};


that works fine, eg:

Data: electric eels
Compressed: -σ» //doesnt render in this text editor sorry
Decompressed: electric eelss
Ratio: 38%


But I have no idea how to efficiently encode the tree itself (needed for the decompression) to send over socket, and then decode it.

Can someone help me with some c code/pseudocode style explanation?

Any help appreciated.

## 1 Answer

The usual approach is to build Canonical Huffman code from the frequencies and use it to encode the data.

Canonical Huffman code can be encoded in a pretty compact way, as was described in the ZIP APPNOTE.TXT file, look for words Shannon-Fano and Huffman.

You can find C code in any deflate/inflate implementation or Huff0.

• Thanks, wouldn't deserialization be O(n^2) then? as you'd have to loop over each code and each character in encoded string. It feels like there would be a O(n*m + log(n)) solution for some reason – BinkyNichols Jul 16 '19 at 12:19