#
Descendants and Ascendants in binary trees

\begin{abstract}
There are 3 classical algorithms to visit all the nodes of a binary tree,
\hbox{preorder--,} {inorder--,} and postorder traversal. From this one
gets a natural labelling
of the $n$ internal nodes of a binary tree by the numbers $1,2,\dots,n$,
indicating the sequence in which the nodes are visited. For given $n$
(size of the tree) and $j$ (a number between 1 and $n$) we consider the statistics
{\it number of ascendants of node $j$\/}
and
{\it number of descendants of node $j$\/}.
By appropriate trivariate generating functions we are able to find {\sl explicit\/}
formul{\ae} for the expectation and the variance in all instances.
The heavy computations that are necessary are facilitated by {\sc Maple}
and Zeilberger's algorithm.
A similar problem comes from labelling the leaves from left to right by
$0,1,\dots,n$ and considering the statistic
{\it number of ascendants (=height) of leaf $j$}. For this, Kirschenhofer
\cite{Kirschenhofer83} has computed the average. With our approach, we are
able to get the variance, too.
In a last section, a table with asymptotic equivalents is provided for the
reader's convenience.
\end{abstract}

This paper is available in the Tex, Dvi, and PostScript format.

helmut@gauss.cam.wits.ac.za,

(Back to List of Papers)