Subtree sizes in recursive trees and binary search trees: Berry-Esseen bounds and poisson approximations

Michael Fuchs*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

We study the number of subtrees on the fringe of random recursive trees and random binary search trees whose limit law is known to be either normal or Poisson or degenerate depending on the size of the subtree. We introduce a new approach to this problem which helps us to further clarify this phenomenon. More precisely, we derive optimal Berry-Esseen bounds and local limit theorems for the normal range and prove a Poisson approximation result as the subtree size tends to infinity.

Original languageEnglish
Pages (from-to)661-680
Number of pages20
JournalCombinatorics Probability and Computing
Volume17
Issue number5
DOIs
StatePublished - 1 Sep 2008

Fingerprint Dive into the research topics of 'Subtree sizes in recursive trees and binary search trees: Berry-Esseen bounds and poisson approximations'. Together they form a unique fingerprint.

Cite this