On the combinatorics of leftist trees (Q5931792)

The author investigates combinatorial properties of leftist trees. Let \(\ell_n\) be the number of leftist trees with \(n\) nodes. The corresponding (ordinary) generating function \(\ell(x)\) is shown to satisfy an explicit functional equation, from which a specific recurrence for the \(\ell_n\) is obtained. Some basic analytic properties of \(\ell(x)\) are uncovered. Then the problem of determining average quantities (expected additive weights, in the notation of \textit{R. Kemp} [Acta Inf. 26, No. 8, 711-740 (1989; Zbl 0685.68023)]) related to the distribution of nodes is re-analysed. Finally, the average height of leftist trees is shown to be asymptotic to \(n^{1/2}\), apart from a multiplicative constant that can be evaluated with high accuracy.