Extremal values of the Sackin tree balance index
Tree balance plays an important role in different research areas like theoretical computer science and mathematical phylogenetics. For example, it has long been known that under the Yule model, a pure birth process, imbalanced trees are more likely than balanced ones. Also, concerning ordered search trees, more balanced ones allow for more efficient data structuring than imbalanced ones. Therefore, different methods to measure the balance of trees were introduced. The Sackin index is one of the most frequently used measures for this purpose. In many contexts, statements about the minimal and maximal values of this index have been discussed, but formal proofs have only been provided for some of them, and only in the context of ordered binary (search) trees, not for general rooted trees. Moreover, while the number of trees with maximal Sackin index as well as the number of trees with minimal Sackin index when the number of leaves is a power of 2 are relatively easy to understand, the number of trees with minimal Sackin index for all other numbers of leaves has been completely unknown. In this manuscript, we extend the findings on trees with minimal and maximal Sackin indices from the literature on ordered trees and subsequently use our results to provide formulas to explicitly calculate the numbers of such trees. We also extend previous studies by analyzing the case when the underlying trees need not be binary. Finally, we use our results to contribute both to the phylogenetic as well as the computer scientific literature by using the new findings on Sackin minimal and maximal trees in order to derive formulas to calculate the number of both minimal and maximal phylogenetic trees as well as minimal and maximal ordered trees both in the binary and non-binary settings. All our results have been implemented in the Mathematica package SackinMinimizer, which has been made publicly available.
\section{Introduction}

Rooted trees, and binary ones in particular, play a fundamental role in many sciences as they can be used as a basis for search algorithms as well as, amongst others, as a model for evolution. In many cases where these trees occur, probability distributions are not always uniform concerning the degree of tree balance -- for instance, the Yule model in phylogenetics, which is a pure birth process, has long been known to lead to more imbalanced trees. A simple example is depicted in Figure \ref{yule}, where it can be seen that if all leaves of a tree with three leaves are equally likely to give rise to a new leaf, then two of them lead to the same (`imbalanced') tree, whereas the other possible tree (the `balanced' one) occurs only once. So in order to understand such processes and their possible bias towards imbalanced (or, in other cases, balanced) trees, one has to be able to classify the degree of balance in more detail than just in a binary way (`balanced' versus `imbalanced'). Therefore, various balance indices were introduced and have been used over the years, e.g.  \citep{blum,colless,cophenetic,sackin,steel2016}. One of the most frequently used and discussed such indices is the Sackin index \cite{sackin}.

\begin{figure}
	\centering
	\includegraphics[scale=.3]{yule.eps}

	\caption{The Yule process splits one leaf at a time uniformly at random to form a so-called cherry. It can be easily seen that this leads to a tree shape bias already when there are $n=4$ leaves. This is due to the fact that the only rooted binary tree on three leaves has two leaves that give rise to the tree on the left, which is considered `imbalanced' (it is the so-called caterpillar tree $T^{cat}_4$ on 4 leaves), whereas only one leaf leads to the so-called fully balanced tree $T_2^{bal}$ of height 2.
	}
	\label{yule}
\end{figure}

