a1 Department of Applied Mathematics, National Chiao Tung University, Hsinchu, 300, Taiwan (e-mail: email@example.com)
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.
(Received October 27 2007)
(Revised June 02 2008)
(Online publication August 06 2008)
† Partially supported by National Science Council under the grant NSC-95-2115-M-009-017.