title: Huffman encoding in C
body: <p>I am trying to write a module which assigns huffman encoded words to the input symbols, but the given codes differ from what they should look like.</p>
  
  <p>For example, if I run it with following symbol probabilities:</p>
  
  <p>(1st column: probabilities; 2nd column: my huffman codes; 3rd column: correct huffman codes) </p>
  
  <p>0,25 --> 01  --> 10</p>
  
  <p>0,15 --> 101 --> 111</p>
  
  <p>0,15 --> 110 --> 110</p>
  
  <p>0,1 --> 1111 --> 010</p>
  
  <p>0,1 --> 000 --> 001</p>
  
  <p>0,05 --> 0010 --> 0110</p>
  
  <p>0,05 --> 0011 --> 0001</p>
  
  <p>0,05 --> 1000 --> 0000</p>
  
  <p>0,05 --> 1001 --> 01111</p>
  
  <p>0,05 --> 1110 --> 01110</p>
  
  <p>I think the problem might be caused in my function for <strong>generating huffman codes</strong>, since <em>strcat()</em> function's behaviour was initially not good for my idea, so I combined it with <em>strcat()</em>. Not sure if it is good that way tho.</p>
  
  <p>I am providing you with two functions responsible for codes assign, <strong>build_huffman_tree()</strong> and <strong>generate_huffman_tree()</strong>, hopefully you can help me out with this, and point out where the problem could be.</p>
  
  <p>Generate guffman tree:</p>
  
  <pre><code>void generate_huffman_tree(node *n, char *code){
  if(n-&gt;left== NULL &amp;&amp; n-&gt;right== NULL){
      SYMBOLS[code_counter] = n-&gt;symbol; // this 3 lines just store current code, not important
      CODES[code_counter] = strdup(code);
      code_counter += 1;
  }
  if(n-&gt;left!= NULL){
      char temp[100];
      strcpy(temp, code);
      strcat(temp, "0");
      generate_huffman_tree(n-&gt;left, temp);
  }
  if(n-&gt;right!= NULL){
      char temp[100];
      strcpy(temp, code);
      strcat(temp, "1");
      generate_huffman_tree(n-&gt;right, temp);
  }
  </code></pre>
  
  <p>Build Huffman tree:</p>
  
  <pre><code>node *build_huffman_tree(double *probabilities){
  
  int num_of_nodes = NUM_SYMBOLS;
  int num = NUM_SYMBOLS;
  
  // 1) Initialization: Create new node for every probability
  node *leafs = (node*) malloc(num_of_nodes*sizeof(node));
  int i;
  for(i=0; i&lt;num_of_nodes; i+=1){
      node c;
      c.probability= *(probability+ i);
      c.symbol= *(SYMBOLS + i);
      c.left= NULL;
      c.right= NULL;
      *(leafs+i) = c;
  }
  
  node *root= (node*) malloc(sizeof(node)); // Root node which will be returned
  
  while(num_of_nodes&gt; 1){
  
      // 2) Find 2 nodes with lowest probabilities
      node *min_n1= (node*)malloc(sizeof(node));
      node *min_n2 = (node*)malloc(sizeof(node));
  
      *min_n1 = *find_min_node(leafs, num, min_n1);
      leafs = remove_node(leafs, min_n1, num); 
      num -= 1;
  
      *min_n2= *find_min_node(leafs, num, min_n2);
      leafs = remove_node(leafs, min_n2, num);
      num -= 1;
  
      // 3) Create parent node, and assign 2 min nodes as its children
              // add parent node to leafs, while its children have been removed from leafs
      node *new_node = (node*) malloc(sizeof(node));
      new_node-&gt;probabilty= min_n1-&gt;probability + min_n2-&gt;probability;
      new_node-&gt;left= min_n1;
      new_node-&gt;right= min_n2;
  
      leafs = add_node(leafs, new_node, num);
      num += 1;
  
      num_of_nodes -= 1;
  
      root = new_node;
  }
  
  return root;
  </code></pre>
  
  <p>I have tested functions for finding 2 min nodes, removing and adding nodes to leafs structure, and it is proven to work fine, so I guess the problem should be something about this here.</p>