DESCENDANTS AND ASCENDANTS IN BINARY TREES

ALOIS PANHOLZER AND HELMUT PRODINGER

Abstract. There are 3 classical algorithms to visit all the nodes of a binary tree, 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, …, 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 number of ascendants of node j and number of descendants of node j.

By appropriate trivariate generating functions we are able to find explicit formulæ for the expectation and the variance in all instances. The heavy computations that are necessary are facilitated by Maple and Zeilberger’s algorithm.

A similar problem comes from labelling the leaves from left to right by 0, 1, …, n and considering the statistic number of ascendants (=height) of leaf j. For this, Kirschenhofer [4] 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.

1. Introduction

Binary trees are not only interesting for combinatorialists, but also for computer scientists, since they constitute a basic data structure. As such, naturally, one needs traversal algorithms, which visit every node of the tree. Basically, there are 3 traversal algorithms, termed inorder, preorder, and postorder traversal. They are all recursive, the left subtree being treated before the right subtree, and they differ with respect to the visit of the root: first (preorder), middle (inorder), and last (postorder). As general references, we cite [8, 11, 12].

The performance of such algorithms is directly related to the following parameters, which are discussed in this paper: The number of ascendants of a node j, which is the number of nodes between the root and the node j, and the number of descendants of a node j, which is the number of nodes of the subtree rooted at node j. (The sum of the numbers of ascendants, over all j, is the so called path length, a quantity that is traditionally used to measure the complexity of tree algorithms. Clearly, it is independent of the labelling.)

The 3 traversal algorithms induce different labellings of the nodes with the natural numbers 1, 2, …; the first node visited gets number 1, and so on. Thus, if we have a binary tree with n internal nodes, it makes sense to speak about node j, for 1 ≤ j ≤ n. Compare with figures Fig. 1, Fig. 2, and Fig. 3.

From a probabilistic point of view, there are different models, e.g. the binary search trees, see e.g. [9]. In this paper, we concentrate on Catalan statistics, i.e. we assume that each binary tree with n internal nodes is equally likely.

We denote by B the family of binary trees, sometimes called extended binary trees, which is defined by the formal identity

Date: April 30, 1997.

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11]

Figure 1. A binary tree with 11 internal nodes, that are labelled by inorder traversal. Node 4 has 7 descendants and 2 ascendants, leave 6 has the height 5.

[figure: 4; 3; 5; 2; 7; 6; 8; 1; 10; 9; 11]

Figure 2. A binary tree with 11 internal nodes, that are labelled by preorder traversal. Node 3 has 7 descendants and 3 ascendants.

[figure: 1; 3; 2; 7; 4; 6; 5; 11; 8; 10; 9]

Figure 3. A binary tree with 11 internal nodes, that are labelled by postorder traversal. Node 5 has 1 descendant and 4 ascendants.

B =  + B  B  (1)

where ◯ is the symbol for an internal node and □ is the symbol for a leaf or external node.

The family of objects from B with exactly n internal nodes is denoted by B_{n}. Further we write B_{n} for the number of elements from B_{n}. Finally we denote with B(z) = ∑_{n≥0} B_{n}z^{n} the ordinary generating function of the B_{n}’s.

We are considering exact formulæ for the expectation and variance of the number of ascendants resp. descendants of node j in a random binary tree with n internal nodes (‘of size n’), for all 3 traversal algorithms.

A similar problem, namely the number of ascendants of the leaves (labelled from left to right by 0, 1, …, n) was considered by Kirschenhofer [4, 5]; he obtained an explicit formula for the expected value of leaf j. (Kirschenhofer’s definition of ‘height’ differs by 1 from our quantity.)

We rederive this and compute the variance additionally.

Apart from Kirschenhofer’s formula, all results seem to be new to the best of our knowledge. The reason that people were not considering such problems earlier might be related to the fact that we used the computer algebra system Maple quite heavily in this paper, and also the powerful algorithm of Zeilberger [10, 1], tools that were not generally available in the eighties. This approach might be less elegant than some clever ad hoc arguments, but it is definitely more flexible.

Except for two instances, we always get closed formulæ, although sometimes of a quite complicated nature. Therefore we give asymptotic equivalents in the last section. In these two cases, the answer is given in terms of a sum, which cannot be evaluated in closed form, which might be seen for instance from the asymptotic equivalent or also with Petkovšek’s algorithm [10].

The labelling by inorder traversal is equivalent to the sequence of min–turns; the j–th min–turn is defined to be the root of the smallest subtree containing the leaves labelled j − 1 and j. Some results about min–turns in the context of planted plane (=ordered) trees can be found in [3, 6, 7].

We would like to emphasize, however, that the spirit of this paper is on exact enumeration, not on asymptotics. Questions about limiting distributions, as treated in [2] (related to Kirschenhofer’s analysis) are not considered here and referred to further research.

Now we sketch the methodology that we use: We always translate the symbolic equation (1) directly into an algebraic equation for the (ordinary) trivariate generating functions

F (z, u, v) = ∑_{j≥1 (0)} ∑_{n≥j} ∑_{l≥0} f_{n,j,l} z^{n}u^{j}v^{l} ,  (2)

where the coefficients f_{n,j,l} are defined as the number of objects from B_{n}, where the node with label j has exactly l ascendants (or descendants, respectively). In short, we do not need to set up recurrences, but we use the symbolic method [12] to get the functions F (z, u, v) immediately. In general, when we are interested in a certain node j, we distinguish 3 cases, namely whether the root is this node or whether it lies in the left or right subtree. Consequently, the functional equations of later sections have 3 terms on the right hand side. In the instance of the next section, where we consider leaves, things are similar but slightly different.

To obtain the expectation E_{n,j}, the second factorial moment M_{n,j}^{(2)} and the variance V_{n,j} of the number of ascendants (or descendants, respectively) of the node with label j in a tree with n internal nodes (‘of size n’) we use the relations

\begin{aligned}E_{n,j} & = \frac{1}{B_{n}} [z^{n}u^{j}]\frac{∂}{∂v} F (z, u, v)|_{v=1} , \\ M_{n,j}^{(2)} & = \frac{1}{B_{n}} [z^{n}u^{j}]\frac{∂^{2}}{∂v^{2}} F (z, u, v)|_{v=1} , \\ V_{n,j} & = M_{n,j}^{(2)} + E_{n,j} − E_{n,j}^{2} . \end{aligned}  (3)

Using the symbolic method, the formal equation (1) translates into an equation of the generating function B(z);

B(z) = 1 + zB^{2}(z) .  (4)

From the solution

B(z) = \frac{1 − \sqrt{1 − 4z}}{2z}  (5)

we get the coefficients of B(z), the so called Catalan numbers

B_{n} = \frac{1}{n + 1}\binom{2n}{n} .  (6)

To shorten the presentation, we will use the following abbreviations throughout the whole paper;

X = \sqrt{1 − 4z} , Y = \sqrt{1 − 4zu} ,

G_{1}(z, u) = \frac{∂}{∂v} F (z, u, v)|_{v=1} , G_{2}(z, u) = \frac{∂^{2}}{∂v^{2}} F (z, u, v)|_{v=1} .

2. The height of leaves

We begin by reviewing and extending the results given by Kirschenhofer, but with the method mentioned above. We will translate the formal identity (1) into a functional equation for the trivariate generating function of the desired parameter.

In this section, f_{n,j,l} denotes the number of binary trees of size n, where the leaf labelled with j has height l. Then we get for the trivariate generating function F (z, u, v) of the f_{n,j,l}, defined as in (2) the functional equation

