Extremal properties of the Colless balance index for rooted binary trees.

Measures of treebalance play an important role in various research areas, for example in phylogenetics. There they are for instance used to test whether an observed phylogenetic treediffers significantly from a treegenerated by the Yule model of speciation. One of the most popular indices in this regard is the Colless index, which measures the degree of balance for rooted binary trees. While many statistical properties of the Colless index(e.g. asymptotic results for its mean and variance under different models of speciation) have already been discussed in different contexts, we focus on its extremal properties. While it is relatively straightforward to characterize treeswith maximal Colless index, the analysis of the minimal value of the Colless indexand the characterization of treesthat achieve it, are much more involved. In this note, we therefore focus on the minimal value of the Colless indexfor any given number of leaves. We derive both a recursive formula for this minimal value, as well as an explicit expression, which shows a surprising connection between the Colless indexand the so-called Blancmange curve, a fractal curve that is also known as the Takagi curve. Moreover, we characterize two classes of treesthat have minimal Colless index, consisting of the set of so-called \emph{maximally balanced trees} and a class of treesthat we call \emph{greedy from the bottom trees}. Furthermore, we derive an upper bound for the number of treeswith minimal Colless indexby relating these treeswith treeswith minimal Sackin index(another well-studied indexof treebalance).