This index has been observed to have some very nice properties -- for instance, it has been stated that its maximum is achieved by the caterpillar tree (the tree with only one `cherry', i.e. with only one internal node whose two descendants are both leaves) and that, whenever the number $n$ of leaves equals a power of 2, i.e. when $n=2^k$ for some $k$, the minimum is achieved by the so-called fully balanced tree of height $k$, i.e. the tree in which all leaves have distance $k$ to the root  \cite{shao}. However, while these statements can be found in the literature, rigorous proofs of them are nowhere to be found. It is one aim of this manuscript to present proofs and thus to show that the Sackin index indeed has these properties. Note that these properties are desirable for a good tree balance index, as the caterpillar tree is normally perceived as very `imbalanced', whereas the fully balanced tree is normally referred to as very `balanced' (which explains its name). 

The idea of the Sackin index is to assign a small number to trees that are perceived as balanced and a high number to more imbalanced trees -- i.e. the higher the Sackin index, the more imbalanced the tree. So while some statements on the maximum of the Sackin index and its minimum in the special case $n=2^k$ can already be found in the literature, even if without proofs, little is known about trees with the minimum Sackin index for $n\neq 2^k$. Moreover, while it has long been known that the tree achieving this minimum in such cases need not be unique, the number of most balanced or most imbalanced trees has never been formally investigated. 

The main aim of this manuscript is to state and rigorously prove the following statements:

\begin{enumerate} 
\item For all leaf numbers $n$, the caterpillar is the unique tree with maximal Sackin index.
\item For $n \in \{2^m-1,2^m,2^m+1\}$ ($m \in \mathbb{N}$), the minimum of the Sackin index is achieved by a unique tree. If $n=2^m$, this tree is the fully balanced tree. 
\item If there is {\bf no} $m \in \mathbb{N}$ such that $n \in \{2^m-1,2^m,2^m+1\}$, then the minimum of the Sackin index is achieved by more than one tree, i.e. it is not unique. 
\end{enumerate}

Moreover, we will present an algorithm which constructs {\em all} trees with minimal Sackin index. Last but not least, we use this algorithm to derive a recursive formula for the number of such trees, which leads to a sequence that has only now been submitted to the Online Encyclopedia of Integer Sequences, i.e. it has not occurred elsewhere in the literature before. 




\section{Preliminaries}

Before we can start to discuss the Sackin tree balance index, we first need to introduce all concepts used in this manuscript. We start with trees: {\em Trees} are connected, acyclic graphs with node set $V$ and edge set $E$. We use $V^1$ in order to denote the set of {\em leaves} of a tree, i.e. the set of nodes of degree at most 1. All nodes $v$ that are not leaves, i.e. $v\in V\setminus V^1$, are called {\em internal nodes}. The set of internal nodes of a tree $T$ will be denoted by $\mathring{V}(T)$, or, whenever there is no ambiguity, simply by $\mathring{V}$. 

All trees $T$ in this manuscript are assumed to be {\em rooted} and {\em binary}, i.e. if they have an internal node at all, they have one root node $\rho$ of degree 2 and all other internal nodes have degree 3. The only rooted binary tree which does not have an internal node is the tree that consists of only one node and no edge -- in this special case, the only node is for technical reasons at the same time defined to be the root and the only leaf of the tree, so it is the only case where the root is not an internal node. Furthermore, for technical reasons all tree edges in this manuscript are implicitly assumed to be {\em directed} from the root to the leaves. Thus, for an edge $e=(u,v)$ of $T$, it makes sense to refer to $u$ as the {\em direct ancestor } or {\em parent } of $v$ (and $v$ as the {\em direct descendant} or {\em child} of $u$). More generally, when there is a directed path from $\rho$ to $v$ employing $u$, $u$ is called {\em ancestor} of $v$ (and $v$ descendant of $u$). Two leaves $v$ and $w$ are said to form a {\em cherry}, denoted by $[v,w]$, if $v$ and $w$ have the same parent, i.e. if there exists an internal node $u$ in $V$ such that $(u,v)$ and $(u,w)$ are edges in $E$. Note that every rooted binary tree with at least 2 leaves has at least one cherry.

Let $T$ be a rooted binary tree with root $\rho$, and let $x \in V^1$ be a leaf of $T$. Then we denote by $\delta_x$ the {\em depth} of $x$ in $T$, which is the number of edges on the unique shortest path from $\rho$ to $x$. Then, the {\em height} of $T$ is defined as $h(T)=\max\limits_{x \in V^1} \delta_x$, i.e. as the maximum of these distances. Note that whenever a leaf $v$ has maximal depth, i.e. whenever $h(T)=\delta_v$, $v$ is element of a cherry. This is due to the fact that if the other direct descendant, say $w$, of the parent of $v$, say $u$, was not a leaf but an internal node, it would have descending nodes of a greater depth than $\delta_v=\delta_w$, which would contradict the maximality of $\delta_v$. This is why in this manuscript, instead of considering both $v$ and $w$ separately as leaves of maximal depth, we sometimes refer to a cherry $[v,w]$ as {\em cherry of maximal depth}.

Moreover, recall that a rooted binary tree $T$ can be decomposed into its two maximal pending subtrees $T_a$ and $T_b$ rooted at the direct descendants $a$ and $b$ of $\rho$, and we denote this by $T=(T_a,T_b)$.

Last but not least, we want to introduce two particular trees which play a crucial role in this manuscript, namely the so-called {\em caterpillar tree} $T^{cat}_n$ and the so-called {\em fully balanced tree} $T^{bal}_k$, respectively. $T^{cat}_n$ denotes the unique rooted binary tree with $n$ leaves that has only one cherry, while $T^{bal}_k$ denotes the unique tree with $n=2^k$ leaves in which all leaves have depth precisely $k$. Whenever there is no ambiguity concerning $n$ or $k$, we also write $T^{cat}$ and $T^{bal}$ instead of $T^{cat}_n$ and $T^{bal}_k$. $T^{cat}_4$ and $T^{bal}_2$ are depicted in the bottom row of Figure \ref{yule}. Note that without loss of generality, the unique rooted binary tree with only one leaf, which consists of only one node and no edges, is defined to be $T^{cat}_1$, and it is thus the only caterpillar tree which does not contain a cherry. This tree is at the same time equal to $T^{bal}_0$, i.e. the fully balanced tree of height 0. This technicality enables  inductive proofs concerning $T^{cat} $ and $T^{bal}$ to start at $n=1$. 

We are now in a position to define the central concept of this manuscript, namely the Sackin index. As there are four different versions of this index to be found in the literature, we will define all of them first and subsequently investigate their respective relationships. Note, however, that we focus on the first two definitions in the present manuscript, which can be shown to be equivalent. Therefore, we will not refer to the other two definitions as Sackin index, but give them modified names instead.

\begin{definition}\label{sackin} \cite{cophenetic,steel2016}
The {\em Sackin index} of a rooted binary tree $T$ is defined as $\mathcal{S}(T)=\sum\limits_{u \in \mathring{V}(T)}n_u$, where $n_u$ denotes the number of leaves in the subtree of $T$ rooted at $u$. 
\end{definition}


Note that in the following, whenever we have for two trees $T_1$ and $T_2$ that $\mathcal{S}(T_1) < \mathcal{S}(T_2)$, then $T_1$ is called {\em more balanced} than $T_2$.


\begin{definition}\label{sackinalternative} \cite{cophenetic,steel2016}
The {\em Sackin index} of a rooted binary tree $T$ is defined as $\bar{\mathcal{S}}(T)=\sum\limits_{x \in V^1(T)}\delta_x$.
\end{definition}
 

\begin{definition}\citep[(3.10)]{steel2016}\label{mike}
The {\em Sackin index} of a rooted binary tree $T$ with root $\rho$ is defined as $\widetilde{\mathcal{S}}(T)=\sum\limits_{u \in V(T)\setminus\{\rho\}} n_u$, where $n_u$ denotes the number of leaves in the subtree of $T$ rooted at $u$.  
\end{definition}


Note that in the original paper by Sackin \citep{sackin}, in fact no index is defined at all. Instead, a sequence $b$ of  leaf depths is defined, which implies that Definition \ref{sackinalternative} is probably most closely related to what Sackin originally intended. However, we will show in Lemma \ref{equidefs} that the first three definitions are in fact equivalent, which does not hold for the following definition.


\begin{definition}\label{noah}\cite{noah}
The {\em normalized Sackin index} of a rooted binary tree $T$ with $n$ leaves is defined as $\widehat{\mathcal{S}}(T)=\frac{1}{n}\sum\limits_{x \in V^1(T)}\delta_x$, where $\delta_x$ denotes the depth of leaf $x$. 
\end{definition}

We now state a first lemma, which has already been partially stated (albeit without proof) in the literature  \cite{cophenetic}. 
 
 \begin{lemma}\label{equidefs} Definitions \ref{sackin}, \ref{sackinalternative} and \ref{mike} are equivalent, i.e. for any rooted binary tree $T$, we have $\mathcal{S}(T)=\bar{\mathcal{S}}(T)=\widetilde{\mathcal{S}}(T)$.
 \end{lemma}
 
 \begin{proof}

 
We first prove $\mathcal{S}(T)=\bar{\mathcal{S}}(T)$. Therefore, consider $\bar{\mathcal{S}}(T)=\sum\limits_{x \in V^1(T)}\delta_x$. Note that while $\delta_x$ by definition denotes the number of edges separating leaf $x$ from the root $\rho$ of $T$, this is equivalent to the number of internal nodes on the path from $\rho$ to $x$ (including $\rho$). This leads to: $$\bar{\mathcal{S}}(T)=\sum\limits_{x \in V^1(T)}\delta_x= \sum\limits_{x \in V^1(T)} |\{u \in \mathring{V}(T): \mbox{$u$ is an ancestor of $x$}\}|$$ 

$$ = |\{(x,u): \mbox{ $x \in V^1(T)$, $u \in \mathring{V}(T)$ and $u$ is an ancestor of $x$}\}|$$
$$ = |\{(x,u): \mbox{ $x \in V^1(T)$, $u \in \mathring{V}(T)$ and $x$ is a descendant of $u$}\}|$$
$$= \sum\limits_{u \in \mathring{V}(T)} |\{x \in V^1(T): \mbox{$x$ is a descendant of $u$}\}| =\sum\limits_{u \in \mathring{V}(T)} n_u=\mathcal{S}(T).$$
So now we have $\mathcal{S}(T)=\bar{\mathcal{S}}(T)$, and next we show that $\mathcal{S}(T)=\widetilde{\mathcal{S}}(T)$. We have $$\mathcal{S}(T) = \sum\limits_{u \in \mathring{V}(T)}n_u = \sum\limits_{u \in V(T)}n_u - \sum\limits_{x \in V^1(T)}n_x = \left(\sum\limits_{u \in V(T)}n_u \right)-n.$$ The latter equality is due to the fact that the only leaf belonging to a subtree rooted at a leaf is the leaf itself, so as we have $n$ leaves, this gives $n$ summands that contribute 1 to the sum. Now recall that $n_\rho = n$, so this leads to 
$$\mathcal{S}(T) =\left( \sum\limits_{u \in V(T)}n_u\right) -n_\rho = \sum\limits_{u \in V(T)\setminus\{\rho\}}n_u=\widetilde{\mathcal{S}}(T).$$ This completes the proof.


 \end{proof}
 
So because Definitions \ref{sackin}, \ref{sackinalternative} and \ref{mike} are equivalent, we do not have to distinguish between them and use them interchangeably. In fact, we will focus on in this manuscript mainly on the first two definitions. 

The normalized Sackin index, however, is a modification of the Sackin index whenever trees with different numbers of leaves are considered, because the ranking induced by the normalized Sackin index can even reverse the ranking induced by the Sackin index. For instance, consider the two trees $T_1=T_{37}^{cat}$, i.e.  the caterpillar tree with 37 leaves, and $T_2=T_{9}^{bal}$ the fully balanced tree with $2^9=512$ leaves. Then, it can easily be verified that we have $\mathcal{S}(T_1)=702 <  4608=\mathcal{S}(T_2)$, but $\widehat{\mathcal{S}}(T_1)\approx 18.97 > 9 =\widehat{\mathcal{S}}(T_2)$.\footnote{Note that these numbers can also be verified later on by using Propositions \ref{sackinCat} and \ref{sackinBal}.} In fact, this ranking modification is no artifact but the very purpose of the normalization: The effect that many leaves automatically may lead to more `imbalance' shall be eliminated. So in fact, $\mathcal{S}$ and $\widehat{\mathcal{S}}$ can be very different -- but only when different leaf numbers are considered! As long as $n$ is fixed, the induced rankings of the two indices are of course equivalent, and in this case, $\widehat{\mathcal{S}}$ is just $\mathcal{S}$ divided by the constant factor $n$. So when we discuss for instance the question how many trees with $n$ leaves exist that have maximal or minimal Sackin index, the answers for $\mathcal{S}$ and $\widehat{\mathcal{S}}$ will be the same. 

Therefore, as this is sufficient for the number of minima and maxima, we focus in this manuscript on Definitions \ref{sackin} and \ref{sackinalternative}.





\section{Results}
 
It is the main aim of this manuscript to fully characterize trees with minimal and maximal Sackin index, respectively, and to count such trees. We will start with the easier case, which is the maximum, before we consider the more involved and therefore more interesting case of the minimum.


\subsection{Maximally imbalanced trees / Minimally balanced trees} \par

In this section, we present an upper bound for $\mathcal{S}(T)$ and prove that this bound is tight as it is achieved by $T^{cat}$. Moreover, we will show that for all values of $n$, $T^{cat}_n$ is even the unique tree maximizing $\mathcal{S}$, i.e. the unique most imbalanced tree. This result has been stated in the literature before, e.g. in \cite{cophenetic}, but so far, a formal proof has not been stated anywhere. 

However, we start by establishing the upper bound on  $\mathcal{S}(T)$ before we can proceed as explained.

\begin{theorem}\label{maxsackin} Let $T$ be a rooted binary tree with $n$ leaves. Then, we have: $$\mathcal{S}(T)\leq \frac{n\cdot(n+1)}{2}-1.$$
\end{theorem}

Before we can prove this theorem, we need one more lemma.

\begin{lemma} \label{cherrydeleted}Let $T$ be a rooted binary tree with $n\geq 2$ leaves. Let $[u,v]$ be a cherry of maximal depth in $T$ with parent $w$, and let $\widetilde{T}$ be the tree derived by $T$ by deleting $u$ and $v$ as well as the edges $(w,u)$ and $(w,v)$. Then, for the Sackin indices of $T$ and $\widetilde{T}$ we have: $$ \mathcal{S}(T)=\mathcal{S}(\widetilde{T})+\delta_u+1.$$ 
\end{lemma}

\begin{proof} By Definition \ref{sackinalternative} and Lemma \ref{equidefs}, we have $\mathcal{S}(T)=\sum\limits_{x \in V^1}\delta_x$. By construction of $\widetilde{T}$, as $u$ and $v$ have been deleted and $w$ is a leaf in $\widetilde{T}$ but was an internal node in $T$, we have $\mathcal{S}(\widetilde{T})= \mathcal{S}(T)-\delta_u-\delta_v+\delta_w$. Note that as $u$ and $v$ form a cherry, we have $\delta_u=\delta_v$, and as $w$ was the parent of $u$ and $v$ in $T$, we have $\delta_w=\delta_u-1$. Thus, altogether we get $\mathcal{S}(\widetilde{T})= \mathcal{S}(T)-2\delta_u+(\delta_u-1)=\mathcal{S}(T)-\delta_u-1.$ Rearranging the latter term yields the desired result.
\end{proof}

Now we can use Lemma \ref{cherrydeleted} to prove Theorem \ref{maxsackin}.

\begin{proof}[Proof of Theorem \ref{maxsackin}] We prove the statement by induction on $n$. For $n=1$ there is only one tree $T$, which consists of only one leaf and has no internal nodes. Thus, by Definition \ref{sackin}, 
$\mathcal{S}(T)=0$ (as the sum in the definition of $\mathcal{S}(T)$ is empty). Moreover, $ 0=\frac{1\cdot2}{2}-1= \frac{n\cdot(n+1)}{2}-1$, which completes the base case of the induction.

Now we assume that for all trees with $n$ leaves the claim is proven and consider a tree $T$ with $n+1$ leaves. It remains to show $\mathcal{S}(T)\leq \frac{(n+1)(n+2)}{2}-1$. We construct a tree $\widetilde{T}$ by taking a cherry $[u,v]$ of $T$ of maximal depth $\delta_u=\delta_v$ and deleting $u$ and $v$ as well as the edges leading from $u$ and $v$ to their direct ancestor, say $w$. Thus, $\widetilde{T}$ has $(n+1)-2+1=n$ leaves, because leaves $u$ and $v$ have been deleted, but $w$, which is an internal node in $T$, is a leaf in $\widetilde{T}$. By Lemma \ref{cherrydeleted}, we  have $\mathcal{S}(T)=\mathcal{S}(\widetilde{T})+\delta_u+1$. We use the inductive hypothesis for $\widetilde{T}$ and derive:
$$\mathcal{S}(T)=\mathcal{S}(\widetilde{T})+\delta_u+1\leq \frac{n(n+1)}{2}-1 + \delta_u +1= \frac{n(n+1)}{2} + \delta_u . $$

Note that for all leaves, including those of maximal depth, their depths are bounded by one less than the number of leaves (cf. Lemma \ref{maxdepth} in the appendix). We use this to  conclude that $\delta_u \leq (n+1)-1=n$. Therefore, we have: 

$$\mathcal{S}(T)\leq \frac{n(n+1)}{2} + n =\frac{n^2+3n}{2}  = \frac{n^2+3n}{2}+\frac{2}{2} -1=\frac{(n+1)(n+2)}{2}-1.$$

 This completes the proof.
\end{proof}


We now consider the caterpillar tree $T^{cat}$ and show that it achieves the bound induced by Theorem \ref{maxsackin}, which implies that this bound is indeed tight.

\begin{proposition}\label{sackinCat} Let $T^{cat}=T^{cat}_n$ be the caterpillar tree with $n$ leaves. Then, we have: $\mathcal{S}(T^{cat})=\frac{n\cdot(n+1)}{2}-1$, i.e. $T^{cat}$ takes on the upper bound provided by Theorem \ref{maxsackin}.
\end{proposition}

\begin{proof} If $n=1$, $T^{cat}$ consists only of a leaf and has no internal nodes, so the sum over all internal nodes in Definition \ref{sackin} is empty, which implies $\mathcal{S}(T^{cat})=0$. On the other hand, in this case we have $\frac{n\cdot(n+1)}{2}-1= \frac{1\cdot(1+1)}{2}-1=0=\mathcal{S}(T^{cat})$. This completes the case $n=1$. 




Now consider the case $n\geq 2$. By Definition \ref{sackinalternative}, we have $\mathcal{S}(T^{cat})=\sum\limits_{x \in V^1(T^{cat})}\delta_x$. But note that in $T^{cat}$ there is precisely one leaf of depth 1, one leaf of depth 2 and so forth. In the unique cherry of $T^{cat}$, both leaves have depth $n-1$. So in total, we have: 
$$\mathcal{S}(T^{cat})=\sum\limits_{x \in V^1(T^{cat})}\delta_x = 1+2+ \ldots + (n-1) + (n-1) = \left(\sum\limits_{i=1}^{n-1}i \right) +(n-1).$$

Using the Gaussian sum, this leads to: 

$$\mathcal{S}(T^{cat})= \frac{(n-1)n}{2} +(n-1)=\frac{n^2-n}{2} +\frac{2n-2}{2}= \frac{n^2+n-2}{2}=\frac{n(n+1)}{2}-1.$$
This completes the proof.

\end{proof}


So by Proposition \ref{sackinCat} we know that the caterpillar tree assumes the maximal Sackin index for all possible leaf numbers $n$. However, Proposition \ref{sackinCat} does not make a statement about whether there exist other trees with maximal Sackin index. We will now show that this is not the case, i.e. the caterpillar tree is the unique most imbalanced tree.

\begin{theorem}\label{catisunique} Let $n \in \mathbb{N}_{\geq 1}$. Then, there is only one rooted binary tree $T$ with maximal Sackin index, i.e. with $\mathcal{S}(T)= \frac{n(n+1)}{2}-1$, and we have $T=T^{cat}$. Thus, the caterpillar tree is the unique tree maximizing the Sackin index.
\end{theorem}

Before we can prove this theorem, we need one more lemma.

\begin{lemma}\label{optStandardDecomp} Let $T$ be a rooted binary tree with $n$ leaves and with maximal (or minimal) Sackin index for $n$, i.e. for all other trees $\widetilde{T}$ with $n$ leaves we have $\mathcal{S}(T) \geq \mathcal{S}(\widetilde{T})$ (or $\mathcal{S}(T) \leq \mathcal{S}(\widetilde{T})$, respectively). Let $T=(T_a,T_b)$ be the standard decomposition of $T$ into its two maximal pending subtrees $T_a$ and $T_b$, with $n_a$ and $n_b$ leaves, respectively. Then, $\mathcal{S}(T_a)$ and $\mathcal{S}(T_b)$ are maximal (minimal) for $n_a$ and $n_b$, respectively.
\end{lemma}

\begin{proof} We consider the case of maximality. The case of minimality can be shown analogously. Now, assume that $\mathcal{S}(T)$ is maximal. Using Definition \ref{sackin}, it is easy to see that $\mathcal{S}(T)=\mathcal{S}(T_a)+\mathcal{S}(T_b)+n$. 
Now assume that $\mathcal{S}(T_a)$ is not maximal, i.e. there is a tree $\widehat{T}$ with $n_a$ leaves such that $\mathcal{S}(\widehat{T})>\mathcal{S}(T_a)$. Then we can construct a tree $\widetilde{T}$ on $n$ leaves such that $\widetilde{T}=(\widehat{T},T_b)$, i.e. we replace $T_a$ in $T$ by $\widehat{T}$ to derive $\widetilde{T}$. Now for $\widetilde{T}$ we have by Definition \ref{sackin}: $\mathcal{S}(\widetilde{T}) =  \mathcal{S}(\widehat{T}) + \mathcal{S}(T_b)+n > \mathcal{S}(T_a)+\mathcal{S}(T_b)+n=\mathcal{S}(T)$. This contradicts the maximality of $\mathcal{S}(T)$, which implies that the assumption was wrong. So $\mathcal{S}(T_a)$ has to be maximal, and analogously, $\mathcal{S}(T_b)$ has to be maximal, too. This completes the proof.
\end{proof}

We are now in a position to prove Theorem \ref{catisunique}.

\begin{proof}[Proof of Theorem \ref{catisunique}] By Proposition \ref{sackinCat}, we have $\mathcal{S}(T^{cat})= \frac{n(n+1)}{2}-1$, which is maximal according to Theorem \ref{maxsackin}. Now assume there is another tree $T$ with $\mathcal{S}(T)= \frac{n(n+1)}{2}-1$. We prove by induction on $n$ that then $T$ must equal $T^{cat}$. For $n=1$, there is only one rooted binary tree, which is by definition a caterpillar, so there is nothing to show. This completes the base case of the induction. 

Next we assume that the statement is already proven for all leaf numbers up to $n-1$ and consider a rooted binary tree $T$ with $n$ leaves and $\mathcal{S}(T)= \frac{n(n+1)}{2}-1$. Note that without loss of generality, $n\geq 2$ (else we consider the base case of the induction again). As $n\geq 2$, we can consider the standard decomposition of $T$ into its two maximal pending subtrees $T_a$ and $T_b$ with $n_a$ and $n_b$ leaves, respectively. Note that $n=n_a+n_b$ and that we may assume without loss of generality that $n_a\geq n_b$. Moreover, recall that we have $\mathcal{S}(T)=\mathcal{S}(T_a)+\mathcal{S}(T_b)+n$ by Definition \ref{sackin}. By Lemma \ref{optStandardDecomp}, $\mathcal{S}(T_a)$ and $\mathcal{S}(T_b)$ are also maximal (as $\mathcal{S}(T)$ is maximal), and thus, by induction, $T_a$ and $T_b$ are both caterpillars. 

So we can conclude by Proposition \ref{sackinCat} that $\mathcal{S}(T_a)= \frac{n_a(n_a+1)}{2}-1$ and $\mathcal{S}(T_b)= \frac{n_b(n_b+1)}{2}-1$, which gives $$\mathcal{S}(T)=\mathcal{S}(T_a)+\mathcal{S}(T_b)+n = \frac{n_a(n_a+1)}{2}-1+\frac{n_b(n_b+1)}{2}-1+n. $$
Using $n_b=n-n_a$ and expanding all terms leads to \begin{equation}\label{Sfterm}\mathcal{S}(T)= \frac{1}{2}n^2-n\cdot n_a+n_a^2+\frac{3}{2}n-2.\end{equation} 
We now consider this term as a function of $n_a$ and analyze the values of this function  more in-depth, i.e. we consider $f(n_a)=\frac{1}{2}n^2-n\cdot n_a+n_a^2+\frac{3}{2}n-2$. Note that as we have $n_a+n_b=n$ and as we assume without loss of generality that $n_a \geq n_b$, we have $n_a\geq \lceil\frac{n}{2}\rceil$ (and $n_b\leq \lfloor\frac{n}{2}\rfloor$). Moreover, note that $n_a\leq n-1$, because $n_b\geq 1$. 

We now show that for $n_a \in \left\{\lceil\frac{n}{2}\rceil,\ldots, n-1\right\}$, $f(n_a)$ is strictly  monotonically increasing. Therefore, consider the first derivative of $f$: $f'(n_a)= -n+2n_a$, which equals 0 precisely if $n_a=\frac{n}{2}$ and is strictly larger than 0 for all $n_a>\frac{n}{2}$. In total, this implies that we have a unique minimum at $\frac{n}{2}$ and that $f$ strictly increases after $n_a$ passes this minimum.


So indeed, $f$ is strictly monotonically increasing on $\left\{\lceil\frac{n}{2}\rceil,\ldots, n-1\right\}$, which implies that its unique maximum is assumed at $n-1$. This implies that $\mathcal{S}(T)$ is maximal if $n_a=n-1$, i.e. if  $T_a$ is the caterpillar on $n-1$ leaves. Using $n=n_a+n_b$, this implies that $n_b=1$. So in total, $T_a$ is a caterpillar on $n-1$ leaves and $T_b$ consists of only one leaf. This implies that $T$ is a caterpillar on $n$ leaves, which completes the proof.
\end{proof}

\par

In total, we conclude that the bound provided by Theorem \ref{maxsackin} is tight, as Proposition \ref{sackinCat} implies that for each $n$, the caterpillar reaches this bound, and by Theorem \ref{catisunique} we know that the caterpillar is unique with this property, i.e. the caterpillar is the unique tree with maximal Sackin index. So for all $n$, there is precisely one tree with maximal Sackin index. We will show in the following section that this is different for the minimal Sackin index, as it can be taken on by various trees (depending on $n$). 

We conclude this section by noting that the sequence $(a_n)_{n \in \mathbb{N}_{\geq 1}}$ with $a_n=\mathcal{S}(T^{cat}_n)=\frac{n(n+1)}{2}-1$ for $i \in \mathbb{N}\geq 1$, which starts with 2, 5, 9, 14, 20, 27, 35, 44, 54, 65, 77, 90, 104, 119, 135, 152, 170, 189, 209, $\ldots$, corresponds to sequence A000096 in the Online Encyclopedia of Integer Sequences OEIS \cite[Sequence A000096]{OEIS}, when the index is shifted by 1 (i.e. the $i$\textsuperscript{th} entry of the OEIS sequence corresponds to the $(i+1)$\textsuperscript{st} entry of our sequence). So this sequence has already occurred in other contexts, which might link the maximal Sackin index to other areas of research like the study of prime polyominoes or the traveling salesman polytope \cite[Sequence A000096]{OEIS}.

\subsection{Maximally balanced trees} \par

In this section, it is our aim to achieve the same results for trees with minimal Sackin index that the previous section stated for trees with maximal Sackin index. In particular, we want to find a tight bound for the minimal Sackin index and we want to characterize the trees that achieve it. However, it turns out that -- as opposed to the previous section -- the case of minimality is far more involved. In fact, depending on the number $n$ of leaves, the tree with the minimal Sackin index need not be unique, so counting these trees is more complicated. Note that while examples for the fact that the Sackin index can be minimized by more than one tree have been presented before, e.g. in \cite{cophenetic}, see Figure \ref{6taxabalanced}, it has so far not been investigated for which values of $n$ this happens and how many minima there are. It is the main aim of this section to present an algorithm that is able to systematically generate all trees with minimal Sackin index and that therefore also leads to a recursive formula for counting such trees.

\begin{figure}
	\centering
	\includegraphics[scale=.4]{sackin6taxamin.eps}

	\caption{Two trees with $n=6$ leaves which both have Sackin index 16, which can be shown to be minimal for $n=6$.
	}
	\label{6taxabalanced}
\end{figure}

However, we start as in the previous section and state the first result, which provides a lower bound on the Sackin index of trees with $n$ leaves. 

\begin{theorem}\label{minsackin} Let $T$ be a rooted binary tree with $n$ leaves. Let $k=\lceil \log_2(n)\rceil$. Then, $\mathcal{S}(T) \geq -2^k+n(k+1)$. \end{theorem}

\begin{proof} Note that as $k = \lceil \log_2(n)\rceil$, we have $n\leq 2^k$, and $k$ is the smallest integer with this property. In other words, we have $k=\min\{\widehat{k}: n\leq 2^{\widehat{k}}\}$. 
We now prove the theorem by induction on $n$. For $n=1$, we have $k=0$, as $1 \leq 2^0$. So the term on the right hand side equals $-2^k+n(k+1) = -2^0+1\cdot (0+1)=-1+1=0$. As $\mathcal{S}(T) \geq 0$ for all $T$ by the definition of the Sackin index, this condition is clearly fulfilled. This completes the base case of the induction.

Let us now consider a tree $T$ with $n$ leaves. We assume that for all trees with $n-1$ leaves, the statement already holds, and we have to show that now $\mathcal{S}(T) \geq -2^k+n(k+1)$. We consider a cherry $[u,v]$ of $T$ of maximal depth $\delta_u=\delta_v$ and its parent node $w$. We consider tree $\widetilde{T}$ which we derive from $T$ as follows: We remove leaves $u$ and $v$ together with the edges $(w,u)$ and $(w,v)$. By Lemma \ref{cherrydeleted}, this leads to $\mathcal{S}(T) =\mathcal{S}(\widetilde{T})+ \delta_u +1$. Note that as $\widetilde{T}$ was derived from $T$ by deleting two leaves ($u$ and $v$) but creating one new one ($w$), for the number of leaves $\widetilde{n}$ of $\widetilde{T}$ we have $\widetilde{n}=n-1$. Let $\widetilde{k} = \lceil \log_2(\widetilde{n})\rceil=\min\{\widehat{k}: \widetilde{n}\leq 2^{\widehat{k}}\}$. Then there are two cases: either $\widetilde{k}=k$ or $\widetilde{k}=k-1$, as the deletion of one leaf might result in a smaller power of 2 being necessary to cover all leaves, but it cannot decrease by more than 1. 

\begin{enumerate} \item
We first consider the case $\widetilde{k}=k-1$. This case implies that the deletion of one leaf leads to a smaller power of 2 necessary to cover $n-1$ than $n$. This is precisely the case if $n=2^{k-1}+1>2^{k-1}=2^{\widetilde{k}}$, because then $n-1=2^{k-1}=2^{\widetilde{k}}$, and in this case, the smallest $\widehat{k}$ such that $2^{\widehat{k}}$ is at least $n$ would be $(k-1)+1=k$. 

So now we have $\mathcal{S}(T) =\mathcal{S}(\widetilde{T})+ \delta_u +1$ and, by the inductive hypothesis, $\mathcal{S}(\widetilde{T}) \geq -2^{\widetilde{k}}+(n-1)(\widetilde{k}+1)= -2^{k-1}+2^{k-1} ((k-1)+1)=-2^{k-1}+2^{k-1}k= 2^{k-1}(k-1)$. Combining these two observations, we derive 

\begin{equation} \label{case2} \mathcal{S}(T) = \mathcal{S}(\widetilde{T})+ \delta_u +1 \geq 2^{k-1}(k-1) + \delta_u + 1.\end{equation}

It remains to show that the latter term in Equation \ref{case2} is at least $-2^k+n(k+1)$. Note that $\delta_u$ is the maximal depth of $T$, because $u$ is an element of a cherry of maximal depth. It can easily be seen that as $n=2^{k-1}+1$, we have $\delta_u \geq k$ (see Lemma \ref{maxdepthleaf} in the appendix). So this leads to: 

\begin{equation}\label{deltabound} \delta_u \geq k =
-2^k+2^{k-1}\left( k+1-(k-1)\right)+k\end{equation}

Now we combine Equations (\ref{case2}) and (\ref{deltabound}) to derive the desired result:



$$\mathcal{S}(T) \geq 2^{k-1}(k-1) -2^k+2^{k-1}\left( k+1-(k-1)\right)+k+1=-2^k+n(k+1).$$


This completes the proof of this case.

\item Now we consider the case $\widetilde{k}=k$. In this case, we have $n \leq 2^k$ and $n-1 > 2^{k-1}$. This implies that $n>2^{k-1}+1$ and thus, again by Lemma \ref{maxdepthleaf}, we have $\delta_u \geq k$. Moreover, we still have $\mathcal{S}(T)=\mathcal{S}(\widetilde{T})+\delta_u+1$, and by the inductive hypothesis we have that $\mathcal{S}(\widetilde{T}) \geq -2^k+(n-1) \cdot k +(n-1)$. Combining all these observations leads to:


\begin{equation} \label{case1} \mathcal{S}(T) =\mathcal{S}(\widetilde{T})+\delta_u+1 \geq -2^k+(n-1) \cdot k +(n-1) +k  +1 =-2^k+n(k+1).
\end{equation}



This completes the proof.

\end{enumerate}
\end{proof}




We now consider the so-called fully balanced tree $T^{bal}_k$ and show that its name is indeed justified in the sense that it achieves the bound induced by Theorem \ref{minsackin} whenever it is defined, i.e. whenever the number $n$ of leaves equals $2^k$.

\begin{proposition}\label{sackinBal} Let $T^{bal}_k$ be the fully balanced tree of height $k$ with $n=2^k$ leaves. Then, we have: $S(T^{bal}_k)=k\cdot 2^k$.
\end{proposition}

\begin{proof} By Definition \ref{sackinalternative} and Lemma \ref{equidefs}, we have $S(T^{bal}_k)=\sum\limits_{x \in {V^1}(T)}\delta_x$. Note that $|V^1|=n=2^k$ and that each of the $2^k$ leaves in $T^{bal}_k$ has depth $k$. This leads to $S(T^{bal}_k)=k\cdot 2^k$, which completes the proof.
\end{proof}

\begin{corollary}\label{balmaxbal} Let $T^{bal}_k$ be the fully balanced tree of level $k$ with $n=2^k$ leaves. Then, $T^{bal}_k$ is maximally balanced, i.e. for all rooted binary trees $T$ with $n=2^k$ leaves we have: $\mathcal{S}(T)\geq S(T^{bal}_k)$.
\end{corollary}

\begin{proof} By Proposition \ref{sackinBal} we have $S(T^{bal}_k)=k\cdot 2^k$. Let $T$ be a rooted binary tree with $n=2^k$ leaves. By Theorem \ref{minsackin}, we then have: 

$$\mathcal{S}(T) \geq -2^k+n(k+1) = -2^k+\underbrace{2^k}_{=n}(k+1) = -2^k+2^k\cdot k+2^k = 2^k\cdot k = \mathcal{S}(T^{bal}).$$ This completes the proof.
\end{proof}


Corollary \ref{balmaxbal} shows that when $n=2^k$, the bound provided by Theorem \ref{minsackin} is tight, i.e. there is in fact a tree that obtains the lower bound of the Sackin index, but it does not consider any other values of $n$. We next want to show that the bound is in fact tight for all $n$, even if $n\neq 2^k$, and we will present an explicit construction to find such maximally balanced trees, i.e. trees with a minimal Sackin index. Therefore, we need the following Algorithm \ref{alg1}. The high-level idea of this algorithm is to start with a maximally balanced tree (and we know already by Corollary \ref{balmaxbal} that $T_k^{bal}$ has that property), possibly of too many leaves, and then deleting leaves, one at a time, in a way that keeps the balance maximal. In particular, we will show that this can be achieved by deleting the leaves of a cherry of maximum depth. 
\par \vspace{0.5cm}



\begin{algorithm}[H]\label{alg1}
\KwIn{number $n$ of leaves}

 \KwOut{tree $T$ with $n$ leaves and $\mathcal{S}(T)$ minimal. }
 Initialization: 
 $k:=\lceil \log_2(n) \rceil$;  $T:=T^{bal}_k$; $\widehat{n}:=2^k$\; 
 
 \While{$\widehat{n} > n$ }{
  Find a cherry $[u,v]$ of maximal depth in $T$ and call its parent node $w$\; 
  Delete leaves $u$ and $v$ and edges $(w,u)$ and $(w,v)$ from $T$\;
  $\widehat{n}:=\widehat{n}-1$\;
  
  
  
 }
 \KwRet{$T$}
 \caption{Construction of maximally balanced rooted binary trees with $n$ leaves}
\end{algorithm}

 \begin{theorem}\label{thm:alg}
Let $n \in \mathbb{N}$ and let $k=\lceil \log_2(n) \rceil$. Then, Algorithm \ref{alg1} returns a tree $T$ with $\mathcal{S}(T)=-2^k+n(k+1)$. So Algorithm \ref{alg1} finds a tree with minimal  $\mathcal{S}(T)$; i.e. a maximally balanced tree.
 \end{theorem}
 
 \begin{proof}  Note that as before,  $k=\lceil \log_2(n) \rceil$ implies $k=\min\{\widetilde{k}: n \leq 2^{\widetilde{k}}\}$. We now distinguish two cases. If $n=2^k$, the algorithm does not enter the while-loop, as $\widehat{n}=n$. Therefore, the algorithm, returns the tree from the initialization step, which is the fully balanced tree $T^{bal}_k$. We know by Proposition \ref{sackinBal} that $S(T^{bal}_k)=k\cdot 2^k$, which is minimal by Corollary \ref{balmaxbal}. Moreover, $S(T^{bal}_k)=k\cdot 2^k= -2^k+ (k\cdot 2^k) +2^k =-2^k+2^k(k+1)=  -2^k+n(k+1).$ Here, the last equality is due to $n=2^k$. This completes the proof of this case.
 
Now let us consider the case where $n<2^k$. Note that we additionally have $n > 2^{k-1}$, because otherwise $k$ would not be minimal with the property $n\leq 2^k$. 

We start with $T^{bal}_k$ employing $\widehat{n}=2^k$ leaves, and the while-loop reduces $\widehat{n}$ in each step by 1 and repeats that as long as $\widehat{n}>n$. So in total, this step is repeated $2^k-n$ times. 

In each step, the leaves of a cherry $[u,v]$ of maximal depth are deleted along with their respective pending edges. Let us call the tree before performing this step $T$ and the resulting tree after the cherry deletion $\widetilde{T}$. Note that the direct ancestor of $u$ and $v$ in $T$, say $w$, is a leaf in $\widetilde{T}$. So in total, $\widetilde{T}$ has one leaf less than $T$. So after repeating this step $2^k-n$ times, we end up with a tree with $2^k-(2^k-n)=n$ leaves.

Moreover, as $[u,v]$ is a cherry of maximal depth, we know from Lemma \ref{cherrydeleted} that $\mathcal{S}(\widetilde{T})=\mathcal{S}(T)-\delta_u-1$. So each time we run through the while-loop, the Sackin index gets reduced by $(\delta_u+1)$.

It is now crucial to note that the value of $\delta_u$ does not change throughout the procedure! This is because we start with $\widehat{n}=2^k$ and stop when $\widehat{n}=n>2^{k-1}$, and we always take a cherry of maximal depth. In the beginning, we have $\frac{2^k}{2}=2^{k-1}$ such cherries in $T^{bal}_k$ to choose from, and in each step, one of those cherries gets replaced by a leaf. So as long as one of the original cherries of $T^{bal}_k$ remains unchanged, the value of $\delta_u$ does not change. But if all of the original cherries were replaced by a leaf, we would end up with $T^{bal}_{k-1}$ and thus with $\widehat{n}=2^{k-1}<n$, which by definition of Algorithm \ref{alg1} cannot happen. 

So $\delta_u$ is the same each time we run the while-loop, and thus, in total, on the way from $T^{bal}_k$ to the final tree $T$, the Sackin index gets reduced by $(2^k-n)(\delta_u+1)$. So we have $\mathcal{S}(T)=S(T^{bal}_k)-(2^k-n)(\delta_u+1)$. Now note that the depth $\delta_u$ of a leaf of maximal depth in $T^{bal}_k$ is precisely $k$. In total, using Proposition \ref{sackinBal}, this leads to: 
 
$$\mathcal{S}(T)=\mathcal{S}(T^{bal}_k)-(2^k-n)(\delta_u+1) =k\cdot 2^k - (2^k-n)(k+1) =-2^k+n(k+1).$$ This completes the proof. 
\end{proof}

\begin{remark} Note that Theorem \ref{thm:alg} proves that the bound provided by Theorem \ref{minsackin} is in fact tight for all $n$, and that Algorithm \ref{alg1} even provides a way of finding a maximally balanced tree for all $n$. The tight bound also implies that the sequence of minimal values of the Sackin index, starting at $n=1$, is $1,2,5,8,12,16,20,24,\ldots$ This corresponds to Sequence A003314 in the Online Encyclopedia of Integer Sequences OEIS \cite[Sequence A003314]{OEIS}, which is also often referred to as binary entropy function. 
\end{remark}

Note that by Theorem \ref{thm:alg}, it is also clear why trees with minimal Sackin index are not necessarily unique with this property: In the while-loop, any cherry of maximum depth in a maximally balanced tree with $\widehat{n}$ leaves will provide a maximally balanced tree with $\widehat{n}-1$ leaves -- so the choice of the particular cherry of maximum depth might result in different trees.


\begin{example} Consider the two trees $T_1$ and $T_2$ with $n=6$ leaves as depicted in Figure \ref{6taxabalanced}. These two trees both have Sackin index 16: $\mathcal{S}(T_1)=2+2+3+3+6=16=2+2+2+4+6=\mathcal{S}(T_2)$. Let $k=\lceil \log_2(6) \rceil=3$. 

Now it is easy to see that $\mathcal{S}(T_1)=\mathcal{S}(T_2)=16$ is indeed minimal, as for $n=6$ we have by Theorem \ref{minsackin} that $\mathcal{S}(T) \geq -2^k+n(k+1)=-2^3+6(3+1)=16$. And the reason why we have two maximally balanced trees with 6 leaves is due to the (unique) maximally balanced tree $T$ with 7 leaves (see Figure \ref{algfig}). In this tree we have three cherries of maximal depth. However, due to symmetry it does not make a difference if we choose either one of the two underbraced ones in the while-loop of Algorithm \ref{alg1}, because the resulting tree is in any case $T_1$. But if we choose the third cherry of maximal depth, the resulting tree is $T_2$. 

\end{example}

\begin{figure}
	\centering
	\includegraphics[scale=.4]{algorithm1.eps}

	\caption{Illustration of Algorithm \ref{alg1}: For $n=5$, we consider $k=\lceil \log_2(5)\rceil =3 $ and thus start at $2^3=8$ leaves. Then, one by one, we delete a cherry of maximal depth until we reach $n=5$ leaves. In this case, when we go from 7 to 6, the particular choice of such a cherry can lead to different trees. \\Note that alternatively, instead of going from $2^k$ leaves down to $n$, one could start at $2^{k-1}$ leaves and go up to $n$, i.e. the arrows in the figure could be reversed. 
	}
	\label{algfig}
\end{figure}


\begin{remark} It can be easily seen that instead of using the top-down principle as presented in Algorithm \ref{alg1}, it is equivalent to use a bottom-up principle. In particular, instead of constructing a maximally balanced tree with $n$ leaves according to the Sackin index by starting at $T_k^{bal}$ for $k= \lceil \log_2(n) \rceil$ and deleting cherries of maximal depth, one could instead start at $T_{k-1}^{bal}$ and replace leaves of minimal depth with a cherry. Figure \ref{algfig} illustrates this as all arrows could simply be reversed. However, as both algorithms can easily be shown to lead to equivalent results, we omit the proof for the second algorithm. 
\end{remark}

We will now consider the set of trees of minimal Sackin index, i.e. the maximally balanced ones according to this index. As we will show, if the number of leaves is a power of 2, i.e. $n=2^k$, the maximally balanced tree is unique, namely $T_k^{bal}$. This has frequently been observed in the literature (cf. \citep{heard,shao}), but to the best of our knowledge, no formal proof has been presented so far. Moreover, no statement on the number of maximally balanced trees for leaf numbers that are not a power of 2 has been made so far. We will provide a recursive formula to calculate this number in the following. But before we can do that, we have to consider the easier case with $n=2^k$. 

\begin{theorem}\label{TkbalUNIQUE} Let $n=2^k$ for some $k\in \mathbb{N}$. Then, $T_k^{bal}$ is the {\bf unique} tree with minimal Sackin index, i.e. for any other tree $T$ with $n=2^k$ leaves we have $\mathcal{S}(T)>S(T_k^{bal})$.
\end{theorem}

\begin{proof} We know by Corollary \ref{balmaxbal} that $T_k^{bal}$ has minimum Sackin index, i.e. $S(T_k^{bal})=k\cdot2^k$. So all that remains to be shown is that $T_k^{bal}$ is unique with this property. We prove this statement by induction on $k$. For $k\leq 1$ there is nothing to show as then there is only one tree to consider, which gives therefore of course the unique minimum. 
Now we assume the statement holds for $k-1$ and we consider a tree $T$ with $n=2^k$ leaves and $\mathcal{S}(T)$ minimal, i.e. by Proposition \ref{sackinBal} and Corollary \ref{balmaxbal} we have $\mathcal{S}(T)=k\cdot 2^k$. We have to show that $T=T_k^{bal}$. 

Let $T=(T_a,T_b)$ be the standard decomposition of $T$ into its two maximal pending subtrees $T_a$ and $T_b$ with leaf numbers $n_a$ and $n_b$, respectively, such that $n=n_a+n_b$. Without loss of generality, we may assume $n_a \geq n_b$, i.e. $n_a \geq \frac{n}{2}$. Note that as $T$ has minimum Sackin index and as by definition we have $\mathcal{S}(T)=
\mathcal{S}(T_a)+\mathcal{S}(T_b)+n$, by Lemma \ref{optStandardDecomp}, $\mathcal{S}(T_a)$ and $\mathcal{S}(T_b)$ must be minimal, too. We now distinguish two cases.

\begin{enumerate}
\item $n_a=n_b=\frac{n}{2}=2^{k-1}$. In this case, we know by the inductive hypothesis that $T_a$ and $T_b$ must equal $T_{k-1}^{bal}$, as this is the unique tree with minimum Sackin index and $ 2^{k-1}$ leaves. So $T=(T_a,T_b)$, and $T_a$ and $T_b$ are both equal to $T_{k-1}^{bal}$, which implies $T=T_k^{bal}$. This completes the proof of this case.

\item $n_a > n_b$, i.e. $n_a > \frac{n}{2}=2^{k-1}$. Then, there exists an $s \in \mathbb{N}$, $s\geq 1$, such that $n_a=\frac{n}{2}+s=2^{k-1}+s$. Due to $2^k=n=n_a+n_b=2^{k-1}+s+n_b$ we conclude $2^k-2^{k-1}=s+n_b$ and thus $n_b=2^{k-1}-s$. 

As in the first case we have $\mathcal{S}(T)=\mathcal{S}(T_a)+\mathcal{S}(T_b)+n$ with $\mathcal{S}(T_a)$ and $\mathcal{S}(T_b)$ minimal. By Theorems \ref{minsackin} and \ref{thm:alg} we conclude that $\mathcal{S}(T_a)=-2^{k_a}+n_a\cdot(k_a+1)$ and $\mathcal{S}(T_b)=-2^{k_b}+n_b\cdot(k_b+1)$, where $k_a=\lceil \log_2(n_a) \rceil$ and $k_b=\lceil \log_2(n_b) \rceil$. Now, note that due to $n_a=2^{k-1}+s$ and $n_b=2^{k-1}-s$ for $s \geq 1$ we have: 
\begin{itemize}
\item $k_a=k$ (as $n_a> 2^{k-1}$ and $n_a <n=2^k$) and
\item $ 0 \leq k_b \leq k-1$ (as $n_b < 2^{k-1}$) and 
\item $s \leq 2^{k-1}-1$, because as $n_b \geq 1$ (otherwise, if $n<2$, we would be in the base case of the induction, so now we have $n\geq 2$ and therefore $n_b\geq 1$), we have $n_a \leq n-1$. This implies $\frac{n}{2}+s \leq n-1$, which yields $s \leq \frac{n}{2}-1$. Using $n=2^k$, we derive $s\leq 2^{k-1}-1$.
\end{itemize}

So, in total we get: $$\mathcal{S}(T)=\mathcal{S}(T_a)+\mathcal{S}(T_b)+n=-2^{k_a}+n_a(k_a+1)-2^{k_b}+n_b(k_b+1)+2^k.$$ Using $k_a=k$, $n_a=2^{k-1}+s$ and $n_b=2^{k-1}-s$, we get: $$\mathcal{S}(T)=-2^k +(2^{k-1}+s) \cdot (k+1)-2^{k_b}+(2^{k-1}-s)\cdot(k_b+1)+2^k$$
$$= 2^{k-1}(k+k_b)+s(k-k_b)+2^k-2^{k_b}. $$ Using $k_b =\lceil \log_2(n_b)\rceil= \lceil \log_2(2^{k-1}-s)\rceil$, this leads to: \begin{equation}\label{STbal}\mathcal{S}(T)= 2^{k-1}\cdot (k+ \lceil \log_2(2^{k-1}-s)\rceil) + s(k- \lceil \log_2(2^{k-1}-s)\rceil)+2^k-2^{ \lceil \log_2(2^{k-1}-s)\rceil}. \end{equation}

We now consider the term $k_b=\lceil \log_2(2^{k-1}-s)\rceil$ in more detail. For a fixed value of $k$, this term depends only on $s$, so we will refer to it as $k_b(s)$. $k_b(s)$ can assume values ranging from $0=k-k$ (if $n_b=1$, i.e. if $T_b$ consists only of one leaf, which is the case when $s=2^{k-1}-1$) to $k-1$ if $s\in\{1,\ldots,2^{k-2}-1\}$ (note that as we are in the case where $n_a \neq n_b$, we already know that $s>0$). 


Moreover, as $k_b(s)=\lceil \log_2(2^{k-1}-s)\rceil$, we can conclude $s \geq 2^{k-1}-2^{k_b(s)}$. This implies: $$k_b(s)=k-a\mbox{ if } s\in  \{2^{k-1}-2^{k-a},\ldots,2^{k-1}-2^{k-a-1}-1\},$$ 

where $a$ ranges from $1$ to $k$. The only exceptions are the cases $a=1$, where the possible choices for $s$ start at $1$, not at $2^{k-1}(2^0-1)=0$ (because we already know that $s>0$), and $a=k$, because $2^{k-(k+1)}(2^k-1)-1= 2^{k-1}-\frac{3}{2} \not\in \mathbb{N}$, so $s$ cannot assume this value (which is why in this case, the set of possible choices of $s$ contains only one element).

Now we use these insights concerning $k_b(s)$ to find minimal values of $\mathcal{S}(T)$ using Equation (\ref{STbal}).

First, we consider two trees $T_1$ and $T_2$ such that $s_1,s_2 \in \{2^{k-a}(2^{a-1}-1),\ldots,2^{k-(a+1)}(2^a-1)-1\}$ for some value of $a \in \{1,\ldots,k\}$. As both values $s_1$ and $s_2$ correspond to the same value of $a$, we have $k_b(s_1)=k_b(s_2)=k-a$ and therefore we get by Equation (\ref{STbal}): 

$$ \mathcal{S}(T_1)= 2^{k-1}\cdot (k+ (k-a)) + s_1(k- (k-a))+2^k-2^{ k-a}$$ $$=2^{k-1}\cdot (2k-a) + s_1\cdot a+2^k-2^{ k-a}.$$

Analogously, we get: 

$$ \mathcal{S}(T_2)= 2^{k-1}\cdot (k+ (k-a)) + s_2(k- (k-a))+2^k-2^{ k-a}$$ $$=2^{k-1}\cdot (2k-a) + s_2\cdot a+2^k-2^{ k-a}.$$

This implies that $ \mathcal{S}(T_1)< \mathcal{S}(T_2)$ if and only if $s_1<s_2$. So in order to minimize the Sackin index, in each possible line of Equation (\ref{kbcases}), i.e. for each possible value of $a$, the lower bound of the possible values for $s$ is the only candidate for a minimum. 

Now let us summarize what we have: If $a>1$, we know that $s=2^{k-a}(2^{a-1}-1)$ minimizes $\mathcal{S}$, and if $a=1$, $s=1$ minimizes  $\mathcal{S}$. Next, we compare two trees $T_1$ and $T_2$ with different values $a_1$ and $a_2$, respectively, i.e. let $a_1$ and $a_2$ be in $\{2,\ldots,k\}$ such that $a_1<a_2$ (the case where one of the values is 1 will be considered later). Then, in order for $\mathcal{S}$ to be as small as possible, we have already seen that we must use the smallest possible values of $s_1$ and $s_2$, respectively, i.e. $s_1=2^{k-a_1}(2^{a_1-1}-1)$ and $s_2=2^{k-a_2}(2^{a_2-1}-1)$. Using this and considering again Equation (\ref{STbal}), we derive:

$$ \mathcal{S}(T_1)= 2^{k-1}\cdot (k+ (k-a_1)) + s_1(k- (k-a_1))+2^k-2^{ k-a_1}$$ 
$$=2^{k}(k+1)-2^{k-a_1}\cdot (a_1+1),$$

$$ \mathcal{S}(T_2)= 2^{k}(k+1)\underbrace{-2^{k-a_2}}_{>-2^{k-a_1}}\cdot \underbrace{(a_2+1)}_{>(a_1+1)}> \mathcal{S}(T_1).$$

So if $a_1<a_2$ (for $a_1,a_2 \in \{2,\ldots,k\}$), we have $\mathcal{S}(T_1)<\mathcal{S}(T_2)$. This implies that for a minimal value of $\mathcal{S}$, $a$ has to be minimal. So the only candidate for $a$ from the set $\{2,\ldots,k\}$ is $a=2$.

However, we have not investigated the case $a=1$ yet, which is different because in this case we are not allowed to choose $s=2^{k-1}(2^0-1)=0$ as we are in the case where $s\geq 1$. So what remains to be done is to compare the case $a=1$ and $s=1$ with the case $a=2$ and $s=2^{k-2}(2^1-1)=2^{k-2}$.

Therefore, now let $T_1$ be such that $s_1=1$ and thus $a_1=1$, and let $T_2$ be such that $s_2=2^{k-2}$ and $a_2=2$. Then, we get by Equation (\ref{STbal}): 


$$ \mathcal{S}(T_1)= 2^{k-1}\cdot (k+ (k-a_1)) + s_1(k- (k-a_1))+2^k-2^{ k-a_1}= 2^{k}k  + 1,$$ 


and analogously

$$ \mathcal{S}(T_2)= 2^{k-1}\cdot (k+ (k-a_2)) + s_2(k- (k-a_2))+2^k-2^{ k-a_2}= 2^{k}k  +2^{k-2}.$$


So as we are in the case where $k\geq 2$ (else consider the base case of the induction again), this leads to $ \mathcal{S}(T_2)\geq  \mathcal{S}(T_1)=2^{k}k  + 1$. So the minimal value of $\mathcal{S}$ is achieved by the choice of $s=1$ and thus $a=1$, i.e. $k_b=k-1$, but even for a tree fulfilling these conditions we have $\mathcal{S}(T)=2^{k}k  + 1>2^kk=\mathcal{S}(T^{bal}_k)$. The latter equality holds due to Corollary \ref{balmaxbal}. So in total, we obtain $\mathcal{S}(T) >S(T_k^{bal})$, which contradicts the minimality of $\mathcal{S}(T)$. Therefore, the case $n_a\neq n_b$ leads to a contradiction, which is why it cannot occur. Thus we only have to consider the first case, for which we have already shown $T=T_k^{bal}$. This completes the proof.

\end{enumerate}

\end{proof}

So now we know that in case of $n=2^k$, the minimum of the Sackin index is unique. But it has long been known that this need not be the case for other values of $n$. In fact, already for $n=6$, there are two minima, which are depicted in Figure \ref{6taxabalanced}. As stated before, this example is not new; it can for instance  already be found in \cite{cophenetic}. However, so far the explicit number of Sackin minima for $n \neq 2^k$ has not been investigated. In order to derive such a formula, we first need the following theorem, which characterizes all Sackin minima.

\begin{theorem}\label{SackinMinCharacterization} Let $T$ be a rooted binary tree with $n\geq 2$ leaves and $\mathcal{S}(T)$ minimal, i.e. there is no tree on $n$ leaves with a smaller Sackin index. Then, we have: $T$ has height $h_T=k$ with $k=\lceil \log_2(n) \rceil$, and $T$ has precisely $n-2^{k-1}$ cherries of depth $k$. 
\end{theorem}

\begin{proof} We prove the statement by induction on $n$. Throughout this proof, for a rooted binary tree $T$, we denote by $c_T$ the number of cherries of maximal depth.

Now for $n=2$, the only binary rooted tree $T$ consists only of a cherry, and this tree has $h_T=1 = \lceil \log_2(2) \rceil=k$, so the height statement holds. Moreover, $T$ has only one cherry, so $c_T=1=2-2^{1-1}=n-2^{k-1}$. This completes the base case.

Next we assume that the statement is true for up to $n$ leaves and now consider a tree $T$ with $n+1$ leaves and with minimal Sackin index. 
First, in case $n+1= 2^{k}$ for some $k$, by Theorem \ref{TkbalUNIQUE} we know that $T=T_{k}^{bal}$. This immediately implies $h_T=\log_2(n+1)=k$ and $c_T=2^{k-1}=(n+1)-2^{k-1}.$

This completes the proof of the case where $n+1$ is a power of 2.

So now we consider the case $2^{k-1}<n+1<2^k$ with $k=\lceil \log_2(n+1)\rceil$. Let $[u,v]$ be a cherry of maximal depth in $T$ with direct ancestor $w$. We remove $u$, $v$ as well as the edges $(w,u)$ and $(w,v)$ to get a tree $\widetilde{T}$ with $n$ leaves ($u$ and $v$ have been deleted, but $w$, which is in $T$ in internal node, is a leaf in $\widetilde{T}$). Now, again there are two cases: \begin{enumerate}\item $n=2^{k-1}$, which is precisely the case if $n+1 = 2^{k-1}+1$, or \item $n>2^{k-1}$.\end{enumerate} 
\begin{enumerate}\item We now consider the first (and easier) case: If $n=2^{k-1}$, there are again only two possibilities: 

\begin{enumerate}\item Either $\widetilde{T}$ has minimal Sackin index, in which case (by Theorem \ref{TkbalUNIQUE}) we know that $\widetilde{T}=T_{k-1}^{bal}$, or \item$\mathcal{S}(\widetilde{T})>S(T_{k-1}^{bal})$. \end{enumerate}

\par \vspace{0.3cm}
\begin{enumerate} \item \label{case1a} If $\widetilde{T}=T_{k-1}^{bal}$, we have $h_{\widetilde{T}}=k-1$, and as $\widetilde{T}$ was derived by $T$ by deleting one cherry of maximal depth, $T$ must look as depicted in Figure \ref{onecherry}. In particular, $h_T=(k-1)+1=k$, and $T$ has only one cherry of depth $k$ (namely $[u,v]$), as otherwise $h_{\widetilde{T}}$ would equal $h_T$. So $c_T=1=(2^{k-1}+1)-2^{k-1}=(n+1)-2^{k-1}$. This completes the proof for the case $\widetilde{T}=T_{k-1}^{bal}$.


\begin{figure}
	\centering
	\includegraphics[scale=.4]{OneCherry.eps}

	\caption{Illustration of the scenario described in Case (\ref{case1a}).
	}
	\label{onecherry}
\end{figure}


\item Now assume that we have $\mathcal{S}(\widetilde{T})>\mathcal{S}(T_{k-1}^{bal})$, i.e. in summary we now have that $T$ with $n+1 = 2^{k-1}+1$ leaves has $\mathcal{S}(T)$ minimal, but $\widetilde{T}$ with $n=2^{k-1}$ leaves has a Sackin index strictly larger than that of $T_{k-1}^{bal}$, i.e. $\mathcal{S}(\widetilde{T})>S(T_{k-1}^{bal})= 2^{k-1}\cdot (k-1)$. The last equality is due to Proposition \ref{sackinBal}. Note that by construction of $\widetilde{T}$ and Lemma \ref{cherrydeleted}, we have $\mathcal{S}(\widetilde{T})=\mathcal{S}(T)-\delta_u-1$.  Combining both statements on $\mathcal{S}(\widetilde{T})$, we conclude \begin{equation} \label{sackinofTildeT}\mathcal{S}(\widetilde{T})=\mathcal{S}(T)-\delta_u-1> 2^{k-1}\cdot (k-1)=S(T_{k-1}^{bal}). \end{equation}
On the other hand, as $\mathcal{S}(T)$ is minimal by assumption, we know from Theorems \ref{minsackin} and \ref{thm:alg} that \begin{equation}\label{smallestsackin}\mathcal{S}(T)= -2^k+(n+1)(k+1)=-2^k+nk+n+k+1.\end{equation} Combining (\ref{sackinofTildeT}) with (\ref{smallestsackin}), we obtain: $$-2^k+nk+n+k+1-\delta_u-1>k\cdot 2^{k-1} -2^{k-1}.$$ Using $n=2^{k-1}$, we note that this holds precisely if $$-2^k+k\cdot 2^{k-1}+2^{k-1}+k+1-\delta_u-1>k\cdot 2^{k-1} -2^{k-1}.$$ Rearranging the inequality shows that this is fulfilled if and only if $$-2^k+2\cdot 2^{k-1}+k>\delta_u, $$  i.e. precisely if $k>\delta_u$. But recall that $u$ was part of a cherry of maximal depth, i.e. $u$ has maximal depth in $T$, and $T$ has $2^{k-1}+1>2^{k-1}$ leaves. Thus, it can easily be seen (cf. Lemma \ref{maxdepthleaf}) that $h_T\geq k$, which implies $\delta_u \geq k$. This contradicts $k>\delta_u$, which shows that this case cannot happen. So if $\widetilde{T}$ has $n=2^{k-1}$ leaves, $\widetilde{T}$ must equal $T_{k-1}^{bal}$, for which we have already proven the statement in (\ref{case1a}). This completes the proof of this case. 
\end{enumerate}

\item Now what remains to be considered is the case $2^{k-1}<n<n+1<2^k$, which implies $k=\lceil  \log_2(n)\rceil = \lceil  \log_2(n+1)\rceil$. As above, we know that $\mathcal{S}(T)$ is minimal, i.e. by Theorems \ref{minsackin} and \ref{thm:alg} we have $\mathcal{S}(T)= -2^k+(n+1)(k+1)$, and again, by construction of $\widetilde{T}$, we have $\mathcal{S}(\widetilde{T})=\mathcal{S}(T)-\delta_u-1$. Again, we distinguish two cases: \begin{enumerate}\item $\mathcal{S}(\widetilde{T})$ is minimal for $n$, or \item there is another tree $\widehat{T}$ on $n$ leaves with $S(\widehat{T})<\mathcal{S}(\widetilde{T})$.\end{enumerate}

\par\vspace{0.3cm}

\begin{enumerate}
\item \label{case2a} If $\mathcal{S}(\widetilde{T})$ is minimal for $n$, we know by Theorems \ref{minsackin} and \ref{thm:alg} that $\mathcal{S}(\widetilde{T})= -2^k+n(k+1).$ Combining this with $\mathcal{S}(\widetilde{T})=\mathcal{S}(T)-\delta_u-1$ yields \begin{equation}\label{lll}\mathcal{S}(T)=-2^k+nk+n+\delta_u+1.\end{equation} On the other hand, we also know that $\mathcal{S}(T)$ is minimal, so we have \begin{equation}\label{mmm}\mathcal{S}(T)=-2^k+(n+1)(k+1).\end{equation} Combining Equations (\ref{lll}) and (\ref{mmm}) leads to $-2^k+nk+n+\delta_u+1=-2^k+nk+n+k+1$, which immediately gives $\delta_u=k$. As $u$ was a leaf of maximal depth, we have $\delta_u=h_T$ and thus $h_T=k$. 
What remains to be shown is that $c_T=(n+1)-2^{k-1}$. But note that as $\mathcal{S}(\widetilde{T})$ is minimal and $\widetilde{T}$ has $n$ leaves, we know by induction that $c_{\widetilde{T}}= n-2^{k-1}$ and $h_{\widetilde{T}}=k$. We have already shown that $h_T=k$, too. So $T$ and $\widetilde{T}$ have the same height $k$, but $\widetilde{T}$ was constructed by deleting one cherry of maximal depth from $T$. So we have $c_T=c_{\widetilde{T}}+1=  n-2^{k-1}+1=(n+1)-2^{k-1}$. This completes the proof of this case.
\item On the other hand, if $\mathcal{S}(\widetilde{T})$ is not minimal, we know by Theorems \ref{minsackin} and \ref{thm:alg} that $\mathcal{S}(\widetilde{T})> -2^k+n(k+1).$ As above, we also know that $\mathcal{S}(T)=\mathcal{S}(\widetilde{T})+\delta_u+1$, and thus we conclude \begin{equation}\label{aaa}\mathcal{S}(T)>-2^k+n(k+1)+\delta_u+1.\end{equation} On the other hand, though, $\mathcal{S}(T)$ is minimal, so again by Theorems \ref{minsackin} and \ref{thm:alg} we have \begin{equation}\label{bbb}\mathcal{S}(T)=-2^k+(n+1)(k+1).\end{equation} Combining Inequality (\ref{aaa}) with Equation (\ref{bbb}), we conclude $$ -2^k+(n+1)(k+1) > -2^k+n(k+1)+\delta_u+1, $$ which holds precisely if $k>\delta_u$. However, as $u$ was a leaf of maximum depth in $T$, we have $h_T=\delta_u$ and thus $h_T<k$. But this is a contradiction, because as $T$ has more than $2^{k-1}$ leaves, it has at least height $k$, i.e. $h_T\geq k$ (cf. Lemma \ref{maxdepthleaf}). This implies that this case cannot happen, so in fact, $\mathcal{S}(\widetilde{T})$ has to be minimal and we must be in case (\ref{case2a}), for which we have already proven the statement. This completes the proof.

\end{enumerate}


\end{enumerate}

\end{proof}

Note that Theorem \ref{SackinMinCharacterization} characterizes trees with minimal Sackin index in terms of their height, which must be minimal, and in terms of the number of cherries of maximal depth, which must be maximal (both with respect to the number of leaves). So trees with minimal Sackin index can be easily identified with Theorem \ref{SackinMinCharacterization}.

\begin{example} Consider again the two trees on $n=6$ taxa depicted in Figure \ref{6taxabalanced}, which -- as already stated above and as can be seen by exhaustive search through the space of all rooted binary trees with 6 leaves -- have minimal Sackin index for $n=6$. We have $k=\lceil \log_2(6)\rceil = 3$, and indeed, both trees have height 3 and 2 cherries of maximum depth 3, respectively, and thus $h_T=k=3$ and $c_T=n-2^{k-1}=6-2^{3-1}=6-4=2$. \end{example}




Note that so far we have shown that all trees with minimal Sackin index have the height and cherry properties described in Theorem \ref{SackinMinCharacterization}, but as the previous example shows, we still have not shown that all trees with these properties are also automatically minimal (we had to hint at an exhaustive search in order to verify that the two trees in the example indeed were maximally balanced). But in fact, it turns out that the opposite is also true, i.e. if the height is minimal and if the number of cherries of maximal depth is maximal, then the tree under consideration has minimal Sackin index. Indeed, this must be true as we will show now that such a tree will be discovered by Algorithm \ref{alg1}, which by Theorems \ref{minsackin} and \ref{thm:alg} returns only trees with minimal Sackin index.

\begin{theorem} \label{algrecovers} Let $T$ be a rooted binary tree with $n$ leaves and height $h_T=k=\lceil \log_2(n)\rceil$ and with $c_T=n-2^{k-1}$ cherries of maximal depth $k$. Then, $\mathcal{S}(T)$ is minimal, i.e. there is no tree $\widehat{T}$ with $n$ leaves and $S(\widehat{T})<\mathcal{S}(T)$.
\end{theorem}

\begin{proof} Let $T$ be as described in the theorem. We will first prove that $T$ can be discovered by Algorithm \ref{alg1}. Note that $2^{k-1}<n\leq 2^{k}$ for $k=\lceil \log_2(n)\rceil$. Recall that Algorithm \ref{alg1} starts with $T_k^{bal}$ and deletes one cherry of maximal depth at a time until $n$ leaves are reached. Moreover, as long as $n>2^{k-1}$ (which must be the case because otherwise Algorithm \ref{alg1} would start at $T_{k-1}^{bal}$ instead), we only delete at most $2^k-(2^{k-1}+1)=2^k-2^{k-1}-1=2^{k-1}(2-1)-1=2^{k-1}-1$ cherries\footnote{Note that this extreme case would correspond to $n=2^{k-1}+1$.} of the originally $2^{k-1} $ cherries of maximum depth in $T_k^{bal}$. So any tree on $n$ leaves with $2^{k-1}<n\leq 2^{k}$ that the algorithm recovers has height $k$ (as at least one cherry of maximum depth $k$ is kept throughout the algorithm!). Moreover, the number of cherries of maximum depth in a tree of $n$ leaves that are left by Algorithm \ref{alg1} is $c_T=2^{k-1}-(2^k-n)$, as we start with the $2^{k-1}$ cherries of $T_k^{bal}$ and make $2^k-n$ steps, in each of which we delete exactly one cherry of maximum depth. So we end up with $c_T=2^{k-1}-(2^k-n)=2^{k-1}-2^k+n=2^{k-1}(1-2)+n=n-2^{k-1}.$ So, in summary, all trees recovered by Algorithm \ref{alg1} have height $h_T=k$ and $c_T=n-2^{k-1}$. And, more importantly, as the particular choice of cherry of maximum depth that the algorithm deletes is arbitrary, {\em all} such trees can be recovered. So $T$ will be found by Algorithm \ref{alg1}, as all trees of height $k$ and with $c_T=n-2^{k-1}$ leaves of maximum depth can be reached by starting with $T_k^{bal}$ and deleting $2^{k-1}-(2^k-n)$ cherries of maximum depth.

So $T$ can be recovered by Algorithm \ref{alg1}. But, on the other hand, we know by Theorem \ref{thm:alg} that any tree recovered by Algorithm \ref{alg1} has minimal Sackin index. This completes the proof.
\end{proof}

This immediately leads to the following corollary, which is a direct conclusion of Theorems  \ref{SackinMinCharacterization} and \ref{algrecovers}.

\begin{corollary}\label{optalg1} Let $T$ be a rooted binary tree. Then, $\mathcal{S}(T)$ is minimal if and only if $T$ can be recovered by Algorithm \ref{alg1}.
\end{corollary}

\begin{example} Consider again the two trees with $n=6$ taxa, which are depicted in Figure \ref{6taxabalanced}. As both trees can be recovered by Algorithm \ref{alg1} (c.f. Figure \ref{algfig}), both trees must by Theorem \ref{thm:alg} indeed have minimal Sackin index, and as they are the only two trees with six leaves that are recovered by Algorithm \ref{alg1}, they are by Corollary \ref{optalg1} indeed the only two trees with this property. So an exhaustive search through all trees on six taxa as proposed above is not necessary anymore -- instead, all trees with 6 leaves that can be recovered by Algorithm \ref{alg1} are maximally balanced, and all other trees cannot be. In this sense, Corollary \ref{optalg1} provides a complete characterization of trees with minimal Sackin index.  
\end{example}


As the previous example shows, for some values of $n$ there is more than one tree with minimal Sackin index. However, without explicitly listing and enumerating all possible outputs of Algorithm \ref{alg1}, it is not easy to see why for six leaves there are two such trees and for, say, twelve leaves there are five such trees. Of course, by Corollary \ref{optalg1} it all has to do with the number of cherries of maximum depth we can choose from -- but that is not all. Some choices might lead to the same tree. For instance, consider $T_3^{bal}$ as depicted in Figure \ref{algfig} at the top. It can easily be checked that no matter which of the cherries we choose to delete in order to recover a tree with $n=7$ leaves and minimal Sackin index, we always end up with the same tree, namely with the tree depicted in the second line of the same figure. This is due to the symmetries of $T_3^{bal}$. However, when we go from $n=7$ down to $n=6$ and choose one of the underbraced cherries, we will end up with the same tree, namely with the one depicted in the third line of Figure \ref{algfig} on the left-hand side. But if we choose the third cherry of maximum depth in this tree, this will lead to another tree -- namely precisely the one depicted  on the right-hand side of the same line in Figure \ref{algfig}. This is due to the fact that the two underbraced  cherries are in some sense `symmetric' (in the sense that there is a graph isomorphism which exchanges them), while the other cherry clearly is not symmetric to the two first ones. However, it is not trivial to count such symmetries or isomorphisms. But luckily, it is quite easy to characterize the cases where the minimum is unique, as can be seen in the following corollary.


\begin{corollary}\label{uniquesackinminima} Let $n\in \mathbb{N}$. Then, there is only one tree $T$ with minimum Sackin index if and only if there exists an $m \in \mathbb{N}$ such that $n\in \{2^m-1,2^m,2^m+1\}$.
\end{corollary}

\begin{proof} If $n=2^m$, then $m=\lceil\log_2(n)\rceil$, so $m=k$ in Theorem \ref{TkbalUNIQUE}, which implies that the minimum is indeed unique. If $n=2^m-1$, then again for $k=\lceil\log_2(n)\rceil$, we have $m=k$. So in this case, Algorithm \ref{alg1} would start with tree $T_k^{bal}$ and delete precisely one cherry. It can be easily seen that due to symmetry, all cherries lead to the same tree. So for $n=2^m-1$, we again have uniqueness of the most balanced tree. However, if $n=2^m+1$, for $k=\lceil\log_2(n)\rceil$ we have $k=m+1$. In this case, the algorithm would start at $T_{k+1}^{bal}$ and delete all but one cherries of maximal depth. Again, due to symmetry, it does not matter which of these cherries remains in the tree (the scenario is equivalent to the one depicted in Figure \ref{onecherry}). So whenever $n\in \{2^m-1,2^m,2^m+1\}$, Algorithm \ref{alg1} returns precisely one tree, which by Corollary \ref{optalg1} is the unique tree that minimizes the Sackin index in these cases.

Now, assume that $n\notin \{2^m-1,2^m,2^m+1\}$ for any $m$. In particular, for $k=\lceil\log_2(n)\rceil$, this implies that $n \in \{2^{k-1}+2,\ldots,2^k-2\}$. We partition this set into two cases: either $n\in  \{2^{k-1}+2,\ldots,2^{k}-2^{k-2}-1\}$ or $n \in \{2^{k}-2^{k-2},\ldots,2^k-2\}$. Recall that Algorithm \ref{alg1} starts with $T_k^{bal}$ with $2^k$ leaves that form $2^{k-1}$ cherries. 
Now in the first case, if $n\in  \{2^{k-1}+2,\ldots,2^{k}-2^{k-2}-1\}$, at least $2^k-(2^k-2^{k-2}-1)=2^{k-2}+1$ cherries of $T_k^{bal}$ get replaced by single leaves in the course of the algorithm. This implies that at most $2^{k-1}-(2^{k-2}+1)=2^{k-2}-1$ cherries of maximal depth remain. So the remaining cherries can either all be together in one of the maximal pending subtrees of the tree, which we call $T_a$, or, for instance, one of them is in the other maximal pending subtree, which we call $T_b$. This already gives two options on how to choose a tree that can be recovered by Algorithm \ref{alg1}, which by Corollary \ref{optalg1} implies at least two optima.

On the other hand, if $n \in \{2^{k}-2^{k-2},\ldots,2^k-2\}$, this implies that at most $2^k-(2^k-2^{k-2})=2^{k-2}$ cherries get replaced by single leaves. These replacements can either all happen in the same maximal pending subtree of the tree, which we then call $T_b$, or, for instance, all can happen in $T_b$ except for one which happens in the other maximal pending subtree, which we then call $T_a$. This again gives at least two options on how to choose a tree that can be recovered by Algorithm \ref{alg1}, which by Corollary \ref{optalg1} implies at least two optima. 

So in summary, the minimum is unique if and only if $n\in \{2^m-1,2^m,2^m+1\}$ for some $m \in \mathbb{N}$. This completes the proof.
\end{proof}

Note that Algorithm \ref{alg1} guarantees that the difference between the two maximal pending subtrees $T_a$ and $T_b$ of the standard decomposition of a minimum Sackin tree does not get too large (in terms of the number of leaves). We will quantify this in the following corollary, which is based on Corollary \ref{optalg1}.

\begin{corollary}
Let $T$ be a rooted binary tree with $n\in \mathbb{N}_{\geq 2}$ leaves. Moreover, let $T=(T_a,T_b)$ be the standard decomposition of $T$ into its two maximal pending subtrees, let $n_i$ denote the number of leaves in $T_i$ for $i\in \{a,b\}$, respectively, such that $n_a\geq n_b$. Let $k=\lceil \log_2 n\rceil$. Then, the following equivalence holds:
$T$ has minimum Sackin index if and only if $ T_a$ and $T_b$ have minimum Sackin index and $n_a-n_b\leq \min\{n-2^{k-1},2^k-n\}.$
\end{corollary}

\begin{proof}
We first consider the case where $T$ has minimum Sackin index. It is clear that $T_a$ and $T_b$ then also have minimum Sackin index. Moreover, by considering Algorithm \ref{alg1}, one can easily see that the difference between $n_a$ and $n_b$ is maximal when you perform as many cherry deletions in $T_b$ as possible. If all cherry deletions happen in $T_b$, which implies $n\geq 2^k-2^{k-2}=3\cdot 2^{k-2}$, $T_a$ equals $T_{k-1}^{bal}$ and thus $n_a =2^{k-1}$ and thus $n_b=n-2^{k-1}$. So if $n\geq 2^k-2^{k-2}$, we have $n_a-n_b \leq 2^{k-1}-n+2^{k-1} = 2^k-n$. Moreover, as $n\geq 3\cdot 2^{k-2}$ also implies that $2^k-n \leq n-2^{k-1}$, this completes the proof for the case where all cherry deletions happen in $T_b$.

However, if more than $2^{k-2}$ cherry deletions happen, $T_b$ equals $T_{k-2}^{bal}$ and thus we have $n_b=2^{k-2}$. Morever, in this case we have  $n_a=n-2^{k-2}$, and $n < 3 \cdot 2^{k-2}$. Thus, on the one hand we have $n_a-n_b=n-2^{k-1}$and $n-2^{k-1} < 3 \cdot 2^{k-2} - 2^{k-1} = 2^{k-2}$. On the other hand, we have $2^k-n > 2^k-3 \cdot 2^{k-2}$. This implies $n_a-n_b=n-2^{k-1}<2^k-n$, which completes the first direction of the proof.

Now let us consider $T=(T_a,T_b)$ such that $T_a$ and $T_b$ are Sackin minima and $n_a-n_b  \leq \min\{n-2^{k-1},2^k-n\}$. We need to show that $T$ is also a Sackin minimum. First note that we have $n_a-n_b\leq 2^k-n$, which implies $n_a \leq 2^{k-1}$, and that we also have $n_a-n_b\leq n-2^{k-1}$, which implies $n_b\geq 2^{k-2}$. As $n=n_a+n_b$ and as $n_a\geq n_b$, we have $n_a \geq \frac{n}{2}$ and $n_b \leq \frac{n}{2}$. So altogether we get $\frac{n}{2} \leq n_a \leq 2^{k-1}$ and $2^{k-2} \leq n_b \leq \frac{n}{2}$. It is easy to see that these leaf numbers precisely correspond to the trees recovered by Algorithm \ref{alg1}. This completes the proof.
\end{proof}











As stated above, counting the symmetries that remain when cherries of maximal depth are deleted is not trivial, even if Corollary \ref{uniquesackinminima} already provides some insight into whether there is more than one tree that minimizes the Sackin index for a given value of $n$. So in order to conclude this section, we will show in the following that the number of trees with minimal Sackin index can be explicitly counted by a recursive formula. The proof of this formula exploits Corollary \ref{optalg1}.

\begin{theorem} \label{recursion} Let $s(n)$ denote the number of binary rooted trees with $n$ leaves and with minimal Sackin index and let $k = \lceil \log_2(n)\rceil$. For any partition of $n$ into two integers $n_a$, $n_b$, i.e. $n=n_a+n_b$, we use $k_a$ and $k_b$ to denote $\lceil \log_2(n_a)\rceil$ and $\lceil \log_2(n_b)\rceil=\lceil \log_2(n-n_a)\rceil$, respectively. Moreover, let $$f(n)=\begin{cases}0 & \mbox{if $n$ is odd} \\ {s(\frac{n}{2})+1 \choose 2}& \mbox{else. }\end{cases}$$  Then, the following recursion holds: 
\begin{itemize}
\item $s(1)=1$
\item $s(n)=  \sum\limits_{\substack{(n_a,n_b): \\n_a+n_b=n,\\ n_a\geq \frac{n}{2},\\ k_a = k -1, \\ k_b = k -1, \\n_a \neq n_b }}  s(n_a)\cdot s(n_b) +f(n)+s(n-2^{k-2})$
\end{itemize}

\end{theorem}

\begin{proof} First consider $n=1$. In this case, it is clear that there is only one rooted binary tree, namely the one consisting of only one node, which therefore has minimal Sackin index, which implies $s(1)=1$.

Before we continue with the recursion, let us analyze Algorithm \ref{alg1} a little bit more in-depth. We know by Corollary \ref{optalg1} that if we want to count all trees with $n$ leaves with minimal Sackin index, we only need to count the ones that can be recovered by Algorithm \ref{alg1}. However, we have also already seen that all trees recovered by this algorithm have height $k= \lceil \log_2(n)\rceil$. Moreover, let $T$ be such a tree recovered by Algorithm \ref{alg1} and consider its standard decomposition $T=(T_a,T_b)$ with $n_a$ and $n_b$ leaves, respectively, such that $n=n_a+n_b$. As before, we can assume without loss of generality that $n_a\geq n_b$, i.e. that $n_a \geq \frac{n}{2}$. Then, Algorithm \ref{alg1} will assure that the larger of the two subtrees has height $k-1$. This is due to the fact that we start with $T_k^{bal}$, i.e. in the beginning both subtrees have height $k-1$, and then we delete at most all but one cherry of maximum depth (because otherwise the algorithm would have started at $T_{k-1}^{bal}$). So the larger of the two subtrees, $T_a$, always keeps its initial height, which is $k-1$, so we always have $k_a=k-1$. Therefore, by Corollary \ref{optalg1}, no trees with $k_a \neq k-1$ can have minimal Sackin index.

Now consider $T_b$. For $T_k^{bal}$, both maximal pending subtrees have height $k-1$, but then some cherries of maximal depth are deleted. This way, it may happen that the height  $k_b$ of $T_b$ is at some stage less than $k-1$ (given that the difference between $n$ and $2^k$ is large enough). However, note that we always have $k_b \geq k-2$ (and thus $n_b\geq 2^{k-2}$), because as soon as the height of $T_b$ is only $k_b=k-2$, there is no longer a cherry of maximum depth $k$ of $T$ to be found in $T_b$. So when the algorithm continues, it will never choose a cherry from $T_b$ again, because all cherries of maximum depth would now be in $T_a$. So in total, we have $k_b \in \{k-2,k-1\}$. 

So in summary, all trees $T$ recovered by Algorithm \ref{alg1}, and thus all trees with a minimal Sackin index, have the property that $k_a=k-1$ and $k_b \in \{k-2,k-1\}$ for $n=n_a+n_b$ and $n_a \geq \frac{n}{2}$. Trees with $n$ leaves which do not have these properties can by Corollary \ref{optalg1} thus not have minimal Sackin index.

Moreover, we know that (as $\mathcal{S}(T)=\mathcal{S}(T_a)+\mathcal{S}(T_b)+n$ by definition) if $\mathcal{S}(T)$ is minimal, $\mathcal{S}(T_a)$ and $\mathcal{S}(T_b)$ must be minimal, too. 

Now we want to calculate $s(n)$. Therefore, we consider all integer partitions of $n$ into precisely 2 summands, i.e. $n=n_a+n_b$ for some $n_a$, $n_b \in \mathbb{N}$ such that $n_a \geq n_b$, i.e. $n_a\geq \frac{n}{2}$. Now we set $k:=\lceil \log_2(n)\rceil$, $k_a:=\lceil \log_2(n_a)\rceil$ and $k_b:=\lceil \log_2(n_b)\rceil$. Note that as $n_a \geq \frac{n}{2}$, $k_a \geq \lceil \log_2(\frac{n}{2})\rceil = \lceil \log_2(n)-\log_2(2)\rceil =\lceil \log_2(n)-1\rceil =\lceil \log_2(n)\rceil-1= k-1$, so $k_a \in \{k-1,k\}$.

We distinguish the only three possible cases: 

\begin{enumerate}
\item $k_a=k-1$ and $k_b=k-1$ and $n_a\neq n_b$, 
\item $k_a=k-1$ and $k_b=k-1$ and $n_a= n_b$, 
\item $k_a=k-1$ and $k_b=k-2$,
\end{enumerate}

\par\vspace{0.3cm}

\begin{enumerate} 

\item Let $n_a$ be such that $k_a=k-1$ and $k_b=k-1$ and $n_a\neq n_b$. Any tree with $n$ leaves and minimum Sackin index and standard decomposition $T=(T_a,T_b)$ with $n=n_a+n_b$, $n_a \geq \frac{n}{2}$, $k_a=k-1$, $k_b=k-1$ and $n_a\neq n_b$ must have the property that $T_a$ and $T_b$ have minimum Sackin index, too, as $\mathcal{S}(T)=\mathcal{S}(T_a)+\mathcal{S}(T_b)+n$. This implies by Theorems \ref{minsackin} and \ref{thm:alg} that $\mathcal{S}(T_a)=-2^{k_a}+n_a(k_a+1)$ and $\mathcal{S}(T_b)=-2^{k_b}+n_b(k_b+1)$. Using this together with $k_a=k-1$ and $k_b=k-1$ and $n_b=n-n_a$, we derive:

$$ \mathcal{S}(T) = \mathcal{S}(T_a)+\mathcal{S}(T_b)+n =-2^k+n(k+1).$$ 

So $\mathcal{S}(T)=-2^k+n(k+1)$, which we know must hold for any tree $T$ with $n$ leaves and minimum Sackin index (again due to Theorems \ref{minsackin} and \ref{thm:alg}). So {\em every } combination of $T_a$ and $T_b$ with the properties that $T_a$ and $T_b$ have minimum Sackin index and $n=n_a+n_b$, $k_a=k-1$, $k_b=k-1$ and $n_a\neq n_b$ leads to a valid tree $T=(T_a,T_b)$ on $n$ leaves, i.e. a tree which indeed has minimum Sackin index. So every such combination has to be considered. Thus, we sum over all those pairs $(n_a,n_b)$ and consider for each of them all possibilities to combine choices from the $s(n_a)$ trees with $n_a$ leaves with minimum Sackin index with the $s(n_b)$ trees with $n_b$ leaves and minimum Sackin index. There are $s(n_a)\cdot s(n_b)$ such combinations. This explains the first sum of the recursion. 

\item Now if $n$ is even, there is another summand: If $k_a=k-1$ and $k_b=k-1$ and $n_a= n_b$, we can proceed as in Case 1 but here, we have to consider all combinations of 2 trees from the $s(n_a)=s(n_b)$ trees with $n_a=n_b$ leaves and with minimum Sackin index, and there are ${s(n_a)-1+2 \choose 2} $ such combinations (unordered sampling of two trees from $s(n_a)$ trees with replacement, as the two trees may be equal and as their order does not matter), see for instance \cite[Equation (1.4.4)]{ProbTheory}) for more details. This explains the second summand in the recursion.