F (z, u, v) = v + zvF (z, u, v)B(z) + zuvF (z, u, v)B(zu) .  (7)

This leads immediately to the solution

F (z, u, v) = \frac{v}{1 − zvB(z) − zuvB(zu)} .  (8)

By differentiating (8) we get with the use of the abbreviations from above

G_{1}(z, u) = \frac{4}{(\sqrt{1 − 4z} + \sqrt{1 − 4zu})^{2}} = \frac{4}{(X + Y)^{2}} .  (9)

To find the coefficients in the expansion of \frac{1}{(X+Y)^{2}} , we can expand this expression about u = 1. This leads to

\frac{1}{(X + Y)^{2}} = ∑_{k≥0} \frac{1}{4(k + 2)}\binom{2(k + 1)}{k + 1}\frac{z^{k}}{(1 − 4z)^{k+1}} (u − 1)^{k} .

The coefficients are then given by the following sum

[z^{n}u^{j}]\frac{1}{(X + Y)^{2}} = ∑_{k=j}^{n} \frac{1}{4(k + 2)}\binom{2(k + 1)}{k + 1}\binom{n}{k}\binom{k}{j}(−1)^{k−j}4^{n−k} .  (10)

We find a closed form of this sum by using Zeilberger’s algorithm [10, 1]: We write

F (n, j, k) = \frac{1}{4(k + 2)}\binom{2(k + 1)}{k + 1}\binom{n}{k}\binom{k}{j}(−1)^{k−j}4^{n−k} ,

DESCENDANTS AND ASCENDANTS IN BINARY TREES 5

then Zeilberger’s algorithm finds the relation −2(n + 1)(2n − 2j + 3)F (n, j, k) + (n + 3)(n − j + 1)F (n + 1, j, k) = G(n, j, k + 1) − G(n, j, k) with

G(n, j, k) = R(n, j, k)F (n, j, k) and R(n, j, k) = −\frac{4(n + 1)(k + 2)(k − j)}{n + 1 − k} . (11)

To find an expression for the coefficients

[z^{n}u^{j}]\frac{1}{(X + Y)^{2}} = f(n, j) = ∑_{k∈ℤ}F (n, j, k) ,  (12)

we sum the above equation over all k ∈ ℤ.

The right side of the equation telescopes and we get the linear recurrence (for n ≥ j)

(n + 3)(n − j + 1)f(n + 1, j) = 2(n + 1)(2n − 2j + 3)f(n, j)  (13)

and the initial condition

f(j, j) = \frac{1}{4(j + 2)}\binom{2(j + 1)}{j + 1} .

This gives the desired result (for 0 ≤ j ≤ n)

[z^{n}u^{j}]\frac{1}{(X + Y)^{2}} = f(n, j) = \frac{(2j + 1)(2n − 2j + 1)}{2(n + 1)(n + 2)}\binom{2j}{j}\binom{2(n − j)}{n − j} .  (14)

Combining the equations (3), (6) and (14) we find again Kirschenhofer’s result [4]. Theorem 1. The expectation E_{n,j} of the height of the leaf with label j in a binary tree of size n, is given by

E_{n,j} = \frac{2(2j + 1)(2n − 2j + 1)}{n + 2} \begin{matrix}\binom{2j}{j} & \binom{2n−2j}{n−j} \\ ( & {2n \atop n} & ) \end{matrix}  for 0 ≤ j ≤ n .  (15)

Differentiating equation (8) twice and evaluating at v = 1 leads to

G_{2}(z, u) = \frac{16}{(X + Y)^{3}} − \frac{8}{(X + Y)^{2}} .  (16)

For this, we also need the coefficients of \frac{1}{(X+Y)^{3}} . To get them we make the following rearrangements;

\begin{matrix}\frac{1}{(X + Y)^{3}} = \frac{(X − Y)^{3}}{(X^{2} − Y^{2})^{3}} = \frac{X^{3} − 3X^{2}Y + 3XY^{2} − Y^{3}}{−64z^{3}(1 − u)^{3}} \\ = \frac{\sqrt{1 − 4z}}{(1 − u)^{3}} (−\frac{1}{16z^{3}} + \frac{1}{16z^{2}} + \frac{3u}{16z^{2}} ) + \frac{\sqrt{1 − 4zu}}{(1 − u)^{3}} (\frac{1}{16z^{3}} − \frac{3}{16z^{2}} − \frac{u}{16z^{2}} ) . \end{matrix} (17)

From this we see that

[z^{n}u^{j}]\frac{1}{(X + Y)^{3}} = [z^{n}u^{j}]\frac{\sqrt{1 − 4z}}{(1 − u)^{3}} (−\frac{1}{16z^{3}} + \frac{1}{16z^{2}} + \frac{3u}{16z^{2}} )  for 0 ≤ j ≤ n , (18)

which finally leads to

[z^{n}u^{j}]\frac{1}{(X + Y)^{3}} = \frac{3}{4} \frac{(2n + 1)(j + 1)(n − j + 1)}{(n + 1)(n + 2)(n + 3)}\binom{2n}{n} for 0 ≤ j ≤ n .  (19)

With the relations (3), (6), (14) and (19) we get

Lemma 1. The second factorial moment M_{n,j}^{(2)} of the height of the leaf with label j in a binary tree of size n is given for all 0 ≤ j ≤ n by

M_{n,j}^{(2)} = \frac{12(2n + 1)(j + 1)(n − j + 1)}{(n + 2)(n + 3)} − \frac{4(2j + 1)(2n − 2j + 1)}{n + 2} \begin{matrix}\binom{2j}{j} & \binom{2n−2j}{n−j} \\ ( & {2n \atop n} & ) \end{matrix} .  (20)

Observing (3) we get as a consequence

Theorem 2. The variance V_{n,j} of the height of the leaf with label j in a binary tree of size n, is given by

\begin{aligned}V_{n,j} & = \frac{12(j + 1)(2n + 1)(n − j + 1)}{(n + 2)(n + 3)} − \frac{2(2j + 1)(2n − 2j + 1)}{n + 2} \begin{matrix}\binom{2j}{j} & \binom{2n−2j}{n−j} \\ ( & {2n \atop n} & ) \end{matrix} \\ & − \frac{4(2j + 1)^{2}(2n − 2j + 1)^{2}}{(n + 2)^{2}} \begin{matrix}\binom{2j}{j} & 2 & \binom{2n−2j}{n−j} & 2 \\ \binom{2n}{n} & 2 \end{matrix}  for 0 ≤ j ≤ n . \end{aligned}  (21)

3. The number of descendants of nodes labelled by inorder traversal

Now we label the nodes of the tree by 1, 2, …, n as we visit them by inorder traversal. Then f_{n,j,l} denotes the number of binary trees of size n, where the node with label j has exactly l descendants. The trivariate generating function F (z, u, v) (compare (2)) fulfills the algebraic equation

F (z, u, v) = zuvB(zuv)B(zv) + zF (z, u, v)B(z) + zuB(zu)F (z, u, v) ,  (22)

which can be found by translating the formal equation (1) appropriately.

Therefore we have the following explicit formula

F (z, u, v) = \frac{zuvB(zv)B(zuv)}{1 − zB(z) − zuB(zu)} .  (23)

From this we get by differentiating

G_{1}(z, u) = \frac{1}{4z} (\frac{1}{XY} − \frac{1}{X} − \frac{1}{Y} + 1) .  (24)

The expansion of the coefficients is easy and we get

