THE LEVEL OF NODES IN HEAP ORDERED TREES

HELMUT PRODINGER

Abstract. A heap ordered tree with n nodes (“size n”) is a planted plane tree together with a bijection from the nodes to the set {1, …, n} which is monotonically increasing when going from the root to the leaves. We consider the level of the node j in a (random) heap ordered tree of size n ≥ j. This distribution does not depend on n. Precise expressions are derived for the expectation, the variance, and the probability distribution.

1. Heap ordered trees

A heap ordered tree with n nodes (“size n”) might be described as a planted plane tree together with a bijection from the nodes to the set {1, …, n} which is monotonically increasing when going from the root to the leaves.

[figure: 1; 2; 3; 4; 1; 1; 1; 1; 1; 2; 3; 3; 4; 4; 4; 2; 4; 2; 3; 3; 4; 2; 3; 2]

[figure: 1; 1; 1; 2; 4; 3; 1; 1; 2; 3; 3; 2; 4; 4; 1; 3; 2; 4; 1; 1; 2; 2; 3; 4; 4; 3; 2; 4; 3; 1; 2; 3; 4; 2; 3; 4]

Figure 1. All 15 heap ordered trees with 4 nodes

In this note, we want to concentrate on the level of the node j in a (random) heap ordered tree of size n ≥ j. This extends some of the results in [9] and [2] where the average over j (the depth of a random node) was considered. It will turn out, that surprisingly, this distribution does not depend on n. Precise expressions are derived for the expectation, the variance, and the probability distribution. A general reference for heap ordered trees and, more generally, increasing trees is [1].

The enumeration of the numbers a_{n} of heap ordered trees of size n is easy and appears already in [10]. The recursion is

a_{n+1} = ∑_{m≥1} ∑_{h_{1}+···+h_{m}=n} \binom{n}{h_{1}, …, h_{m}} a_{h_{1}} … a_{h_{m}} for n ≥ 1, a_{1} = 1 ;  (1)

Date: May 7, 1996.

hence the exponential generating function A(z) := ∑_{n≥0} a_{n} \frac{z^{n}}{n!} fulfills the differential equation

A′(z) = \frac{1}{1 − A(z)} with A(0) = 0 ,

with the solution

A(z) = 1 − \sqrt{1 − 2z} ,

so that

a_{n} = n! 2^{1−n} C_{n} = 1 · 3 · 5 … (2n − 3) ,

with a (shifted) Catalan number C_{n} = \frac{1}{n} \binom{2n−2}{n−1}.

Now let us consider the average level of node j in a heap ordered tree of size n. For that purpose we need a different recursion than (1). We want to fix the subtree which contains j and say that it is the first subtree. However, j can be in any of the m subtrees. So we introduce a factor m. (Of course, we assume j ≥ 2.) But then, we cannot choose h_{1} numbers out of {2, …, n + 1}, since we know already that j is there!

Therefore our alternative recursion is

a_{n+1} = ∑_{m≥1} ∑_{h_{1}+···+h_{m}=n} m \binom{n − 1}{h_{1} − 1, h_{2}, …, h_{m}} a_{h_{1}} … a_{h_{m}} for n ≥ 1, a_{1} = 1 . (2)

Let us test via generating functions that this is indeed correct. We multiply (2) by \frac{z^{n−1}}{(n−1)!} and sum up. The right hand side becomes

\frac{d}{du} \frac{u A′(z)}{1 − u A(z)}|_{u=1} = \frac{1}{(1 − 2z)^{3/2}} .

The left hand side is A′′(z), which equals the same quantity.

Now we want the probability that j lies in a subtree of size k. This is

∑_{m≥1} ∑_{h_{2}+···+h_{m}=n−k} m \binom{n − 1}{k − 1} \binom{n − k}{h_{2}, …, h_{m}} \frac{a_{k}a_{h_{2}} … a_{h_{m}}}{a_{n+1}}

We compute the factor of \binom{n−1}{k−1} \frac{a_{k}}{a_{n+1}} in this expression by multiplying this factor by \frac{z^{n−k}}{(n−k)!} and summing up. The result is amazingly simple:

\frac{d}{du} \frac{u}{1 − u A(z)}|_{u=1} = \frac{1}{1 − 2z} ,

whence our sought probability that j lies in a subtree of size k turns out to be

\binom{n − 1}{k − 1} \frac{a_{k}}{a_{n+1}} 2^{n−k} (n − k)! .

Again, it is an easy check that the sum on k of this quantity is 1.

Now, let D_{n,j} be the average level of node j. To avoid misinterpretations, we say that the root (= the node ‘1’) is on level 0. Using the last probability, we can set up a recursion for D_{n,j}. However, we must take care of the fact that in its subtree, ‘j’ does not mean ‘j’ any further. The numbers in the subtree are to be replaced by 1, 2, …, according to their relative order. Let us compute the probability that j will be i after this procedure, or, what is the same, that j is the ith largest number in its subtree. It is

\begin{matrix}\binom{j−2}{i−1} & \binom{n+1−j}{k−i} \\ ( & {n−1 \atop k−1} & ) \end{matrix} ,

since i − 1 numbers have to be chosen from {2, 3, …, j − 1} and k − i numbers from {j + 1, …, n + 1}.

Therefore we finally found our recursion:

D_{n+1,j} = 1 + ∑_{k=1}^{n} \binom{n − 1}{k − 1} \frac{a_{k}}{a_{n+1}} 2^{n−k} (n − k)! ∑_{i=1}^{k} \begin{matrix}\binom{j−2}{i−1} & \binom{n+1−j}{k−i} \\ ( & {n−1 \atop k−1} & ) \end{matrix} D_{k,i} .  (3)

This recursion is valid for n + 1 ≥ j ≥ 2. Additionally, we have, since ‘1’ is always on level 0, that D_{n,1} = 0 for all n ≥ 1.

The solution of this recursion is found by inspection^{1} (!), and it transpires that

D_{n,j} = H_{2j−2} − \frac{1}{2}H_{j−1} , independently of n (n ≥ j) .

Since we have such a simple result, we should explain it and prove it. The independency on n means that the nodes larger than j don’t change anything. We might say that a random tree of n nodes (each heap ordered tree is equally likely) remains ‘random’ if we cut off the nodes larger than j. This is in fact not too hard to see. First, it is enough to show that randomness is preserved if we erase node n. Or, since

\frac{a_{n+1}}{a_{n}} = 2n − 1 ,

we might alternatively show that from each tree with n nodes, we get 2n − 1 new trees by inserting the new node n + 1. We can attach this new node on every node, but the relative order in the plane is important, so if a certain node has i outgoing branches, it gives us i + 1 possibilities, namely to the left of all, between first and second edge, etc. Denoting by d(k) the number of outgoing branches, we have altogether

∑_{k=1}^{n} (1 + d(k)) = n + number of edges = 2n − 1 ,

as desired.

[figure: 1; 2; 3; 1; 1; 1; 1; 1; 2; 2; 2; 2; 2; 3; 3; 3; 3; 3; 4; 4; 4; 4; 4]

Figure 2. A heap ordered tree with 3 nodes and the 5 trees obtained by inserting a fourth node

1We used Maple to ‘see’ it.

To solve the recursion, we set n = j −1 and write D_{j} = D_{j,j} for simplicity. Then (3) turns into

D_{j} = 1 + ∑_{k=1}^{j−1} \frac{a_{k}}{a_{j}} 2^{j−1−k} (j − 1 − k)! \binom{j − 2}{k − 1} D_{k} .  (4)

With

E_{j} := \frac{a_{j}D_{j}}{2^{j}(j − 1)!} ,

we get

2(j − 1)E_{j} = \frac{2^{1−j}a_{j}}{(j − 2)!} + ∑_{k=1}^{j−1} E_{k} ,

or, by taking differences of two consecutive equations,

2jE_{j+1} = (2j − 1)E_{j} + \frac{a_{j}}{2^{j}(j − 1)!} ,

which means that

D_{j+1} = D_{j} + \frac{1}{2j − 1} .