\item Next, consider the case $k_a=k-1$ and $k_b=k-2$. Note that if $k_b=\lceil \log_2(n_b) \rceil= k-2$, we have $n_b\leq 2^{k-2}$. But as explained above, for a tree recovered by Algorithm \ref{alg1}, we always have $n_b\geq 2^{k-2}$, so now we must have $n_b=2^{k-2}$. By Theorem \ref{TkbalUNIQUE}, this implies that the only choice for $T_b$ with minimum Sackin index is $T_{k-2}^{bal}$. So for $T_b$, there is no alternative, but we can combine the only choice of $T_b$ with all possible choices of $T_a$, of which there are $s(n_a)=s(n-n_b)=s(n-2^{k-2})$ many. This explains the last summand in the above recursion. 

\end{enumerate}

As we have considered all cases and added all contributions of each possible integer partition of $n$, there is nothing more to show. This completes the proof. 

\end{proof}

\begin{remark} Starting at $n=1$ and continuing up to $n=32$, the sequence $s(n)$ of numbers of trees with $n$ leaves and with minimal Sackin index is 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 5, 3, 3, 1, 1, 1, 4, 6, 14, 17, 27, 28, 35, 28, 27, 17, 14, 6, 4, 1, 1. We have calculated the values of $s(n)$ for up to $n=1024$. These data can be found online at \cite{NumberOfSackinMinima}. Note that this sequence is new to the Online Encyclopedia of Integer Sequences OEIS \cite[Sequence A299037]{OEIS}; it has been submitted in the scope of this manuscript. It had previously not been contained in the OEIS, i.e. this sequence has so far apparently not occurred in any other context.
\end{remark}