[z^{n}u^{j}]G_{1}(z, u) = [z^{n}u^{j}]\frac{1}{4zXY} = \frac{1}{4}\binom{2j}{j}\binom{2(n + 1 − j)}{n + 1 − j}  for 1 ≤ j ≤ n .  (25)

This gives with the relations (3), (6) and (25)

Theorem 3. The expectation E_{n,j} of the number of descendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is given by

E_{n,j} = \frac{n + 1}{4} \begin{matrix}\binom{2j}{j} & \binom{2(n+1−j)}{n+1−j} \\ ( & {2n \atop n} & ) \end{matrix}  for 1 ≤ j ≤ n .  (26)

Further we get from (23) the equation

\begin{aligned}G_{2}(z, u) & = \frac{(1 − X)(−4X^{2}Y^{2} + 3X^{2}Y^{3} + X^{2} − XY^{3} + 2XY^{2} − XY + Y^{2} − Y^{3})}{8zX^{3}Y^{3}} \\ & = \frac{1}{8z} (−3 + \frac{4}{X} − \frac{1}{X^{3}} ) + \frac{1}{8zY} (4 − \frac{6}{X} + \frac{1}{X^{2}} + \frac{1}{X^{3}} ) + \frac{1}{8zY^{2}} (\frac{1}{X} − \frac{1}{X^{2}} ) \\ & + \frac{1}{8zY^{3}} (−1 + \frac{1}{X} ) . \end{aligned} (27)

With the relations

[z^{n}u^{j}]\frac{1}{X^{p}Y^{q}} = [z^{j}u^{j}]\frac{1}{Y^{q}} [z^{n−j}]\frac{1}{X^{p}} = [z^{j}]\frac{1}{X^{q}} [z^{n−j}]\frac{1}{X^{p}}  for p, q ∈ ℕ  (28)

and

[z^{n}]\frac{1}{X} = \binom{2n}{n} , [z^{n}]\frac{1}{X^{2}} = 4^{n} , [z^{n}]\frac{1}{X^{3}} = (2n + 1)\binom{2n}{n}  (29)

the expansion of (27) is also easy to do (preferably with the use of a computer algebra system like Maple) and we get for 1 ≤ j ≤ n

[z^{n}u^{j}]G_{2}(z, u) = \frac{n − 1}{4}\binom{2j}{j}\binom{2n + 2 − 2j}{n + 1 − j} − \frac{1}{2}4^{n} + \frac{1}{8}4^{j}\binom{2n + 2 − 2j}{n + 1 − j} + \frac{1}{8}4^{n+1−j}\binom{2j}{j} . (30)

This leads to Lemma 2. The second factorial moment M_{n,j}^{(2)} of the number of descendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is given by

\begin{aligned}M_{n,j}^{(2)} & = \frac{(n − 1)(n + 1)}{4} \begin{matrix}\binom{2j}{j} & \binom{2n+2−2j}{n+1−j} \\ ( & {2n \atop n} & ) \end{matrix} \\ & + \frac{n + 1}{\binom{2n}{n}} [−\frac{1}{2}4^{n} + \frac{1}{8}4^{j}\binom{2n + 2 − 2j}{n + 1 − j} + \frac{1}{8}4^{n+1−j}\binom{2j}{j}] for 1 ≤ j ≤ n . \end{aligned}  (31)

So we get with (3) Theorem 4. The variance V_{n,j} of the number of descendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is given by

\begin{aligned}V_{n,j} & = \frac{n(n + 1)}{4} \begin{matrix}\binom{2j}{j} & \binom{2n+2−2j}{n+1−j} \\ ( & {2n \atop n} & ) \end{matrix} − \frac{(n + 1)^{2}}{16} \begin{matrix}\binom{2j}{j} & 2 & \binom{2n+2−2j}{n+1−j} & 2 \\ \binom{2n}{n} & 2 \end{matrix} \\ & + \frac{n + 1}{\binom{2n}{n}}[−\frac{1}{2}4^{n} + \frac{1}{8}4^{j}\binom{2n + 2 − 2j}{n + 1 − j} + \frac{1}{8}4^{n+1−j}\binom{2j}{j}]  for 1 ≤ j ≤ n . \end{aligned}  (32)

4. The number of ascendants of nodes labelled by inorder traversal

Here we denote by f_{n,j,l} the number of binary trees of size n, where the node labelled j by inorder traversal has exactly l ascendants.

For the usual trivariate generating function F (z, u, v) we get from (1) the functional equation

F (z, u, v) = zuvB(zu)B(z) + zvF (z, u, v)B(z) + zuvB(zu)F (z, u, v) ,  (33)

8 A. PANHOLZER AND H. PRODINGER

and thus

F (z, u, v) = \frac{zuvB(z)B(zu)}{1 − zvB(z) − zuvB(zu)} .  (34)

Hence it follows by differentiation from (34) that

G_{1}(z, u) = \frac{(1 − X)(1 − Y)}{z(X + Y)^{2}} = \frac{1}{z(X + Y)^{2}} − \frac{1}{z(X + Y)} + \frac{XY}{z(X + Y)^{2}} .  (35)

Therefore we need the coefficients of

\begin{aligned}[z^{n}u^{j}]\frac{1}{X + Y} & = [z^{n}u^{j}]\frac{X − Y}{X^{2} − Y^{2}} = [z^{n}u^{j}]\frac{\sqrt{1 − 4z} − \sqrt{1 − 4zu}}{−4z(1 − u)} \\ & = [z^{n}u^{j}] (−\frac{\sqrt{1 − 4z}}{4z(1 − u)}) = \frac{1}{2(n + 1)}\binom{2n}{n}  for 1 ≤ j ≤ n , \end{aligned}  (36)

and of

\begin{aligned}[z^{n}u^{j}]\frac{XY}{(X + Y)^{2}} & = 2[z^{n−1}u^{j}]\frac{1}{(X + Y)^{2}} + 2[z^{n−1}u^{j−1}]\frac{1}{(X + Y)^{2}} − [z^{n}u^{j}]\frac{1}{(X + Y)^{2}} \\ & = −\frac{(n − 1)(n − 8j) + 8j(j − 1)}{2n(n + 1)(n + 2)}\binom{2j}{j}\binom{2n − 2j}{n − j} for 1 ≤ j ≤ n . \end{aligned} (37)

Combining the equations (14), (36) and (37) we get for 1 ≤ j ≤ n

[z^{n}u^{j}]G_{1}(z, u) = \frac{4jn + n − 4j^{2} + 4j + 1}{2(n + 1)(n + 2)}\binom{2j}{j}\binom{2n + 2 − 2j}{n + 1 − j} − \frac{2n + 1}{(n + 1)(n + 2)}\binom{2n}{n} .

This leads to Theorem 5. The expectation E_{n,j} of the number of ascendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is given by

E_{n,j} = \frac{4jn + n − 4j^{2} + 4j + 1}{2(n + 2)} \begin{matrix}\binom{2j}{j} & \binom{2n+2−2j}{n+1−j} \\ ( & {2n \atop n} & ) \end{matrix} − \frac{2n + 1}{n + 2}  for 1 ≤ j ≤ n .  (38)

For G_{2}(z, u) we get from (34) by differentiating twice and evaluating at v = 1

\begin{aligned}G_{2}(z, u) & = −2\frac{(1 − X)(1 − Y)(X + Y − 2)}{z(X + Y)^{3}} \\ & = \frac{4XY}{z(X + Y)^{3}} + \frac{4}{z(X + Y)^{3}} − \frac{6}{z(X + Y)^{2}} − \frac{2XY}{z(X + Y)^{2}} + \frac{2}{z(X + Y)} . \end{aligned} (39)

