A note on subtrees rooted along the primary path of a binary tree
Let Fn denote the set of rooted binary plane trees with n external nodes, for given T∈Fn let ui(T) be the altitude i node along the primary path of T, and let δi(T) denote the number of external nodes in the induced subtree rooted at ui(T). We set δi(T) = 0 if i is greater than the length of the primary path of T. We prove limn→∞ ∑i≤x/n En{δi}/∑i<∞ En{δi} = G(x), where En denotes the average over trees T∈Fn and where the distribution function G is determined by its moments, for which we present an explicit expression.
Citation Information
Publication Year | 1993 |
---|---|
Title | A note on subtrees rooted along the primary path of a binary tree |
DOI | 10.1016/0166-218X(93)90181-M |
Authors | Brent M. Troutman, Michael R. Karlinger |
Publication Type | Article |
Publication Subtype | Journal Article |
Series Title | Discrete Applied Mathematics |
Index ID | 70018378 |
Record Source | USGS Publications Warehouse |