Paths in image-ary interval trees Original Research Article

We introduce the image-ary interval tree, a random structure that underlies interval division and simultaneous parking problems. Certain significant paths in the image-ary interval trees are considered. When appropriately normed, the length of these paths are shown to converge in distribution to a normal random variable. The work extends the study of incomplete binary interval trees in Itoh and Mahmoud (J. Appl. Probab. 40 (2003) 645). However, the extension is nontrivial, in the sense that the characterization in the image-ary case involves high-order differential equations, which is to be contrasted with the first-order differential equation that underlies the binary case, and in the sense that the path lengths exhibit oscillatory behavior for image, that does not exist in binary and ternary cases.