On the combinatorics of leftist trees

Let l(n) be the number of leftist trees with n nodes. The corresponding (or dinary) generating function l(x) is shown to satisfy an explicit functional equation, from which a specific recurrence for the l(n) is obtained. Some basic analytic properties of l(x) are uncovered. Then the problem of determ ining average quantities (expected additive weights, in the notation of Kem p (Acta Inform. 26 (1989) 711-740)) related to the distribution of nodes is re-analysed. Finally, the average height of leftist trees is shown to be a symptotic to n(1/2), apart from a multiplicative constant that can be evalu ated with high accuracy. (C) 2001 Elsevier Science B.V. All rights reserved .