On the number of deepest nodes in ordered trees

✍ Scribed by R. Kemp

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 637 KB
• Volume: 81
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(90)90064-o

✦ Synopsis

Let Qn.k,, be the number of all n-node ordered trees with r nodes of maximum level k and let B,,*,, be the number of all r-tuply rooted ordered trees with n nodes and height less than or equal to k. In this paper we derive the identitity

where n, k, r > 0. An explicit expression for Qn,k,r and its asymptotic equivalent is computed. Assuming that all trees with n nodes are equally likely, the above relation implies that a tree has two deepest nodes on the average; the probabilities and higher moments about origin for this distribution are computed. Finally, assuming that all n-node trees with height k are equally likely, we show that such a tree has 4 deepest nodes on the average for fixed k.