Given a degenerate tree (a tree where all the nodes are less or greater than the root, perform 'in-place' rotations to construct a complete tree. Splicing may also be used, but prefer rotations.

An 'in-place' rotation means do NOT construct a new tree. Reassemble the degenerate tree to a complete tree using existing nodes. To verify the nodes are complete, create a degenerate tree with the number of nodes being a power of 2 + 1 for the root.

Test your algorithm on binary trees with nodes > 8.

Willing to paypal for a full complete program.