Left and right pathlengths in random binary trees
2006 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 46, no 3-4, 419-429 p.Article in journal (Refereed) Published
We study the difference between the left and right total pathlengths in a random binary tree. The results include exact and asymptotic formulas for moments and an asymptotic distribution that can be expressed in terms of either the Brownian snake or ISE. The proofs are based on computing expectations for a subcritical binary Galton-Watson tree, and studying asymptotics as the Galton-Watson process approaches a critical one.
Place, publisher, year, edition, pages
2006. Vol. 46, no 3-4, 419-429 p.
random binary tree, total pathlength, left pathlength, right pathlength, Brownian snake, ISE
IdentifiersURN: urn:nbn:se:uu:diva-26314DOI: 10.1007/s00453-006-0099-3ISI: 000243383500009OAI: oai:DiVA.org:uu-26314DiVA: diva2:54088
10th Workshop on the Analysis of Algorithms
Berkeley, CA, JUL, 2004 2008-01-112008-01-112011-04-08Bibliographically approved