The moments of the sackin index of random $\boldsymbol{d}$-ary increasing trees


R. Kazemi, A. Behtoei




For any fixed integer $d\geq 2$, the $d$-ary increasing tree is a rooted, ordered, labeled tree where the out-degree is bounded by $d$, and the labels along each path beginning at the root increase. Total path length, or search cost, for a rooted tree is defined as the sum of all root-to-node distances and the Sackin index is defined as the sum of the depths of its leaves. We study these quantities in random $d$-ary increasing trees.