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 NP NP -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) log n + O ( 1 ) . Our algorithm requires O(n2logn) O ( n 2 log n ) 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.
optimal leaf ordering permutations bit-manipulation algorithms