\section{Discussion}
In this manuscript, we first proved some results which are maybe not surprising as they have been stated in the literature before, but as they still had to be proved, we delivered the mathematical arguments to back those results up. We also explicitly derived the sequences for the values $\mathcal{S}(T)$ (where $T$ is a tree with $n$ leaves) of the minimum and maximum Sackin indices for growing values of $n$, and showed that they are known sequences as they are already contained in OEIS. This might lead to future research as it connects the optimal Sackin index to other problems that can be found in the literature.

Subsequently and more importantly, we provided two algorithms which can be used to explicitly find all trees with minimal Sackin index even in the complicated case where $n\neq 2^k$, about which previously little had been known. We then used these algorithms to characterize trees with a minimal Sackin index and to derive a recursion for the sequence of numbers of such trees, which is new to the OEIS. A question for future research could be to find a closed formula or a generating function describing this sequence.

Another area of interest for future research might be the investigation of other well-known and frequently used balance indices like, for instance, the Colless index \cite{colless}. Moreover, the implications of our findings, i.e. of the number of extremal trees concerning the Sackin index, on evolutionary models and their induced probability distributions on the tree space are also of high interest.


\section*{Acknowledgements}
The author wishes to thank Lina Herbst and Kristina Wicke for very helpful discussions on the general topic and for comments concerning an earlier version of the manuscript. The author also wishes to thank Mike Steel for very helpful discussions and some suggestions, in particular concerning a shorter version of the first part of the proof of Lemma \ref{equidefs} and a shorter version of the proof of Proposition \ref{sackinCat}.


