A note on subtrees rooted along the primary path of a binary tree
Discrete Applied Mathematics
By: Brent M. Troutman and Michael R. Karlinger
Links
- More information: Publisher Index Page (via DOI)
- Download citation as: RIS | Dublin Core
Abstract
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.
| Publication type | Article |
|---|---|
| Publication Subtype | Journal Article |
| Title | A note on subtrees rooted along the primary path of a binary tree |
| Series title | Discrete Applied Mathematics |
| DOI | 10.1016/0166-218X(93)90181-M |
| Volume | 42 |
| Issue | 1 |
| Year Published | 1993 |
| Language | English |
| Publisher | Elsevier |
| Description | 7 p. |
| First page | 87 |
| Last page | 93 |
| Google Analytic Metrics | Metrics page |