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)