Extremal properties of random trees - art. no. 035101

We investigate extremal statistical properties such as the maximal and the minimal heights of randomly generated binary trees. By analyzing the master evolution equations we show that the cumulative distribution of extremal h eights approaches a traveling wave form. The wave front in the minimal case is governed by the small-extremal-height tail of the distribution, and con versely, the front in the maximal case is governed by the large-extremal-he ight tail of the distribution. We determine several statistical characteris tics of the extremal height distribution analytically. In particular, the e xpected minimal and maximal heights grow logarithmically with the tree size , N, h(min)similar tov(min) ln N, and h(max) similar tov(max) ln N, with v( min)=0.373365... and v(max)=4.31107.... respectively. Corrections to this a symptotic behavior are of order C(InlnN).