You might want to look into the Day-Stout-Warren algorithm, which is an O(n)-time, O(1)-space algorithm for reshaping an arbitrary binary search tree into a complete binary tree. Intuitively, the algorithm works as follows:
- Using tree rotations, convert the tree into a degenerate linked list.
- By applying selective rotations to the linked list, convert the list back into a completely balanced tree.
The beauty of this algorithm is that it runs in linear time and requires only constant memory overhead; in fact, it just reshapes the underlying tree, rather than creating a new tree and copying over the old data. It is also relatively simple to code up.
Hope this helps!