$O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree
Let us denote by $L(x)$ the set of leaves in the subtree rooted at $x$. The idea is that the decision whether to switch the two children $x_1,x_2$ of $x$ depends only on $L(x_1),L(x_2)$, and depends on how many of the pairs $(a,b) \in L(x_1) \times L(x_2)$ satisfy $a &lt; b$ and how many satisfy $b &lt; a$.

If the sets $L(x_1),L(x_2)$ were available to you in their sorted forms, then you could count the number of pairs of each type by merging these sets and doing some accounting. This suggests a recursive algorithm which sorts the leaves using the merge sort strategy.

Details left to you.