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