To expand this expression we need additionally

\begin{matrix}[z^{n}u^{j}]\frac{XY}{(X + Y)^{3}} \\ = \frac{1}{2}[z^{n}u^{j}]\frac{1}{X + Y} − [z^{n}u^{j}]\frac{1}{(X + Y)^{3}} + 2[z^{n−1}u^{j}]\frac{1}{(X + Y)^{3}} + 2[z^{n−1}u^{j−1}]\frac{1}{(X + Y)^{3}} \\ = −\frac{2n^{2} − 15jn − 5n + 15j^{2} − 3}{4(n + 1)(n + 2)(n + 3)}\binom{2n}{n}  for 1 ≤ j ≤ n . \end{matrix} (40)

With the relations (39), (19), (36), (37) and (40) we get (for 1 ≤ j ≤ n)

[z^{n}u^{j}]G_{2}(z, u) = \frac{2(2n + 1)(6jn + 5n − 6j^{2} + 6j + 9)}{(n + 1)(n + 2)(n + 3)}\binom{2n}{n}

− \frac{12jn^{2} + 5n^{2} − 12j^{2}n + 32jn + 14n − 20j^{2} + 20j + 9}{(n + 1)(n + 2)(n + 3)}\binom{2j}{j}\binom{2n + 2 − 2j}{n + 1 − j} . (41)

From that we obtain Lemma 3. The second factorial moment M_{n,j}^{(2)} of the number of ascendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is for all 1 ≤ j ≤ n given by

\begin{aligned}M_{n,j}^{(2)} & = \frac{2(2n + 1)(6jn + 5n − 6j^{2} + 6j + 9)}{(n + 2)(n + 3)} \\ & − \frac{12jn^{2} + 5n^{2} − 12j^{2}n + 32jn + 14n − 20j^{2} + 20j + 9}{(n + 2)(n + 3)} \begin{matrix}\binom{2j}{j} & \binom{2n+2−2j}{n+1−j} \\ ( & {2n \atop n} & ) \end{matrix} . \end{aligned}  (42)

Thus we have Theorem 6. The variance V_{n,j} of the number of ascendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is for all 1 ≤ j ≤ n given by

\begin{aligned}V_{n,j} & = \frac{(2n + 1)(12jn^{2} + 7n^{2} − 12j^{2}n + 36jn + 26n − 24j^{2} + 24j + 27)}{(n + 2)^{2}(n + 3)} \\ & − \frac{4jn^{3}+5n^{3}−4j^{2}n^{2}+16jn^{2}+24n^{2}−12j^{2}n+44jn+43n−32j^{2}+32j+24}{2(n + 2)^{2}(n + 3)} \begin{matrix}\binom{2j}{j} & \binom{2n+2−2j}{n+1−j} \\ ( & {2n \atop n} & ) \end{matrix} \\ & − \frac{(4jn + n − 4j^{2} + 4j + 1)^{2}}{4(n + 2)^{2}} \begin{matrix}\binom{2j}{j} & 2 & \binom{2n+2−2j}{n+1−j} & 2 \\ \binom{2n}{n} & 2 \end{matrix} . \end{aligned}  (43)

5. The number of descendants of nodes labelled by preorder traversal

The following results are obtained by the same methods that we used in the instance of inorder traversal. So we can omit the details and only sketch the main steps to get analogous results in the case of preorder traversal (and postorder traversal, in later sections).

The trivariate generating function F (z, u, v) of the numbers f_{n,j,l}, counting the trees of size n, where the node with label j (labelled by preorder traversal) has exactly l descendants, is given by the functional equation

F (z, u, v) = zuvB^{2}(zv) + zuF (z, u, v)B(z) + zuB(zu)F (z, u, v) ,  (44)

and explicitly by

F (z, u, v) = \frac{zuvB^{2}(zv)}{1 − zuB(z) − zuB(zu)} .  (45)

From (45) we get

G_{1}(z, u) = \frac{2(1 − Y)}{X(1 + X)(X + Y)} = \frac{2}{X(X + Y)} + \frac{2}{1 + X} − \frac{2}{X} .  (46)

For 1 ≤ j ≤ n only the first summand contributes a nonzero coefficient. At first we get the sum

[z^{n}u^{j}]\frac{1}{X(X + Y)} = ∑_{k=j}^{n}[z^{k}u^{j}]\frac{1}{X + Y} [z^{n−k}]\frac{1}{X} = ∑_{k=j}^{n} \frac{1}{2(k + 1)}\binom{2k}{k}\binom{2n − 2k}{n − k} , (47)

which we evaluate as before with Zeilberger’s algorithm and obtain

[z^{n}u^{j}]\frac{1}{X(X + Y)} = \frac{2n + 1 − 2j}{2(n + 1)} \binom{2j}{j}\binom{2n − 2j}{n − j} .  (48)

This gives us

[z^{n}u^{j}]G_{1}(z, u) = \frac{2n + 1 − 2j}{n + 1} \binom{2j}{j}\binom{2n − 2j}{n − j} ,  (49)

and furthermore Theorem 7. The expectation E_{n,j} of the number of descendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n, is given by

E_{n,j} = (2n + 1 − 2j)\begin{matrix}\binom{2j}{j} & \binom{2n−2j}{n−j} \\ ( & {2n \atop n} & ) \end{matrix} .  (50)

For G_{2}(z, u) we get the following expression:

\begin{aligned}G_{2}(z, u) & = \frac{(1 − Y)(1 − X)(1 + 3X)}{X^{3}(1 + X)(X + Y)} \\ & = \frac{1}{X^{3}(X + Y)} + \frac{2}{X^{2}(X + Y)} − \frac{3}{X(X + Y)} + \frac{4}{X} − \frac{1}{X^{2}} − \frac{1}{X^{3}} − \frac{4}{X + 1} . \end{aligned} (51)

To read off the coefficients in this expression, we still need to expand \frac{1}{X^{2}(X+Y)} and \frac{1}{X^{3}(X+Y)}. From the equation

\frac{1}{X^{2}(X + Y)} = \frac{1}{X^{2}Y} + \frac{1}{4z(1 − u)Y} − \frac{1}{4z(1 − u)X}

we get the coefficients from \frac{1}{X^{2}(X+Y)}:

[z^{n}u^{j}]\frac{1}{X^{2}(X + Y)} = 4^{n−j}\binom{2j}{j} − \frac{1}{4}\binom{2(n + 1)}{n + 1} .  (52)

For the coefficients from \frac{1}{X^{3}(X+Y)} we first get the following sum

[z^{n}u^{j}]\frac{1}{X^{3}(X + Y)} = ∑_{k=j}^{n} \frac{1}{2(k + 1)}\binom{2k}{k}(2(n − k) + 1)\binom{2(n − k)}{n − k}

= (2n + 3) ∑_{k=j}^{n} \frac{1}{2(k + 1)}\binom{2k}{k}\binom{2(n − k)}{n − k} − ∑_{k=j}^{n} \binom{2k}{k}\binom{2(n − k)}{n − k} ,

which can be simplified using (47) and (48), yielding

[z^{n}u^{j}]\frac{1}{X^{3}(X + Y)} = \frac{(2n + 3)(2n + 1 − 2j)}{2(n + 1)}\binom{2j}{j}\binom{2(n − j)}{n − j} − ∑_{k=j}^{n} \binom{2k}{k}\binom{2(n − k)}{n − k} .(53)

It can be shown that the remaining sum cannot be brought into a closed form; see the general comment from the introduction.

