Optimal leaf ordering of complete binary trees

Ordering a set of items so as to minimize the sum of distances between consecutive elements is a fundamental optimization problem occurring in many settings. While it is NPNP-hard in general, it becomes polynomially solvable if the set of feasible permutations is restricted to be compatible with a tree of bounded degree. We present a new algorithm for the elementary case of ordering the n   leaves of a binary tree with height logn+O(1)logn+O(1). Our algorithm requires O(n2logn)O(n2logn) time and O(n)O(n) space. While the running time is a log-factor away from being asymptotically optimal, the algorithm is conceptually simple, easy to implement, and highly practical. Its implementation requires little more than a few bit-manipulations.