Distribution of the size of random hash trees, pebbled hash trees and N-trees

Devroye (SIAM J. Comput. 28 (1999) 1215-1224) computed the average size of several random hash-based trees. We extend this analysis by finding the central limit distribution for a suitably normalized version of the size of each of random hash trees, pebbled hash trees and N-trees. Because of a strong dependency among the sizes of the subtrees, one cannot appeal to standard theorems for sums of independent random variables. Our paper probes further a saddle point method based on expressing the characteristic generating function of the size of each tree as a coefficient in a super characteristic generating function raised to a large power.