Tight Upper and Lower Bounds on the Path Length of Binary Trees.
The external path length of a tree $T$ is the sum of the lengths of the paths from the root to each external node. The maximal path length difference, $\Delta$, is the difference between the lengths of the longest and shortest such paths.  Tight lower and upper bounds are proved on the external path length  of binary trees with $N$ external nodes and  maximal path  length difference $\Delta$ is prescribed.   In particular, an upper bound is given that, for each value of  $\Delta$, can be exactly achieved for infinitely many values of $N$.  This improves on the previously known upper bound that could  only be achieved up to a factor proportional to $N$. An elementary proof of the known upper bound is also presented as  a preliminary result.  Moreover, a lower bound is proved that can be exactly achieved for each value of $N$ and $\Delta\leq N/2$.
Introduction
. Binary trees constitute the most important and widely used
data structure for the storage and retrieval of information. The cost of accessing information
stored in a node is proportional to the distance of the node from the root.
An important measure of efficiency, often considered with respect to a binary tree T , is
its external path length External(T ), that is the sum of the distances of the external
nodes from the root as this is related to the average cost of an unsuccessful search in the
tree T . Moreover, the external path length of T is related to the internal path length
that is the sum of the distances of the internal nodes from the root and
corresponds to the average cost of a successful search in the tree T .
It is well known that the external path length of a binary tree with N external
nodes is \Theta(N lg N) in the best case while in the worst case can be as bad as \Theta(N 2 ).
The large gap between the best and the worst case motivates the study of this important
quantity when some additional information about the tree is available. Nievergelt and
Wong [7] proposed an upper bound for the external path length of a tree T in term
of the number of external nodes and the maximum weight balance of all its subtrees.
More recently, Klein and Wood [5] obtained an upper bound that requires much less
information about the tree. Namely, they derived an upper bound on the external path
length of a T in terms of N , the number of external nodes, and \Delta, the maximum of the
differences of the lengths of the paths from the root to each external node. In the case
Dipartimento di Informatica ed Applicazioni, Universit'a di Salerno, 84081 Baronissi (Salerno),
Italy. Part of this work was done while the author was visiting IBM Research Division, T. J. Watson
Research Ctr, Yorktown Heights, NY 10598.
y Aiken Computation Laboratory, Harvard University, Cambridge, MA 02138. Partially supported
by NSF Grant # NSF-CCR-90-07677. Part of this work was done while the author was visiting AT&T
Bell Laboratories, New Jersey (USA).
N , they also constructed trees whose external path length is within O(N) from
their upper bound.
In this paper we continue and extend the work of [5]. We present an upper bound
on the external path length of binary trees with N nodes and maximum path length
difference \Delta and construct an infinite class of trees whose external path length matches
our bound exactly. Moreover, we present a lower bound on the external path length of
these trees. For the case \Delta - N=2, there exist trees whose external path length matches
exactly our bound.
Organization of the Paper and Summary of the Results.
In this paper we study the path length of (N; \Delta)-trees, that are extended binary trees
with N external nodes and maximum path difference \Delta.
In Section 2 we set up our notation and recall some elementary facts about binary
trees.
In Section 3, we present our upper bounds. As a preliminary result, in Section 3.1 we
give a simple derivation of the upper bound presented in [5]. In Section 3.2 we improve
on this result by giving a better bound that, for each \Delta, can be exactly achieved for
infinitely many N .
In Section 4 we present our lower bound. We exactly compute, for each N and
the external path length of the tree with shortest external path length. Our
lower bound is the first lower bound to improve on the banal lower bound obtained by
considering the binary tree with external nodes on two consecutive levels, which has
the shortest external path length among the trees with the same number of external
nodes.
2. Background and Notation. In this section we set up our notation and recall
some elementary facts about binary trees.
We denote the set of the natural numbers by N , the set of the positive natural
numbers by N + , and the set of the positive real numbers by R + . The writing dxe
denotes the least integer greater than or equal to x. Throughout this paper, the writing
lg x denotes the logarithm to base 2 of x.
All the trees considered in this paper are extended binary trees. An extended binary
tree is obtained from a binary tree by adding special nodes, the external nodes, so that
every node in the binary tree has exactly two children. The originary nodes of the
binary tree are also called internal nodes.
We say that an external node e is at level l of a tree T if the length of the (unique)
path from the root to e is l. Let T have N external nodes at levels l
the external path length of T , External(T ), is defined as:
The internal path length of a tree Internal(T ) is defined as the sum of the levels of
the internal nodes.
PATH LENGTH OF BINARY TREES 3
The maximum path length difference of T , Fringe(T ), is defined as:
Also, a level l (other than the last one) is said to be dense if it has more than one
external node, while the last level is dense if it has more than two external nodes. An
(N; \Delta)-tree is a binary tree with N external nodes and maximum path length difference
\Delta.
For \Delta) as follows:
T is a (N; \Delta)-tree
and
T is a (N; \Delta)-tree
In this paper we give bounds on epl(N; \Delta) and EPL(N; \Delta). We restrict our attention
to the cases when there exists no
(N; \Delta)-tree and the cases can be completely characterized (see Section 4).
The following is a simple and well-known result about extended binary trees (see,
for example, [4]) that will be extensively used in the sequel.
Fact 2.1 (Kraft equality). Let l l N be a sequence of positive integers.
Then, there exists an extended binary tree with N external nodes at levels l
and only if
We shall say that a (N; \Delta)-tree T has configuration (L; a 0 ; a
1. a
2. T has a i external nodes at level L
3.
a
Two (N; \Delta)-trees with the same configuration are said isomorphic, as for our purposes
they are the "same" tree. In what follows, we will omit L from a configuration when it
is either clear from the context or immaterial.
3. Upper Bounds. In this section we present upper bounds on EPL(N; \Delta). The
problem of computing EPL(N; \Delta) can be stated as follows:
Find the maximum of
l i subject to
1. l i
2.
3.
Because of the constraints l i finding the exact maximum does not appear to
be an easy task.
3.1. A simple proof of a known upper bound. Recently, Klein and Wood [5]
have proved the following upper bound on EPL(N; \Delta).
Bound 1.
where
and e is the base of the natural logarithm.
In [5], the bound above is derived by first proving that the external path length is
related to the ratio of the geometric and the harmonic means of certain integers and
then by applying a theorem by Specht [8]. In this section, we re-derive Bound 1 using
only elementary calculus.
We obtain an upper bound on EPL(N; \Delta), by allowing the l i 's to range over the
real numbers.
To this end, for as the maximum of
l i
over the sequences l satisfying the following constraints
1. l i
2.
3. x - l i
A triplet (N; \Delta; x) for which there exists a sequence l
that satisfies the three
constraints above is called admissible.
It is clear that an upper bound on the external path length of binary trees is given
by
EPL(N; \Delta) - maxfM(N; \Delta; x)j(N; \Delta; x) is admissible and x
(1)
The following lemma gives a useful characterization of the maximum M(N; \Delta; x).
Lemma 3.1. Let (N; \Delta; x) be an admissible triplet. The maximum M(N; \Delta; x) is
achieved by a sequence l 1 all the l i 's, but at most one, are equal either
to x or x \Delta.
Proof. Assume, by way of contradiction, that the maximum is reached by l 0
such that x ! l 0
define the sequence l 00
N in the
following way
l 00
l 0
l 0
l 0
where ffi is chosen so that the Kraft equality holds; that is 2 \Gammal 00
Notice that for sufficiently small values of ffl (i.e.
PATH LENGTH OF BINARY TREES 5
00are both in [x; x \Delta]. Since the function
increasing in x and is equal to 0 for positive
holds. Therefore, if ffl
xg, the
sequence l 00
N satifies the three constraints in the definition of M(N; \Delta; x) and
contradicting the maximality of l 0
N .
The following lemma provides an upper bound on the maximum M(N; \Delta; x).
Lemma 3.2. Let (N; \Delta; x) be an admissible triplet. Then,
Proof. By Lemma 3.1, the maximum is achieved when l
l \Delta. By the
Kraft equality, we get
from which we see that m is uniquely specified by N , \Delta, y, and x. The maximum
M(N; \Delta; x) is thus given by
\Gammay
The function function of y with
and f \Delta. Hence the lemma.
We are now ready to prove Bound 1.
Theorem 3.3.
where
and e is the base of the natural logarithm.
Proof. Combining Lemma 3.2 and (1) we get
ae
oe
(2)
The function to maximize is a concave function of x. It can be easily seen, using
elementary calculus, that it reaches its maximum (for fixed values of N and \Delta) at
\Delta. Substituting this into (2) we get Bound 1.
6 DE SANTIS AND PERSIANO
3.2. An improved upper bound achievable by infinitely many values.
In the previous section all maximizations were carried over the real numbers. Now, we
show that by restricting x to be an integer we get a better bound. The bound presented
in this section improves on Bound 1 on two accounts: first, it is more accurate; second,
for each value of \Delta, it can be exactly achieved for infinitely many values of N .
Bound 2. Let
Moreover, for each \Delta there exists an infinite subset N \Delta
' N such that for each N 2 N \Delta
there exists a (N; \Delta)-tree T (N;\Delta)
with
Proof. From the analysis done in Section 3.1, it is clear that an upper bound on
the external path length of binary trees is given by
From Lemma 3.2 we get
where
be an integer at which \Phi N;\Delta
(x) is maximum; i.e.
As \Phi N;\Delta
(x) is a concave function of x, any integer x such that
satisfies (3). From the definition of \Phi
(x), we obtain that any x such that
satisfies (3). However, is not an integer power of 2: if it were equal to 2 z ,
for some z would be a factor of \Delta2 z\Gamma\Delta , thus of \Delta, which is impossible.
Hence, the above inequalities uniquely determine x as proving
the bound.
PATH LENGTH OF BINARY TREES 7
Now, we prove that the bound is achievable. Let \Delta and x be positive integers such
that
h \Delta;x
The function h \Delta;x
enjoys the following three properties.
(a) h \Delta;x
x. Indeed, this inequality is equivalent to 2 x ?
that is satisfied for x - \Delta.
(b) h \Delta;x
x. Indeed, this can be written as
that is satisfied for x - \Delta - 2.
(c) h \Delta;x
simple algebra shows
that it is equivalent to y which holds for y - 1.
Because of the above three properties, for each \Delta - 2 and x - \Delta, there exists some
1g such that h \Delta;x
(y \Delta;x
(y \Delta;x
1. (Actually, there can
be several such y \Delta;x
's; for instance, if
For each \Delta - 2, consider the infinite set N \Delta
1)y \Delta;L
g. Fix \Delta and N 2 N \Delta
, and consider the
external
nodes at level L and y \Delta;L
2 \Delta at level L+ \Delta, where L is such that
First of all, such a tree exists. In fact, as y \Delta;L
the Kraft equality is satisfied. From the definition of y \Delta;L
we obtain
h \Delta;L
(y \Delta;L
(y \Delta;L
and by the definition of the function h \Delta;L
lg
from which
l
lg
jm
follows.
We now compute External(T ) which turns out to be exactly as in Bound 2. In
fact, one has that
\Delta2 \Delta
It is clear that Bound 2 is more accurate than Bound 1. In fact, for every
and N - \Delta, (1) is the absolute maximum of the function \Phi
while (2) is the maximum of the same function subject to the additional
constraint x
Example 1. As an example, consider the case 5. There are binary trees which
satisfy Bound 2 with equality for
and so on for all larger L.
Example 2. By plugging Bound 2, we obtain that
Actually, it can be proved that the above bound is tight for all values of N (see [2, 3]).
Example 3. As a simple application of the Bound 2, we derive an upper bound on
the internal path length of red-black trees. The class of red-black trees constitute an
important class of balanced binary trees that guarantee a worst-case search cost of
1). The bound we obtain is, up to terms of lower order, equal to the one
presented in [1] that was proved to be asymptotically tight.
The bound is obtained by observing that a red-black tree has Fringe - log(N +1)
and that Bound 2 is increasing in \Delta.
Bound 3. Let T be a red-black tree with N internal nodes. Then
We refer the reader to [3] for a proof of the above bound.
4. Lower Bound. In this section we present a lower bound that can be exactly
achieved for N - 4 and 2 - \Delta - N=2.
Before dealing with the general case, let us briefly discuss the cases
(see [6] for a more complete treatment). The case easily settled: a
exists if and only if N is a power of 2, in which case the N external nodes
are located at level lg N and the tree is unique. On the other hand, a (N; 1)-tree exists
if and only if N is not a power of 2, in which case it is unique. The external nodes of
the unique (N; 1)-tree are located at levels dlg Ne \Gamma 1 and dlg Ne and its external path
length is N(dlg Ne The following property of (N; 1)-trees can be easily
proved using the Kraft equality.
Lemma 4.1. If the (N; 1)-tree exists and has c ? 0 external nodes at level dlg Ne
c is a power of 2 and, due to c ! N , none of the integers in [N; N
a power of 2.
Let us now consider the case \Delta - N=2 and N - 4. We start by characterizing the
(N; \Delta)-trees with minimum external path length. As we will prove in Theorem 4.5, such
trees belong to a class of (N; \Delta)-trees with a particular structure. Then we compute
the external path length of the trees with such a structure and obtain a lower bound
by minimizing the so obtained external path lengths.
Lemma 4.2. Let T be a (N; \Delta)-tree with minimum external path length and
configuration (L; a
1. T has at most two dense levels. Moreover, if T has two dense levels, then these
two levels are consecutive.
2. If level
PATH LENGTH OF BINARY TREES 9
Proof. We only prove 1, as the proof of 2 is similar. Assume, by way of contradiction,
that T is a tree with two non-consecutive dense levels and minimum external path
length. That is, a case in which one of the two
dense levels is the last one is similar). Now, consider the tree T 0 with configuration
(L; a 0
a 0
a
T 0 is still a (N; \Delta)-tree and has external path length
Thus T cannot have minimum external path length.
Now, it is immediate that there cannot be more than two intermediate levels with
more than one external node even if they are consecutive. In fact, suppose that three
levels have more than one external node. Then, obviously, at least two of them must
be non-consecutive.
Before going any further, let us introduce the following notation. An (N; \Delta)-tree
of type
) has an unspecified, but greater than or equal to b 0 , external
nodes at level L; more, precisely it has configuration (L; a 0 ; a
We shall say that a (N; \Delta)-tree has type (L; a b 0
it has a 0 external nodes
on each of the first b 0 levels, a 1 external nodes on each of the following b 1 levels and so
on; that is, it has configuration
(L; a
times
The symbols - a b and - a b denote respectively b levels each of which has no more than
a external nodes and no less of a external nodes. As done with the configuration, we
will omit L and just say that a tree is of type (a b 0
from the context or immaterial.
Lemma 4.3. Let T be a tree of type (L; - 0 a
contains an external node then all levels L
exactly one external node each; that is T is of type (L; - 0 a
Proof. Consider the grandparent e of the two external nodes at level L
This node has two children, one of which is the internal node which is the parent of the
two external nodes at level L b. Now, the other child of e cannot be an internal
node as this would imply either that level L has more than 2 external nodes
or that some successive level has some external nodes. Thus, level L
exactly one external node. We can prove by induction that this is the case also for
proving the lemma.
We are now ready to completely characterize the configuration of (N; \Delta)-trees with
minimum external path length. In fact, in Theorem 4.5 we will prove that such a tree
must be a (N; \Delta; a)-tree defined as follows.
Definition 4.4. For N - 4,
we define a (N; \Delta; a)-tree in the following way.
1. A (N; \Delta; \Gamma1)-tree is a (N; \Delta)-tree of type (-
2. Let 0 - a - 2g. A (N; \Delta; a)-tree is a (N; \Delta)-tree of type
3. If
Remark. Notice that in the above definition we have not considered the case a ?
log In fact, a tree of type (L; contains at least 2
external nodes. But L - 1 and thus 2 a+1 - N from which a - lg N \Gamma 1.
Also notice that using the Kraft equality it is easy to see that the (N; \Delta; a)-tree, if
it exists, is unique. See also the discussion following Lemma 4.6.
Theorem 4.5. For N - 4, is a (N; \Delta)-tree with minimum
external path length then T is a (N; \Delta; a)-tree for some a, \Gamma1 - a -
1g.
Proof. In view of Lemma 4.2, a (N; \Delta)-tree with minimum external path length
has at most two dense levels and the levels preceeding the dense levels (except for the
very first one) are all empty.
We consider first the case in which the are two dense levels. If the dense levels are
the first two levels, then, because of Lemma 4.3, the tree is of type (- 2; - 2; 1 \Delta\Gamma2 ; 2) and
thus is a (N; \Delta; \Gamma1)-tree. Instead, if the last two levels are dense, then the tree is of type
is thus a (N; \Delta; Finally, if the two dense levels are
intermediate then, because of Lemma 4.3, the tree is of type (1; 0 a
for some a, and thus is a (N; \Delta; a)-tree.
Consider now the case in which there exists only one single dense level. Then,
if this level is the first, the tree is a (N; \Delta; \Gamma1)-tree; if it is the last level then the
tree is a (N; \Delta; otherwise the tree is a (N; \Delta; a)-tree for some 0 - a -
2g.
Lemma 4.6.
a) For 0 - a - the (X; 1)-tree U with configuration (L; a 0 ; a 1 ), where
a exists if and only if there exists an
T with configuration (L
b) The (X; 1)-tree U with configuration (L; a 0 ; a 1 ) exists if and only if there exists
an configuration (L; a 0 ; a
c) The (X; 1)-tree U with configuration (L; a exists if and
only if there exists an
Proof. We prove only part a) of the lemma, the proofs of parts b) and c) being very
similar.
For brevity, we denote the configuration of T by (L
PATH LENGTH OF BINARY TREES 11
b. First, all the c i are nonnegative integers if and only if a 0 - 2 a+1 .
Moreover,
a 0
a 1
\Gamma2 L+1
a 0
a 1
By using the Kraft equality, the existence of one of the two trees implies that both sums
are equal to 1 and thus both trees exist.
The above lemma implies that, for fixed N , \Delta, and a, there exists a unique
\Delta; a)-tree. In fact, for each a, Lemma 4.6 naturally defines an invertible mapping
on trees with trees with greater \Delta. Therefore, if for some N , \Delta, and a there
are two (non-isomorphic) (N; \Delta; a)-trees then, by inverting the mapping we would construct
two (non-isomorphic) trees with and the same number of external nodes
which is not possible.
The next lemma gives necessary and sufficient conditions for the existence of the
(N; \Delta; a)-tree and computes its external path length. To this aim, we define the function
F (a; N; \Delta) as follows:
dlg X(a; N; \Delta)e+1
\Gamma2 dlg X(a;N;\Delta)e +2 a+2
where
Lemma 4.7. For N - 4,
the (N; \Delta; a)-tree exists if and only if the interval [X(a; N; \Delta); X(a;
does not contain any power of 2, in which case its external path length is F (a; N; \Delta).
Proof. We will prove the lemma for 0 - a - 1g. The cases
can be proved in a similar way.
Suppose that the interval [X(a; N; \Delta); X(a; does not contain any
power of 2. Then, by Lemma 4.1 and since
unique (X(a; N; \Delta); 1)-tree has at least 2 a+1 external nodes on its first level. Therefore,
the hypothesis of part a) of Lemma 4.6 hold and, thus, the (N; \Delta; a)-tree exists. The
other implication is proved in a similar way.
To compute the external path length of the (N; \Delta; a)-tree we use Lemma 4.6. The
configuration of the (N; \Delta; a)-tree, and thus its external path length, is completely
determined by the configuration of the corresponding (X; 1)-tree. It can be expressed
as a function of L; a 0 , and a 1 which, in turn, depend only on the value X. We can thus
compute the external path length of the (N; \Delta; a)-tree, that a tedious computation
shows to be exactly F (a; N; \Delta).
We next study the behavior of the external path length of the (N; \Delta; a)-tree, for
fixed N and \Delta. We will see that the external path length of the (N; \Delta; a)-tree is a
bitonic function of a; that is, it is non-increasing up to a certain value ff(\Delta) of a and
then it is non-decreasing. ff(\Delta) is the integer part of the unique solution to the equation
It is easily seen that ff(\Delta) is equal to either blg \Deltac \Gamma 2 or blg \Deltac \Gamma 1.
Lemma 4.8. Let N - 4, 1g. If
the (N; \Delta; a \Gamma 1)-tree exists then
F (a; N; \Delta)
Proof. The difference F (a \Gamma \Delta) is equal to
By hypothesis the (N; \Delta; a \Gamma 1)-tree exists. Therefore, by Lemma 4.7, the interval
does not contain any power of 2.
\Delta) +2 a is a power of 2 then dlg
a ) and
(from the definition of X(a \Gamma
Therefore,
and the lemma is proved.
Let us consider now the case when X(a a is not a power of 2. In this
case we have
(as the interval [X(a \Gamma
does not contain any power of 2.)
Therefore,
Now, if a - ff(\Delta) then a \Delta). On the other
hand, if a ? ff(\Delta) then a \Delta).
PATH LENGTH OF BINARY TREES 13
Lemma 4.9. Let N - 4, 1g. If the
(N; \Delta; a \Gamma 1)-tree does not exist and the (N; \Delta; a)-tree and the (N; \Delta; a \Gamma 2)-tree exist,
then
F (a; N; \Delta)
Proof. The proof of this lemma is very similar to the one of the previous lemma
and is omitted. We refer the reader to [3] for a complete proof.
Lemma 4.10. Let N - 4, \Delta - N=2, and ff(\Delta). If the (N; \Delta; ff)-tree does not
exist, then both the (N; \Delta; ff \Gamma 1)-tree and the (N; \Delta; ff exist.
Proof. As the (N; \Delta; ff)-tree does not exists, then, by Lemma 4.7, the interval
contains a power of 2 and the previous power of 2 is in the interval
The interval
does not contain any power of 2, and thus the (N; \Delta; ff \Gamma 1)-tree exists, since X(ff \Gamma
The first inequality follows from the definition of X(a; N; \Delta), while the second is equivalent
to the above inequality holds,
thus proving that the (N; \Delta; ff \Gamma 1)-tree exists.
The existence of the (N; \Delta; ff + 1)-tree is established in a similar way.
We can summarize the above lemmata by saying that if the (N; \Delta; ff)-tree exists,
that is, if the interval [X(ff; N; \Delta); X(ff; does not contain any power
of 2, then When the (N; \Delta; ff)-tree does not exist, then,
by Lemma 4.10, both the (N; \Delta; ff \Gamma 1)-tree and the (N; \Delta; ff exist and the
minimum path length is obtained by either one.
We have thus proved the following
Bound 4. For all N - 4 and \Delta - N=2,
does not contain any power of 2;
14 DE SANTIS AND PERSIANO
where ff is the integer part of the (unique) solution of the equation x
and
dlg X(a; N; \Delta)e+1
\Gamma2 dlg X(a;N;\Delta)e +2 a+2

Acknowledgements

. The second author would like to thank Prof. Harry Lewis
for his suggestions. We also thank Marios Mavronicolas for a careful reading of the
manuscript.



--R

The Internal Path Length of Red-Black Trees
"STACS 91"
Tight Upper and Lower Bounds on the Path Length of Binary Trees
Coding and Information Theory
On the Path Length of Binary Trees
The Art of Computer Programming
Upper Bounds for the Total Path Length of Binary Trees
Zur Theorie der Elementaren Mittel
--TR
binary search trees;path length