title: Optimizing binary tree gives weird duplication errors
body: <p>I'm trying to implement an <em>optimize</em> method that should make a binary tree complete. My method does this by sorting the tree into an <code>int*</code>, then adding the midpoint of the array to a new array and recursing on each half.</p>
  
  <p>However, what the code's actually outputting is generating duplicates after descending to max depth along the left tree:</p>
  
  <pre><code>16 8 4 2 1 0 0 3 3 6 5 5 7 7 12 10 9 9 11 11 14 13 13 15 15 24 20 18 17 17 19 19
  </code></pre>
  
  <p>I can't for the life of my figure out why this is happening.</p>
  
  <p>My code:</p>
  
  <pre><code>// bth is "binary tree helper [method]"
  void bth_optimizearray(int* in, int* out, int min, int max, int* i) {
      // `in' is sorted, `out' should be optimized
      // `i' is the current index in `out'
  
      int len /* of subarray */ = max - min;
      if (len &lt; 1) {
          // empty subarray
          return;
      }
      if (len == 1) {
          // just add it
          out[(*i)++] = in[min];
      } // else
  
      // Add the midpoint
      int midpos = min + ((max - min) &gt;&gt; 1);
      out[(*i)++] = in[midpos];
      bth_optimizearray(in, out, min, midpos, i);
      bth_optimizearray(in, out, midpos + 1, max, i);
  }
  
  void bt_optimize(bintree *tree) {
      int treesize = bt_size(tree);
  
      int *ordered = malloc(treesize * sizeof(int));
      {
          int i = 0;
          void visit(node *n) {
              ordered[i++] = n -&gt; key;
          }
          bt_traverse(tree, INORDER, visit);
      }
  
  
      int *optimized = malloc(treesize * sizeof(int));
      {
          int *i = malloc(sizeof(int));
          (*i) = 0;
          bth_optimizearray(ordered, optimized, 0, treesize, i);
      }
  
      // Free all nodes (but don't call freetree; that would free the tree too)
      void freenode(node *n) {
          free(n);
      }
      bt_traverse(tree, INORDER, freenode);
      tree -&gt; root = NULL;
  
      {
          int i;
          for (i = 0; i &lt; treesize; i++) {
              printf("%d ", optimized[i]);
              bt_add(tree, optimized[i]);
          }
      }
  }
  </code></pre>
  
  <p>In this code, <code>bintree</code> is a <code>struct { node *root; int size; }</code> and all other methods work as they should.</p>
  
  <p>The full code is also <a href="https://github.com/wchargin/apcs" rel="nofollow">on GitHub</a>, but this <code>bt_optimize</code> method is only in the <code>optimize</code> branch.</p>
  
  <p><strong>This is C, not C++.</strong></p>
  
  <p>Any suggestions?</p>