\section*{Appendix}

Here we state and prove some basic combinatorial and graph theoretic results that are helpful to understand the proofs in the main part of the manuscript.








\begin{lemma} \label{h>k} Let $T$ be a rooted binary tree with $n$ leaves. Let $h=h(T)$ be the height of $T$, i.e. the number of edges on the longest path from the root to any of the leaves of $T$. Let $k \in \mathbb{N}$ be such that $n>2^k$. Then we have: $h> k$.
\end{lemma}


\begin{proof} Recall that in a rooted binary tree $T$ with node set $V$ and $n$ leaves, we have $|V|=2n-1$. So by assumption, we here have $|V|=2n-1> 2\cdot 2^k-1=2^{k+1}-1$, as we assume $n>2^k$. 
Now let $a_i$ denote the number of nodes in $V$ with level $i$, i.e. the number of nodes in $V$ whose shortest path to the root employs $i$ edges. Note that then, $a_0$ is 1, because the root $\rho$ itself is the only node with distance 0 to the root, and the node with maximal level has level $h$ -- it will be precisely one of the leaves whose depths defines the height of $T$. We now use the $a_i$ values to derive a second bound for $|V|$, namely by summing up over all possible levels: $ |V|=\sum\limits_{i=0}^{h}a_i.$ 
Note that it can be easily seen that as $T$ is binary, we have $a_i \leq 2^i$ for each $i=0,\ldots, h$, which leads to: 
$$|V|=\sum\limits_{i=0}^{h}a_i \leq \sum\limits_{i=0}^{h}2^i = 2^{h+1}-1.$$

