uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Left and right pathlengths in random binary trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2006 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 46, no 3-4, 419-429 p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
random binary tree, total pathlength, left pathlength, right pathlength, Brownian snake, ISE
National Category
URN: 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 Available from: 2008-01-11 Created: 2008-01-11 Last updated: 2011-04-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Janson, Svante
By organisation
Department of Mathematics
In the same journal

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 142 hits
ReferencesLink to record
Permanent link

Direct link