EUVIMEDObjevte EUVIMED
Crossref

Growing Binary Trees

Olivier Bodini, Antoine Genitrini, Khaydar Nurligareev

Electronic Proceedings in Theoretical Computer Science · 2026-06-07 · 445 · 47-56

DOI: 10.4204/eptcs.445.7 ↗

At a glance

Journal article in Electronic Proceedings in Theoretical Computer Science, published online on 2026-06-07. Written by Olivier Bodini and 2 co-authors. 21 references.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

This paper introduces a new combinatorial framework for modeling the growth of binary trees through a discrete evolution process that incorporates a growing rule and an extinction rule. Building upon the theory of increasingly labeled structures and the analysis of polynomial iterates, we extend previous models of increasing trees with label repetitions by allowing growth branches to terminate. This mechanism enables a direct connection between dynamic evolutionary processes and classical unlabeled binary trees. We provide a combinatorial outlook for this model, linking our new approach to essential but traditionally complex parameters such as tree height, the maximum number of leaves at the deepest level (for a given tree size), and the overall tree profile. Our approach reveals structural links with Mandelbrot polynomials and coding theory. Furthermore, we leverage these structural insights to develop an efficient, iterative uniform random sampler for binary trees with a prescribed profile, achieving optimal complexity in both time and space and in random bit consumption.

Cite

APA

Bodini, O., Genitrini, A., & Nurligareev, K. (2026). Growing Binary Trees. Electronic Proceedings in Theoretical Computer Science, 445, 47-56. https://doi.org/10.4204/eptcs.445.7

Vancouver

Bodini O, Genitrini A, Nurligareev K. Growing Binary Trees. Electronic Proceedings in Theoretical Computer Science. 2026;445:47-56. doi:10.4204/eptcs.445.7

BibTeX
@article{Bodini2026,
  author = {Bodini, Olivier and Genitrini, Antoine and Nurligareev, Khaydar},
  title = {Growing Binary Trees},
  journal = {Electronic Proceedings in Theoretical Computer Science},
  year = {2026},
  volume = {445},
  pages = {47--56},
  doi = {10.4204/eptcs.445.7}
}
Start for free →