Combining these results we get

\begin{aligned}[z^{n}u^{j}]G_{2}(z, u) & = \frac{n(2n − 2j + 1)}{n + 1}\binom{2j}{j}\binom{2n − 2j}{n − j} + 2 · 4^{n−j}\binom{2j}{j} − \frac{1}{2}\binom{2n + 2}{n + 1} \\ & − ∑_{k=j}^{n} \binom{2k}{k}\binom{2n − 2k}{n − k} \end{aligned} (54)

and thus Lemma 4. The second factorial moment M_{n,j}^{(2)} of the number of descendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n is given by

\begin{aligned}M_{n,j}^{(2)} & = n(2n − 2j + 1)\begin{matrix}\binom{2j}{j} & \binom{2n−2j}{n−j} \\ ( & {2n \atop n} & ) \end{matrix} + 2(n + 1)\frac{4^{n−j}\binom{2j}{j}}{\binom{2n}{n}} − 2n − 1 \\ & − \frac{n + 1}{\binom{2n}{n}} ∑_{k=j}^{n} \binom{2k}{k}\binom{2n − 2k}{n − k}  for 1 ≤ j ≤ n . \end{aligned}  (55)

This leads immediately to Theorem 8. The variance V_{n,j} of the number of descendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n, is given by

\begin{aligned}V_{n,j} & = (n + 1)(2n − 2j + 1)\begin{matrix}\binom{2j}{j} & \binom{2n−2j}{n−j} \\ ( & {2n \atop n} & ) \end{matrix} + 2(n + 1)\frac{4^{n−j}\binom{2j}{j}}{\binom{2n}{n}} − 2n − 1 \\ & − (2n + 1 − 2j)^{2} \begin{matrix}\binom{2j}{j} & 2 & \binom{2n−2j}{n−j} & 2 \\ \binom{2n}{n} & 2 \end{matrix} − \frac{n + 1}{\binom{2n}{n}} ∑_{k=j}^{n} \binom{2k}{k}\binom{2n − 2k}{n − k} for 1 ≤ j ≤ n . \end{aligned}

We remark that the full sum can be easily evaluated;

∑_{k=0}^{n} \binom{2k}{k}\binom{2n − 2k}{n − k} = 4^{n} .  (56)

This relation might be useful if j is rather small; the sum can always be rewritten so that it has not more than roughly n/2 terms.

6. The number of ascendants of nodes labelled by preorder traversal

Now f_{n,j,l} counts the number of binary trees of size n, where the node with label j has exactly l ascendants.

For the usual trivariate generating function we get the relation

F (z, u, v) = zuvB^{2}(z) + zuvF (z, u, v)B(z) + zuvB(zu)F (z, u, v) ,  (57)

from which we obtain

F (z, u, v) = \frac{zuvB^{2}(z)}{1 − zuvB(z) − zuvB(zu)} .  (58)

To expand the quantity

G_{1}(z, u) = \frac{4(1 − Y)}{(1 + Y)(X + Y)^{2}} = \frac{2}{zu(X + Y)^{2}} − \frac{4}{(X + Y)^{2}} − \frac{2Y}{zu(X + Y)^{2}}  (59)

we still need the following expansion;

\begin{aligned}[z^{n}u^{j}]\frac{Y}{(X + Y)^{2}} & = [z^{n}u^{j}]\frac{XY}{(X + Y)^{3}} + [z^{n}u^{j}]\frac{1}{(X + Y)^{3}} − 4[z^{n−1}u^{j−1}]\frac{1}{(X + Y)^{3}} \\ & = \frac{2n + 1 − 3j}{2(n + 1)(n + 2)}\binom{2n}{n} . \end{aligned} (60)

Hence we have

[z^{n}u^{j}]G_{1}(z, u) = \frac{(jn + 2n − j)(2n − 2j + 1)}{(n + 1)(n + 2)(n + 3)}\binom{2j + 2}{j + 1}\binom{2n − 2j}{n − j} − \frac{2n − 3j}{(n + 2)(n + 3)}\binom{2n + 2}{n + 1} ,

which proves

Theorem 9. The expectation E_{n,j} of the number of ascendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n, is given for all 1 ≤ j ≤ n by

E_{n,j} = \frac{(jn + 2n − j)(2n − 2j + 1)}{(n + 2)(n + 3)} \begin{matrix}\binom{2j+2}{j+1} & \binom{2n−2j}{n−j} \\ ( & {2n \atop n} & ) \end{matrix} − \frac{2(2n + 1)(2n − 3j)}{(n + 2)(n + 3)} .  (61)

To get the coefficients in the expansion of

\begin{aligned}G_{2}(z, u) & = 8\frac{(1 − Y)^{2}(X + Y + 2)}{(X + Y)^{3}(1 + Y)^{2}} \\ & = \frac{8(1 − 4uz + 2u^{2}z^{2})}{u^{2}z^{2}} \frac{1}{(X + Y)^{3}} − \frac{8(1 − 2uz)}{u^{2}z^{2}} \frac{Y}{(X + Y)^{3}} \\ & + \frac{4(1 − 4uz + 2u^{2}z^{2})}{u^{2}z^{2}} \frac{1}{(X + Y)^{2}} − \frac{4(1 − 2uz)}{u^{2}z^{2}} \frac{Y}{(X + Y)^{2}} \end{aligned}  (62)

we still have to compute the coefficients [z^{n}u^{j}]\frac{Y}{(X+Y)^{3}} .

As a first step, we get them as a sum;

\begin{aligned}[z^{n}u^{j}] & \frac{Y}{(X + Y)^{3}} = ∑_{k=0}^{j}[z^{k}u^{k}]Y [z^{n−k}u^{j−k}]\frac{1}{(X + Y)^{3}} \\ & = −\frac{3}{2} ∑_{k=0}^{j} \frac{(2k − 2)!}{k!(k − 1)!} \frac{(2(n − k) + 1)(j − k + 1)(n − j + 1)}{(n − k + 1)(n − k + 2)(n − k + 3)}\binom{2(n − k)}{n − k} , \end{aligned} (63)

that is valid by observing the limiting relation \frac{(−2)!}{(−1)!} = −\frac{1}{2} .

Zeilberger’s algorithm evaluates this sum as before, and we obtain

[z^{n}u^{j}]\frac{Y}{(X + Y)^{3}} = \frac{(2j + 1)(2n + 1 − 2j)(3n − 4j + 3)}{4(n + 1)(n + 2)(n + 3)}\binom{2j}{j}\binom{2n − 2j}{n − j} .  (64)

Hence we get

\begin{matrix}[z^{n}u^{j}]G_{2}(z, u) = \frac{4(2n+1)(3jn^{3}+23n^{3}−3j^{2}n^{2}−51jn^{2}+18n^{2}+33j^{2}n−42jn+19n+30j^{2}−30j)}{(n + 1)(n + 2)(n + 3)(n + 4)(n + 5)}\binom{2n}{n} \\ − \frac{(n−j+1)(11j^{2}n^{3}+47jn^{3}+46n^{3}−16j^{3}n^{2}−68j^{2}n^{2}−44jn^{2}+36n^{2}−35j^{2}n−35jn+38n+16j^{3}+20j^{2}−16j)}{(j + 2)(n + 1)(n + 2)(n + 3)(n + 4)(n + 5)} × \\ × \binom{2j + 2}{j + 1}\binom{2n + 2 − 2j}{n + 1 − j} \end{matrix}(65)

and thus Lemma 5. The second factorial moment M_{n,j}^{(2)} of the number of ascendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n is given by

