title: Decoding algorithm/implementation using Huffman tree
body: <p>Start with a text file that looks like this:</p>
  
  <pre><code>a: 0
  b: 100
  c: 101
  d: 11
  
  0 0 100 100 11 101
  </code></pre>
  
  <p>So this would decode: <code>aabbdc</code></p>
  
  <p>What decoding algorithm could I use that builds a Huffman tree and then uses it to decode the message? Sample code would be highly appreciated as well!</p>
  
  <p>Here is what I was thinking: </p>
  
  <ul>
  <li>create a lookup table that maps each symbol to its bits</li>
  <li>create a root node </li>
  <li>to build the tree, read in each bit from the encoded
  
  <ul>
  <li>if 0, create a left child. if 1, create a right child</li>
  <li>if space is reached, indicate a leaf somehow (null left and right pointers)
  
  <ul>
  <li>use the bits we read up until that space and see what this is the lookup table</li>
  <li>insert the character at that leaf</li>
  </ul></li>
  </ul></li>
  </ul>
  
  <p>then, I could just read in each bit again and have it move through the tree. when it hits a space, I would just return the character at the leaf it reached?</p>