Total path length

The total path length $TPL$ sums up all vertex depths. As such, it is related to the Sackin index, i.e., the total external path length, and the total internal path length. $TPL$ is defined for arbitrary trees and it is an imbalance index, i.e. for a fixed $n\in\mathbb{N}_{\geq 1}$ it increases with decreasing balance of the tree. It can be calculated using the function totPathLen from our R package treebalance.

Definition (e.g. Dobrow, Fill, 1999, Takacs, 1992, Takacs, 1994): The total path length $TPL(T)$ of a tree $T\in\mathcal{T}^\ast_n$ is defined as $TPL(T) := \sum\limits_{v \in V(T)} \delta_T(v) = S(T)+TIP(T)$ ,
where $S(T)$ denotes the Sackin index, i.e., the total external path length, and $TIP(T)$ denotes the total internal path length.
Computation time: For every tree $T\in\mathcal{T}^\ast_n$ , the total path length $TPL(T)$ can be computed in time $O(n)$ (see Fischer et al., 2023, Proposition 23.5).
Recursiveness: The total path length is a recursive tree shape statistic. More information on the recursion can be found in Fischer et al., 2023, Proposition 23.6.
Locality: For arbitrary trees $T\in \mathcal{T}^\ast_n$ the total path length is not local. For binary trees $T\in \mathcal{BT}^\ast_n$ it is local. (see Fischer et al., 2023, Proposition 23.7).
Maximal value and (number of) trees with maximal value on $\mathcal{T}^\ast_n$ and $\mathcal{BT}^\ast_n$ : An upper bound for the total path length for arbitrary and binary trees trees $T\in \mathcal{T}^\ast_n$ or $\in \mathcal{BT}^\ast_n$ with $n$ leaves which is tight for all $n\in\mathbb{N}_{\geq 1}$ as well as the (number of) corresponding maximal (binary) trees has already been established (see Fischer et al., 2023, Theorem 23.3).
Minimal value and (number of) minimal trees on $\mathcal{T}^\ast_n$ : A lower bound for the total path length for trees $T\in \mathcal{T}^\ast_n$ which is tight for all $n\in\mathbb{N}_{\geq 1}$ as well as the (number of) corresponding minimal trees have already been established (see Fischer et al., 2023, Proposition 23.8).
Minimal value and (number of) minimal trees on $\mathcal{BT}^\ast_n$ : A lower bound for the total path length for binary trees $T\in \mathcal{BT}^\ast_n$ which is tight for all $n\in\mathbb{N}_{\geq 1}$ as well as the (number of) corresponding minimal trees have already been established (see Fischer et al., 2023, Theorem 23.4).
Expected value and variance under the Yule model: Open problem.
Expected value and variance under the uniform model: Open problem.