\begin{matrix}M_{n,j}^{(2)} = \frac{4(2n+1)(3jn^{3}+23n^{3}−3j^{2}n^{2}−51jn^{2}+18n^{2}+33j^{2}n−42jn+19n+30j^{2}−30j)}{(n + 2)(n + 3)(n + 4)(n + 5)} \\ − \frac{(n−j+1)(11j^{2}n^{3}+47jn^{3}+46n^{3}−16j^{3}n^{2}−68j^{2}n^{2}−44jn^{2}+36n^{2}−35j^{2}n−35jn+38n+16j^{3}+20j^{2}−16j)}{(j + 2)(n + 2)(n + 3)(n + 4)(n + 5)} × \\ × \begin{matrix}\binom{2j+2}{j+1} & \binom{2n+2−2j}{n+1−j} \\ ( & {2n \atop n} & ) \end{matrix} . \end{matrix}(66)

This leads to the following Theorem 10. The variance V_{n,j} of the number of ascendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n, is given by

\begin{aligned}V_{n,j} & = \frac{2n(2n+1)(6n^{4}j+28n^{4}−6n^{3}j^{2}−21n^{3}j+86n^{3}−60jn^{2}−40n^{2}+12j^{2}n+297jn−62n−186j^{2}+138j−12)}{(n + 2)^{2}(n + 3)^{2}(n + 4)(n + 5)} \\ & − \frac{Ψ}{(j + 1)(j + 2)(n + 2)^{2}(n + 3)^{2}(n + 4)(n + 5)} \begin{matrix}\binom{2j}{j} & \binom{2n−2j}{n−j} \\ ( & {2n \atop n} & ) \end{matrix} \\ & − \frac{4(jn + 2n − j)^{2}(2n − 2j + 1)^{2}}{(n + 2)^{2}(n + 3)^{2}} \begin{matrix}\binom{2j+2}{j+1} & 2 & \binom{2n−2j}{n−j} & 2 \\ \binom{2n}{n} & 2 \end{matrix} , \end{aligned} (67)

with Ψ = 2(2j +1)(2n−2j +1)(5j^{2}n^{5} +26jn^{5} +24n^{5} −8j^{3}n^{4} −79j^{2}n^{4} −152jn^{4} −132n^{4} +44j^{3}n^{3} − 51j^{2}n^{3} −554jn^{3} −864n^{3} +200j^{3}n^{2} +919j^{2}n^{2} +1112jn^{2} −444n^{2} −188j^{3}n−242j^{2}n+528jn− 24n − 48j^{3} − 120j^{2} + 48j) .

7. The number of descendants of nodes labelled by postorder traversal

Now f_{n,j,l} counts the number of binary trees of size n, where the node with label j (labelled by postorder traversal) has exactly l descendants.

For the trivariate generating function we get the relation

F (z, u, v) = zuvB^{2}(zuv) + zF (z, u, v)B(z) + zB(zu)F (z, u, v) ,  (68)

from which we obtain

F (z, u, v) = \frac{zuvB^{2}(zuv)}{1 − zB(z) − zB(zu)} .  (69)

From the expression

G_{1}(z, u) = \frac{2(1 − Y)}{Y (1 + X)(X + Y)} = \frac{1}{2zXY} − \frac{2}{X(X + Y)} − \frac{1}{2zY}  (70)

we get the coefficients

[z^{n}u^{j}]G_{1}(z, u) = \frac{1}{2}[z^{n+1}u^{j}]\frac{1}{XY} − 2[z^{n}u^{j}]\frac{1}{X(X + Y)} = \frac{j}{2(n + 1)}\binom{2j}{j}\binom{2n + 2 − 2j}{n + 1 − j} .(71)

This leads to Theorem 11. The expectation E_{n,j} of the number of descendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n, is given by

E_{n,j} = \frac{j}{2} \begin{matrix}\binom{2j}{j} & \binom{2n+2−j}{n+1−j} \\ ( & {2n \atop n} & ) \end{matrix} .  (72)

Furthermore we get for G_{2}(z, u)

\begin{aligned}G_{2}(z, u) & = \frac{(1 − Y)^{2}(1 + 3Y)}{Y^{3}(1 + X)(X + Y)} \\ & = 3\frac{1}{X(X + Y)} + 2\frac{1}{X^{2}(X + Y)} − \frac{1}{X^{3}(X + Y)} − \frac{3}{4} \frac{X}{zY} + \frac{1}{2} \frac{X}{zY^{2}} + \frac{1}{4} \frac{X}{zY^{3}} \\ & − 3\frac{1}{XY} − 2\frac{1}{X^{2}Y} + \frac{1}{X^{3}Y} + 2\frac{1}{XY^{2}} − \frac{1}{X^{2}Y^{2}} + \frac{1}{XY^{3}} + \frac{3}{4} \frac{1}{zY} − \frac{1}{2} \frac{1}{zY^{2}} − \frac{1}{4} \frac{1}{zY^{3}} . \end{aligned} (73)

Combining the earlier results we get for the coefficients

\begin{aligned}[z^{n}u^{j}]G_{2}(z, u) & = \frac{nj}{2(n + 1)}\binom{2j}{j}\binom{2n + 2 − 2j}{n + 1 − j} + \frac{1}{2}4^{j}\binom{2n + 2 − 2j}{n + 1 − j} − \frac{1}{2}\binom{2n + 2}{n + 1} \\ & − 4^{n} + ∑_{k=j}^{n} \binom{2k}{k}\binom{2n − 2k}{n − k} . \end{aligned} (74)

This leads to Lemma 6. The second factorial moment M_{n,j}^{(2)} of the number of descendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n is given by

\begin{aligned}M_{n,j}^{(2)} & = \frac{nj}{2} \begin{matrix}\binom{2j}{j} & \binom{2n+2−2j}{n+1−j} \\ ( & {2n \atop n} & ) \end{matrix} + \frac{n + 1}{2} \frac{4^{j}\binom{2n+2−2j}{n+1−j}}{\binom{2n}{n}} − (n + 1)\frac{4^{n}}{\binom{2n}{n}} − 2n − 1 \\ & + \frac{n + 1}{\binom{2n}{n}} ∑_{k=j}^{n} \binom{2k}{k}\binom{2n − 2k}{n − k}  for 1 ≤ j ≤ n . \end{aligned}  (75)

This leads immediately to Theorem 12. The variance V_{n,j} of the number of descendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n, is given by

\begin{aligned}V_{n,j} & = \frac{(n + 1)j}{2} \begin{matrix}\binom{2j}{j} & \binom{2n+2−2j}{n+1−j} \\ ( & {2n \atop n} & ) \end{matrix} + \frac{n + 1}{2} \frac{4^{j}\binom{2n+2−2j}{n+1−j}}{\binom{2n}{n}} − (n + 1)\frac{4^{n}}{\binom{2n}{n}} − 2n − 1 \\ & − \frac{j^{2}}{4} \begin{matrix}\binom{2j}{j} & 2 & \binom{2n+2−2j}{n+1−j} & 2 \\ \binom{2n}{n} & 2 \end{matrix} + \frac{n + 1}{\binom{2n}{n}} ∑_{k=j}^{n} \binom{2k}{k}\binom{2n − 2k}{n − k}  for 1 ≤ j ≤ n . \end{aligned}  (76)

8. The number of ascendants of nodes labelled by postorder traversal

Here we denote by f_{n,j,l} the number of binary trees of size n, where the node labelled j by postorder traversal has exactly l ascendants.

For the trivariate generating function F (z, u, v) we get the relation

