DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2026.2

Path Length and External Path Length in Random Trees

Authors: Jacob Lundblad and Stephan Wagner

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract

We consider two closely related concepts in rooted trees: the path length is the sum of all distances from the root to the vertices of the tree, while the external path length is the sum of all distances from the root to the leaves of the tree. Upon dividing by the number of vertices and leaves respectively, we obtain the average distance to the root. For two important classes of random trees, we show that the average distance of the root to a random leaf is almost the same as the average distance to a random vertex. For Bienaymé-Galton-Watson trees, the difference is bounded in probability. For three varieties of increasing trees (recursive trees, d-ary increasing trees, generalised plane-oriented recursive trees), on the other hand, the difference converges to a constant in probability.

Cite as

Jacob Lundblad and Stephan Wagner. Path Length and External Path Length in Random Trees. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lundblad_et_al:LIPIcs.AofA.2026.2,
  author =	{Lundblad, Jacob and Wagner, Stephan},
  title =	{{Path Length and External Path Length in Random Trees}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.2},
  URN =		{urn:nbn:de:0030-drops-262733},
  doi =		{10.4230/LIPIcs.AofA.2026.2},
  annote =	{Keywords: Path length, external path length, Bienaym\'{e}-Galton-Watson trees, increasing trees}
}

Search Results

Documents authored by Lundblad, Jacob

Path Length and External Path Length in Random Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message