The last equality uses the geometric series property.

So, in total we conclude $2^{k+1}-1 < |V| \leq 2^{h+1}-1$. This implies $k < h$ and thus completes the proof. 
\end{proof}



\begin{lemma}\label{maxdepthleaf}
Let $T$ be a rooted binary tree with $n\geq2^{k-1}+1$ leaves for some $k \in \mathbb{N}_0$, and let $u$ be a leaf of maximal depth $\delta_u$ in $T$, i.e. $\delta_u=h(T)$.  Then, $\delta_u=h(T) \geq k$. In particular, if $n=2^k$, we have $h(T) \geq k$. 
\end{lemma}

\begin{proof} By Lemma \ref{h>k}, as $n\geq2^{k-1}+1> 2^{k-1}$, we conclude that $h(T)>k-1$ and thus $\delta_u>k-1$. As $\delta_u \in \mathbb{N}$, we conclude $\delta_u\geq k$. 
Moreover, if $n=2^k$, this implies $n\geq2^{k-1}+1$, so this completes the proof.
\end{proof}


\begin{lemma} \label{maxdepth} Let $T$ be a rooted binary tree with $n\geq 1$ leaves. Let $u$ be a leaf of maximal depth $\delta_u$ in $T$. Then, $\delta_u \leq n-1$. 
\end{lemma}