Unrolling this recursion, we get

D_{j} = 1 + \frac{1}{3} + ⋯ + \frac{1}{2j−3} = H_{2j−2} − \frac{1}{2}H_{j−1} ,

and that was to be demonstrated.

We can get an easy corollary: Since

∑_{j=1}^{n} ∑_{i=1}^{j−1} \frac{1}{2i − 1} = ∑_{i=1}^{n} \frac{n − i}{2i − 1} = ∑_{i=1}^{n} \frac{(n − \frac{1}{2}) − (i − \frac{1}{2})}{2i − 1} = (n − \frac{1}{2}) (H_{2n} − \frac{1}{2}H_{n}) − \frac{n}{2} ,

we get, by dividing this by n, the average depth d_{n} of a random node

d_{n} = (1 − \frac{1}{2n}) (H_{2n} − \frac{1}{2}H_{n}) − \frac{1}{2} ,

a result from [9] and [2].

Now we want to compute the variance. Very much in the style of (3) we can set up a recursion for the probability generating functions F_{n,j}(x);

F_{n+1,j}(x) = x ∑_{k=1}^{n} \binom{n − 1}{k − 1} \frac{a_{k}}{a_{n+1}} 2^{n−k} (n − k)! ∑_{i=1}^{k} \begin{matrix}\binom{j−2}{i−1} & \binom{n+1−j}{k−i} \\ ( & {n−1 \atop k−1} & ) \end{matrix} F_{k,i}(x) .

As before, we freely drop the index n, by replacing n by j − 1.

F_{j}(x) = x ∑_{k=1}^{j−1} \frac{a_{k}}{a_{j}} 2^{j−1−k} (j − 1 − k)! \binom{j − 2}{k − 1} F_{k}(x) .  (5)

With the short hand notation

E_{j} = \frac{a_{j}F_{j}(x)}{2^{j}(j − 1)!} ,

we find

2(j − 1)E_{j+1} = x ∑_{k=1}^{j−1} E_{j} ,

whence

2jE_{j+1} − 2(j − 1)E_{j} = xE_{j} ,

or

E_{j} = \frac{2j − 4 + x}{2j − 2}E_{j−1} = \frac{1}{2^{j−1}(j − 1)!} ∏_{i=1}^{j−1} (2i − 2 + x) .

Therefore

F_{j}(x) = ∏_{i=1}^{j−1} \frac{2i − 2 + x}{2i − 1} .  (6)

When we have the probability generating function in a factored form where each factor constitutes a probability generating function itself, it is particularly easy to get the variance, see [5].

V_{j} := Var \{F_{j}(x)\} = ∑_{i=1}^{j−1} Var \{\frac{2i − 2 + x}{2i − 1}\} = ∑_{i=1}^{j−1} [\frac{1}{2i − 1} − \frac{1}{(2i − 1)^{2}} ] .

The reader might have noticed that in this paper a modified notion of harmonic numbers (of first and second order) would be more appropriate. If we define

Ĥ_{n} = ∑_{k=1}^{n} \frac{1}{2k − 1}  and  Ĥ_{n}^{(2)} = ∑_{k=1}^{n} \frac{1}{(2k − 1)^{2}} ,

then we have

V_{j} = Ĥ_{j−1} − Ĥ_{j−1}^{(2)} ;

in terms of harmonic numbers this equals

V_{j} = H_{2j−2} − \frac{1}{2}H_{j−1} − H_{2j−2}^{(2)} + \frac{1}{4}H_{j−1}^{(2)} .

From (6) it is even possible to get an explicit expression for the coefficient of x^{k}, which is the probability that node j is at level k. We write

F_{j}(x) = \frac{x(x + 2) … (x + 2(j − 1))}{a_{j}} = \frac{(−2)^{j−1}}{a_{j}} (−\frac{x}{2})\underline{j−1} = \frac{2^{j−1}}{a_{j}} ∑_{k=0}^{j−1} \left[{j − 1 \atop k}\right] \frac{x^{k}}{2^{k}} ,

and therefore