F (z, u, v) = zuvB^{2}(zu) + zvF (z, u, v)B(z) + zvB(zu)F (z, u, v) ,  (77)

and explicitly

F (z, u, v) = \frac{zuvB^{2}(zu)}{1 − zvB(z) − zvB(zu)} .  (78)

From this equation we derive

G_{1}(z, u) = \frac{4(1 − Y)(1 + Y)}{(1 + X)^{2}(X + Y)^{2}} = \frac{2u}{z(X + Y)^{2}} − \frac{4u}{(X + Y)^{2}} − \frac{2u}{z} \frac{X}{(X + Y)^{2}} .  (79)

In order to get the coefficients in the expansion of the above expression we need

[z^{n}u^{j}]\frac{X}{(X + Y)^{2}} = [z^{n}u^{j}]\frac{1}{X + Y} − [z^{n}u^{j}]\frac{Y}{(X + Y)^{2}} = −\frac{n − 1 − 3j}{2(n + 1)(n + 2)}\binom{2n}{n} . (80)

With this we get

[z^{n}u^{j}]G_{1}(z, u) = \frac{n + 3 − 3j}{(n + 2)(n + 3)}\binom{2n + 2}{n + 1} + \frac{j(n^{2} − jn + 2n + j − 1)}{2(n + 1)(n + 2)(n + 3)}\binom{2j}{j}\binom{2(n + 2 − j)}{n + 2 − j} (81)

and Theorem 13. The expectation E_{n,j} of the number of ascendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n, is given for all 1 ≤ j ≤ n by

E_{n,j} = \frac{2(2n + 1)(n + 3 − 3j)}{(n + 2)(n + 3)} + \frac{j(n^{2} − jn + 2n + j − 1)}{2(n + 2)(n + 3)} \begin{matrix}\binom{2j}{j} & \binom{2(n+2−j)}{n+2−j} \\ ( & {2n \atop n} & ) \end{matrix} .  (82)

Furthermore we consider the coefficients of

\begin{aligned}G_{2}(z, u) & = 8\frac{(1 − Y)(1 + Y)(1 − X)(X + Y + 2)}{(1 + X)^{3}(X + Y)^{3}} \\ & = −\frac{8(1 − 2z)u}{z^{2}} \frac{X}{(X + Y)^{3}} + \frac{8(1 − 4z + 2z^{2})u}{z^{2}} \frac{1}{(X + Y)^{3}} \\ & − \frac{4(1 − 2z)u}{z^{2}} \frac{X}{(X + Y)^{2}} + \frac{4(1 − 4z + 2z^{2})}{z^{2}} \frac{1}{(X + Y)^{2}} . \end{aligned}  (83)

To do this we need

\begin{aligned}[z^{n}u^{j}]\frac{X}{(X + Y)^{3}} & = [z^{n}u^{j}]\frac{1}{(X + Y)^{2}} − [z^{n}u^{j}]\frac{Y}{(X + Y)^{3}} \\ & = −\frac{(2j + 1)(2n − 2j + 1)(n − 4j − 3)}{4(n + 1)(n + 2)(n + 3)}\binom{2j}{j}\binom{2(n − j)}{n − j} . \end{aligned}  (84)

Then we get

\begin{aligned}[z^{n}u^{j}]G_{2}(z, u) & = \frac{Ψ}{(n + 3 − j)(n + 1)(n + 2)(n + 3)(n + 4)(n + 5)}\binom{2j}{j}\binom{2(n + 2 − j)}{n + 2 − j} \\ & + \frac{4(2n+1)(3jn^{3}+2n^{3}−3j^{2}n^{2}−9jn^{2}+18n^{2}+33j^{2}n−84jn+40n+30j^{2}−30j)}{(n + 1)(n + 2)(n + 3)(n + 4)(n + 5)}\binom{2n}{n} , \end{aligned}(85)

where Ψ is given in Lemma 7, whence we have

Lemma 7. The second factorial moment M_{n,j}^{(2)} of the number of ascendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n is given by

\begin{aligned}M_{n,j}^{(2)} & = \frac{4(2n+1)(3jn^{3}+2n^{3}−3j^{2}n^{2}−9jn^{2}+18n^{2}+33j^{2}n−84jn+40n+30j^{2}−30j)}{(n + 2)(n + 3)(n + 4)(n + 5)} \\ & + \frac{Ψ}{(n + 3 − j)(n + 2)(n + 3)(n + 4)(n + 5)} \begin{matrix}\binom{2j}{j} & \binom{2(n+2−j)}{n+2−j} \\ ( & {2n \atop n} & ) \end{matrix} \end{aligned}  (86)

with Ψ = j(5n^{5} − 26jn^{4} + 47n^{4} + 37j^{2}n^{3} − 163jn^{3} + 143n^{3} − 16j^{3}n^{2} + 116j^{2}n^{2} − 250jn^{2} + 129n^{2} − 13j^{2}n + 31jn − 40n + 16j^{3} − 68j^{2} + 72j − 20) .

Also we get Theorem 14. The variance V_{n,j} of the number of ascendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n, is given by

\begin{aligned}V_{n,j} & = \frac{2n(2n+1)(6jn^{4}+n^{4}+11n^{3}+33jn^{3}−6j^{2}n^{3}+36jn^{2}+35n^{2}+12j^{2}n+51jn+13n−186j^{2}+234j−60)}{(n + 2)^{2}(n + 3)^{2}(n + 4)(n + 5)} \\ & + \frac{Ψ}{2(n + 3 − j)(n + 2)^{2}(n + 3)^{2}(n + 4)(n + 5)} \begin{matrix}\binom{2j}{j} & \binom{2(n+2−j)}{n+2−j} \\ ( & {2n \atop n} & ) \end{matrix} \\ & − \frac{j^{2}(n^{2} − jn + 2n + j − 1)^{2}}{4} \begin{matrix}\binom{2j}{j} & 2 & \binom{2(n+2−j)}{n+2−j} & 2 \\ \binom{2n}{n} & 2 \end{matrix} \end{aligned} (87)

with Ψ = j(3n^{7} − 14jn^{6} + 23n^{6} + 19j^{2}n^{5} − 38jn^{5} − 2n^{5} − 8j^{3}n^{4} − 29j^{2}n^{4} + 428jn^{4} − 436n^{4} + 44j^{3}n^{3} − 681j^{2}n^{3} + 1950jn^{3} − 1271n^{3} + 200j^{3}n^{2} − 955j^{2}n^{2} + 1794jn^{2} − 1003n^{2} − 188j^{3}n + 950j^{2}n − 1048jn + 262n − 48j^{3} + 264j^{2} − 336j + 120) .

9. Asymptotics

In this section we evaluate our findings asymptotically, under the assumptions j fixed; j ∼ ρn, with 0 < ρ < 1; n − j fixed. All formulæ are easy to obtain, thus we only collect them in a table.

j fixed  j ∼ ρn  l := n − j fixed
E_{n,j}  (2j+1)\binom{2j}{j}4^{−j+1}  8^{\begin{matrix}√ & \overline{ρ(1−ρ)} \\ √ & \overline{π} \end{matrix}} \sqrt{n}  (2l+1)\binom{2l}{l}4^{−l+1}

Ascendants of leaf V_{n,j}

\begin{matrix}24(j+1) \\ −16(2j+1)^{2}\binom{2j}{j}^{2}4^{−2j} \\ −(2j+1)\binom{2j}{j}4^{−j+1} \end{matrix}

8\frac{ρ(1−ρ)(3π−8)}{π}n