\begin{proof}
Considering that a rooted binary tree with $n$ leaves has $2n-1$ nodes in total and therefore $n-1$ internal nodes, the stated bound is obvious: The extreme case would be if a leaf had {\it all} internal nodes on its path to the root, which implies $\delta_u\leq n-1$ for all leaves $u$ of $T$. This completes the proof.
\end{proof}







\bibliographystyle{natbib}

2019-03-28T01:17:57.000
1801
1801.10418
en
https://arxiv.org/abs/1801.10418
Tree balance plays an important role in different research areas like theoretical computer science and mathematical phylogenetics. For example, it has long been known that under the Yule model, a pure birth process, imbalanced trees are more likely than balanced ones. Also, concerning ordered search trees, more balanced ones allow for more efficient data structuring than imbalanced ones. Therefore, different methods to measure the balance of trees were introduced. The Sackin index is one of the most frequently used measures for this purpose. In many contexts, statements about the minimal and maximal values of this index have been discussed, but formal proofs have only been provided for some of them, and only in the context of ordered binary (search) trees, not for general rooted trees. Moreover, while the number of trees with maximal Sackin index as well as the number of trees with minimal Sackin index when the number of leaves is a power of 2 are relatively easy to understand, the number of trees with minimal Sackin index for all other numbers of leaves has been completely unknown. In this manuscript, we extend the findings on trees with minimal and maximal Sackin indices from the literature on ordered trees and subsequently use our results to provide formulas to explicitly calculate the numbers of such trees. We also extend previous studies by analyzing the case when the underlying trees need not be binary. Finally, we use our results to contribute both to the phylogenetic as well as the computer scientific literature by using the new findings on Sackin minimal and maximal trees in order to derive formulas to calculate the number of both minimal and maximal phylogenetic trees as well as minimal and maximal ordered trees both in the binary and non-binary settings. All our results have been implemented in the Mathematica package SackinMinimizer, which has been made publicly available.
Populations and Evolution (q-bio.PE); Combinatorics (math.CO)
Extremal values of the Sackin tree balance index
Qwen/Qwen-72B
1. YES
2. YES