[x^{k}]F_{j}(x) = \frac{2^{j−1}}{a_{j}} \left[{j − 1 \atop k}\right] \frac{1}{2^{k}} .

Here, we used the notion of Stirling’s cycle numbers \left[{n \atop k}\right], compare [3].

For the readers convenience we collect our main findings as follows.

Theorem 1. The average and the variance of the level (depth) of the node with label j in a heap ordered tree of at least j nodes is given by

D_{j} = Ĥ_{j−1} ,
V_{j} = Ĥ_{j−1} − Ĥ_{j−1}^{(2)} .

The probability that node j has level k is given by

\frac{2^{j−1−k}}{a_{j}} \left[{j − 1 \atop k}\right] .

2. Binary trees

For the sake of completeness and comparison we briefly sketch the corresponding considerations for the instance of binary trees. However, mutatis mutandis, these are well known and old results, going back to Lynch, Hibbard, Knuth and others, see [4, 7, 6, 8].

The recursion for the increasing binary trees is

a_{n+1} = ∑_{k=0}^{n} \binom{n}{k}a_{k}a_{n−k}

with the obvious solution a_{n} = n!. The probability that j lies in a subtree of size k is

2\binom{n − 1}{k − 1}\frac{k!(n − k)!}{(n + 1)!} = \frac{2k}{n(n + 1)} .

The recursion for the probability generating functions is

F_{n+1,j}(x) = x ∑_{k=1}^{n} \frac{2k}{n(n + 1)} ∑_{i=1}^{k} \begin{matrix}\binom{j−2}{i−1} & \binom{n+1−j}{k−i} \\ ( & {n−1 \atop k−1} & ) \end{matrix}F_{k,i}(x) ,

and the specialization to n = j − 1 is

F_{j}(x) = \frac{2x}{j(j − 1)} ∑_{k=1}^{j−1} k F_{k}(x) ,

from which we derive

(j + 1)F_{j+1}(x) = (j − 1 + 2x)F_{j}(x)

and thus

F_{j}(x) = ∏_{i=2}^{j} \frac{i + 2(x − 1)}{i} .

Therefore the expectation is

D_{j} = ∑_{i=2}^{j} \frac{2}{i} = 2(H_{j} − 1) ,

and the variance is

V_{j} = ∑_{i=2}^{j} (\frac{2}{i} − \frac{4}{i^{2}} ) = 2H_{j} − 4H_{j}^{(2)} + 2 .

Furthermore, the probability generating function F_{j}(x) can be written as

F_{j}(x) = \frac{1}{j!}(−1)^{j−1}(−2x)\underline{j−1} = \frac{1}{j!} ∑_{k=0}^{j−1} \left[{j − 1 \atop k}\right] (2x)^{k} ,

whence we find for the probability that the node j lies on level k the quantity

\frac{2^{k}}{j!} \left[{j − 1 \atop k}\right] .

References

[1] F. Bergeron, P. Flajolet, and B. Salvy. Varieties of increasing trees. Lecture Notes in Computer Science, 581:24–48, 1992.

[2] W.-C. Chen and W.-C. Ni. On the average altitude of heap–ordered trees. International Journal of Foundations of Computer Science, 15:99–109, 1994.

[3] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison Wesley, 1989.

[4] T. N. Hibbard. Some combinatorial properties of certain trees with applications to searching and sorting. Journal of the ACM, 9(1):13–28, January 1962.

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

[6] D. E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 1973.

[7] W. C. Lynch. More combinatorial problems on certain trees. Computer Journal, 7:299–302, 1965.

[8] H. M. Mahmoud. Evolution of Random Search Trees. John Wiley, New York, 1992.

[9] H. Prodinger. Depth and path length of heap ordered trees. International Journal of Foundations of Computer Science, 1996 (to appear).

[10] H. Prodinger and F.J. Urbanek. On monotone functions of tree structures. Discrete Applied Mathematics, 5:223–239, 1983.

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

  E-mail address: Helmut.Prodinger@tuwien.ac.at
  WWW-address: http://info.tuwien.ac.at/theoinf/proding.htm