The Distribution of the Deepest Leaves in Binary Trees
Abstract
We study the extreme local structure of plane binary trees through the limiting distribution of the number of leaves at maximum depth. For every m≥1, we determine the limiting probability κ[m] that the deepest level contains 2m leaves. The resulting sequence is encoded by a generating function K(y), obtained from a bivariate refinement of the Catalan iteration. We show that, at the critical point of this iteration, a parabolic recurrence governs the marked generating functions. Using continuous iteration theory and a Fatou coordinate, we transform this recurrence into the functional equation K((1+y/4)2)=K(y)+4, which describes the limiting law. Its singular behavior yields the exponential tail κ[m]∼4−m+1. Numerical evaluation gives, e.g., κ[1]≈0.7009, κ[2]≈0.2226 and an average number of deepest leaves equal to κ̂=4κ[1]≈2.8037.
Related
- Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
- Maximal Center of Distances of Finite Ultrametric Spaces and Perfect Binary Trees
- From Trees to Binary Trees: Approximation Algorithms and a PTAS
- On the limiting distribution of the number of improper edges for random trees
- When is the deepest drawdown also the longest?
BibTeX
@misc{bodini2026distribution,
title = {{The Distribution of the Deepest Leaves in Binary Trees}},
author = {Olivier Bodini and Antoine Genitrini and Khaydar Nurligareev},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.12821},
eprint = {2605.12821},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.12821},
}
RIS
TY - UNPB
TI - The Distribution of the Deepest Leaves in Binary Trees
AU - Olivier Bodini
AU - Antoine Genitrini
AU - Khaydar Nurligareev
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2605.12821
UR - https://arxiv.org/abs/2605.12821
AB - We study the extreme local structure of plane binary trees through the limiting distribution of the number of leaves at maximum depth. For every m≥1, we determine the limiting probability κ^[m] that the deepest level contains 2m leaves. The resulting sequence is encoded by a generating function K(y), obtained from a bivariate refinement of the Catalan iteration. We show that, at the critical point of this iteration, a parabolic recurrence governs the marked generating functions. Using continuous iteration theory and a Fatou coordinate, we transform this recurrence into the functional equation K((1+y/4)^2)=K(y)+4, which describes the limiting law. Its singular behavior yields the exponential tail κ^[m]∼4^−m+1. Numerical evaluation gives, e.g., κ^[1]≈0.7009, κ^[2]≈0.2226 and an average number of deepest leaves equal to κ̂=4κ^[1]≈2.8037.
ER -