\begin{matrix}24(l+1) \\ −16(2l+1)^{2}\binom{2l}{l}^{2}4^{−2l} \\ −(2l+1)\binom{2l}{l}4^{−l+1} \end{matrix}

E_{n,j}  \binom{2j}{j}4^{−j}n  \sqrt[\frac{1}{\sqrt{π}\sqrt{ρ(1−ρ)}}]{n}  \binom{2(l+1)}{l+1}4^{−(l+1)}n

Descendants V_{n,j} (\binom{2j}{j}4^{−j}−\binom{2j}{j}^{2}4^{−2j})n^{2} (\frac{1}{\sqrt{π}\sqrt{ρ(1−ρ)}} − \frac{\sqrt{π}}{2} )n^{3/2}  \begin{matrix}(\binom{2(l+1)}{l+1}4^{−(l+1)} \\ −\binom{2(l+1)}{l+1}^{2}4^{−2(l+1)})n^{2} \end{matrix}

Inorder  E_{n,j}  2(4j+1)\binom{2j}{j}4^{−j}−2  8^{\begin{matrix}√ & \overline{ρ(1−ρ)} \\ √ & \overline{π} \end{matrix}} \sqrt{n}  2(4(l+1)+1)\binom{2(l+1)}{l+1}4^{−(l+1)}−2

Ascendants V_{n,j}  \begin{matrix}24j+14 \\ −2(4j+5)\binom{2j}{j}4^{−j} \\ −4(4j+1)^{2}\binom{2j}{j}^{2}4^{−2j} \end{matrix}  8\frac{ρ(1−ρ)(3π−8)}{π}n \begin{matrix}24(l+1)+14 \\ −2(4(l+1)+5)\binom{2(l+1)}{l+1}4^{−(l+1)} \\ −4(4(l+1)+1)^{2}\binom{2(l+1)}{l+1}^{2}4^{−2(l+1)} \end{matrix}

E_{n,j}  2\binom{2j}{j}4^{−j}n  2\begin{matrix}√ & \overline{1−ρ} \\ \sqrt{π} & \sqrt{ρ} \end{matrix} \sqrt{n}  (2l+1)\binom{2l}{l}4^{−l}

Descendants V_{n,j}  \begin{matrix}(2\binom{2j}{j}4^{−j} \\ −\binom{2j}{j}^{2}4^{−2j+1})n^{2} \end{matrix}  − arcsin \sqrt{1−ρ})n^{3/2}^{\frac{2}{\sqrt{π}} (\begin{matrix}^{√} & \overline{1−ρ} \\ ^{√} & \overline{ρ} \end{matrix}}  \begin{matrix}\frac{2}{3} l(l+1)\binom{2(l+1)}{l+1}4^{−(l+1)}+l+1 \\ −4(l+1)^{2}\binom{2(l+1)}{l+1}^{2}4^{−2(l+1)} \end{matrix}

Preorder  E_{n,j} 2(j+2)\binom{2(j+1)}{j+1}4^{−j}−8  8^{\begin{matrix}√ & \overline{ρ(1−ρ)} \\ √ & \overline{π} \end{matrix}} \sqrt{n}  4(2l+1)\binom{2l}{l}4^{−l}+4
Ascendants V_{n,j} \begin{matrix}24j+112 \\ −4(j+2)^{2}\binom{2(j+1)}{j+1}^{2}4^{−2j} \\ − \frac{2(j+4)(5j+6)}{j+2} \binom{2(j+1)}{j+1}4^{−j} \end{matrix} 8\frac{ρ(1−ρ)(3π−8)}{π}n  \begin{matrix}24l+28 \\ −16(2l+1)^{2}\binom{2l}{l}^{2}4^{−2l} \\ +12(2l+1)\binom{2l}{l}4^{−l} \end{matrix}

E_{n,j}  2j\binom{2j}{j}4^{−j}  2\begin{matrix}√ & \overline{ρ} \\ \sqrt{π} & \sqrt{1−ρ} \end{matrix} \sqrt{n}  2\binom{2(l+1)}{l+1}4^{−(l+1)}n

Descendants V_{n,j}  \begin{matrix}\frac{2j(j−1)}{3} \binom{2j}{j}4^{−j}+j \\ −4j^{2}\binom{2j}{j}^{2}4^{−2j} \end{matrix}  + arcsin \sqrt{1−ρ}− \frac{π}{2} )n^{3/2}^{\frac{2}{\sqrt{π}} (\begin{matrix}^{√} & \overline{ρ} \\ ^{√} & \overline{1−ρ} \end{matrix}}  \begin{matrix}(2\binom{2(l+1)}{l+1}4^{−(l+1)} \\ −4\binom{2(l+1)}{l+1}^{2}4^{−2(l+1)})n^{2} \end{matrix}

Postorder  E_{n,j}  8j\binom{2j}{j}4^{−j}+4  8^{\begin{matrix}√ & \overline{ρ(1−ρ)} \\ √ & \overline{π} \end{matrix}} \sqrt{n}  2(l+3)\binom{2(l+2)}{l+2}4^{−(l+1)}−8

Ascendants V_{n,j}  \begin{matrix}24j+4 \\ +24j\binom{2j}{j}4^{−j} \\ −64j^{2}\binom{2j}{j}^{2}4^{−2j} \end{matrix}  8\frac{ρ(1−ρ)(3π−8)}{π}n  \begin{matrix}24l+136 \\ −4(l+3)^{2}\binom{2(l+2)}{l+2}^{2}4^{−2(l+1)} \\ − \frac{2(l+5)(5l+11)}{l+3} \binom{2(l+2)}{l+2}4^{−(l+1)} \end{matrix}

Table 1. Asymptotic results related to all the explicit formulae in the paper

References

[1] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics (Second Edition). Addison Wesley, 1994.

[2] W. Gutjahr and G. Pflug. The asymptotic contour process of a binary tree is a Brownian excursion. Stochastic processes and their applications, 41:69–89, 1992.

[3] R. Kemp. On the average oscillation of a stack. Combinatorica, 2:157–176, 1982.

[4] P. Kirschenhofer. On the height of leaves in binary trees. Journal of Combinatorics, Information and System Sciences, 8:44 –60, 1983.

[5] P. Kirschenhofer. Some new results on the average height of binary trees. Ars Combinatoria, 16 A:255– 260, 1983.

[6] P. Kirschenhofer and H. Prodinger. On the average hyperoscillations of planted plane trees. Combinatorica, 2:177–186, 1982.

[7] P. Kirschenhofer and H. Prodinger. On the average oscillation of the contour of monotonically labelled ordered trees. In Proceedings of the Second World Conference on Mathematics at the Service of Man (Las Palmas), pages 394–399, 1982.

[8] D. E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms. Addison-Wesley, 1968. Second edition, 1973.

[9] C. Martínez and H. Prodinger. On the number of descendants and ascendants in random search trees. Submitted, 1996.

[10] M. Petkovšek, H. Wilf, and D. Zeilberger. A = B. A.K. Peters, Ltd., 1996.

[11] R. Sedgewick. Algorithms. Addison-Wesley, 1991.

[12] R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley, 1996.

Institut für Algebra und Diskrete Mathematik, Technical University of Vienna, Wiedner Hauptstrasse 8–10, A-1040 Vienna, Austria.

  E-mail address: e9125354@fbma.tuwien.ac.at (Alois Panholzer)
  E-mail address: Helmut.Prodinger@tuwien.ac.at
  WWW-address: http://info.tuwien.ac.at/theoinf/proding.htm