Optimizing binary tree gives weird duplication errors

Optimizing binary tree gives weird duplication errors

I'm trying to implement an optimize method that should make a binary tree
complete. My method does this by sorting the tree into an int*, then
adding the midpoint of the array to a new array and recursing on each
half.
However, what the code's actually outputting is generating duplicates
after descending to max depth along the left tree:
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
I can't for the life of my figure out why this is happening.
My 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 < 1) {
// empty subarray
return;
}
if (len == 1) {
// just add it
out[(*i)++] = in[min];
} // else
// Add the midpoint
int midpos = min + ((max - min) >> 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 -> 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 -> root = NULL;
{
int i;
for (i = 0; i < treesize; i++) {
printf("%d ", optimized[i]);
bt_add(tree, optimized[i]);
}
}
}
In this code, bintree is a struct { node *root; int size; } and all other
methods work as they should.
The full code is also on GitHub, but this bt_optimize method is only in
the optimize branch.
This is C, not C++.
Any suggestions?