Skip to main content
U.S. flag

An official website of the United States government

A note on subtrees rooted along the primary path of a binary tree

January 1, 1993

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 Eni}/∑i<∞ Eni} = 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 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
Was this page helpful?