Trees. An Introduction to the Analysis of Algorithms by Robert Sedgewick and Phillipe Flajolet. (2024)

This chapter investigates properties of many different types oftrees, fundamental structures that arise implicitly and explicitlyin many practical algorithms. Our goal is to provide access to resultsfrom an extensive literature on the combinatorial analysis of trees,while at the same time providing the groundwork for a host ofalgorithmic applications.

6.1 Binary Trees

Definition.A binary treeis either an external node or aninternal node attached to an ordered pair of binary trees called theleft subtree and the right subtree of that node.

Theorem.(Enumeration of binary trees)The number of binary trees with $N$internal nodes and $N+1$ external nodes isgiven by the Catalan numbers:$$T_{N}={1\over N+1}{2N\choose N}= {4^N\over\sqrt{\pi N^3}}\Bigl(1+O({1\over N})\Bigr).$$Proof.

6.2 Forests and Trees

In a binary tree, no node has more than two children. Thischaracteristic makes it obvious how to represent and manipulate suchtrees in computer implementations, and it relates naturally to“divide-and-conquer” algorithms that divide a problem into twosubproblems. However, in many applications (and in more traditionalmathematical usage), we need to consider general trees:

Definition.A tree (also called a general tree)is a node (called the root) connected to a sequence of disjoint trees.Such a sequence is called a forest.

We use the same nomenclatureas for binary trees: the subtrees of a node are its children, a rootnode has no parents, and so forth. Trees are more appropriate modelsthan binary trees for certain computations.

Theorem.(Enumeration of general trees)Let $G_N$ be the number of general trees with $N$ nodes.Then $G_N$ is exactlyequal to the number of binary trees with $N-1$ internal nodes and isgiven by the Catalan numbers: $$G_N=T_{N-1}={1\over N}{2N-2\choose N-1}.$$Proof. (via the symbolic method)A forest is either empty or a sequence of trees:$$\cal F = \epsilon + \cal G + (\cal G\times\cal G) + (\cal G\times\cal G\times\cal G) + (\cal G\times\cal G\times\cal G\times\cal G) + \ldots$$which translates directly to$$F(z) = 1 + G(z) + G(z)^2 + G(z)^3 + G(z)^4 + \ldots = {1\over 1-G(z)}.$$The obvious one-to-one correspondence between forests and trees(cut off the root) means that $zF(z) = G(z)$, so$$G(z)={z\over 1-G(z)}.$$Thus $G(z)-G(z)^2=z$ and therefore $G(z)=zT(z)$, since both functionssatisfy the same functional equation. That is, the number of trees with$N$ nodes is equal to the number of binary trees with $N$ external nodes.

6.3 Combinatorial Equivalences to Trees and Binary Trees

The following combinatorial objects are all in 1-1 correspondence and are therefore counted by the Catalan numbers.

• Binary trees with $N$ external nodes.
• Trees with $N$ nodes.
• Legal sequences of $N$ pairs of parentheses.
• Triangulated $N$-gons.
• Gambler's ruin sequences.

Here are examples of these objects for small $N$:

6.4 Properties of Trees

Definition.In a tree $t$:

• the size $|t|$ is its number of nodes
• the level of a node is its distance from the root (which is at level 0)
• the path length $\pi(t)$ is the sum of thelevels of each of the nodes in $t$
• the height $\eta(t)$ is themaximum level among all the nodes
• the leaves are the nodes with no children

Definition.In a binary tree $t$:

• the size $|t|$ is its number of internal nodes
• the level of a node is its distance from the root (which is at level 0)
• the internal path length $\pi(t)$ is the sum of thelevels of each of the internal nodes in $t$
• the external path length $\xi(t)$ is the sum of thelevels of each of the external nodes in $t$
• the height $\eta(t)$ is themaximum level among all the external nodes
• the leaves are the (internal) nodes with both children external

Recursive definitions.It is often convenient to work with recursive definitions for treeparameters. In a binary tree $t$, the parameters we have defined areall $0$ if $t$ is an external node; otherwise if the root of $t$ isan internal node and the left and right subtrees, respectively, are denotedby $t_l$ and $t_r$, we have following recursive formulae:$$\eqalign{|t|&=|t_l|+|t_r|+1\cr\pi(t)&=\pi(t_l)+\pi(t_r)+|t|-1\cr\xi(t)&=\xi(t_l)+\xi(t_r)+|t|+1\cr\eta(t)&=1+\max(\eta(t_l), \eta(t_r)).\cr}$$These are easily seen to be equivalent to the definitions above.These forms serve as the basis for deriving functionalequations on associated generating functions when we analyze treeparameters. They also facilitate inductive proofs aboutrelationships among the parameters.

Example. Path lengths in any binary tree $t$ satisfy$\xi({t})=\pi({t})+2|t|$. Subtracting the equation$\pi(t)=\pi(t_l)+\pi(t_r)+|t|-1$from the equation$\xi(t)=\xi(t_l)+\xi(t_r)+|t|+1$immediately provides the basis for a proof by induction.

In the analysis of algorithms, we are particularly interested in knowingthe average values of these parameters, for various types of“random” trees. One of our primary topics of discussion for thischapter is how these quantities relate to fundamentalalgorithms and how we can determine their expected values.A random binary tree has larger values for bothpath length and height than a random forest. One of the prime objectivesof this chapter is to quantify these and similar observations, precisely.

6.5 Examples of Tree Algorithms

Trees are relevant to the study of analysis of algorithms not onlybecause they implicitly model the behavior of recursive programsbut also because they are involved explicitly in many basic algorithmsthat are widely used. For typical applications, we are interested in the pathlength and height of trees. To consider the average value ofsuch parameters, of course, we need to specify a model defining whatis meant by a random tree. For applications such as tree traversal and expression evaluation (or, more generally, recursive program execution,the model where trees are taken equally likely is worth considering. For these applications, we studyso-called Catalan models, where each of the$T_N$ binary trees of size $N$ or general trees of size $N+1$ are taken withequal probability. This is not the only possibility---in many situations,the trees are induced by external data, and other modelsof randomness are appropriate. Next, we consider a particularly importantexample.

6.6 Binary Search Trees

One of the most important applications of binary trees is thebinary tree search algorithm, a method that uses binary treesexplicitly to provide an efficient solution to a fundamental problemin computer science. For full details, see Section 3.2 in Algorithms, 4th edition.The analysis of binary treesearch illustrates the distinction between models where all trees areequally likely to occur and models where the underlying distributionis nonuniform. The juxtaposition of these two is one of the essentialconcepts of this chapter.

Definition. A binary search treeis a binary tree with keys associated with the internal nodes, satisfyingthe constraint that the key in every node is greater than or equal to allthe keys in its left subtree and less than or equal to all the keys inits right subtree.

We study binary search trees under the random permutationmodel, where we assume that each permutation of the keys in the tree(all distinct) is equally likely as input. This model has beenvalidated in many practical situations. Many different permutationsmay map to the same tree. It isnot true that each tree is equally likely to occur if keys areinserted in random order into an initially empty tree.

The cost of constructing a particular tree is directly proportional toits internal path length, since nodes are not moved once inserted, andthe level of a node is exactly the number of nodes required to insertit. Thus, the cost of constructing a tree is the same for each of thepermutations that could lead to its construction.

We could obtain the average construction costby adding, for all $N!$ permutations, the internal pathlength of the resulting tree (the cumulated cost) and then dividing by $N!$.The cumulated cost also could be computed by adding, for all trees,the product of the internal path length and the number of permutationsthat lead to the tree being constructed.This is the average internal path length that we expect after $N$random insertions into an initially empty tree, but it isnotthe same as the average internal path length of a random binary tree,under the Catalan model where all trees are equally likely. It requiresa separate analysis. We will consider the Catalan tree case in the nextsection and the binary search tree case in Section 6.8.Indeed, it is fortunately the case that the more balancedtree structures, for which search and construction costs are low, aremore likely to occur than tree structures for which the costs arehigh. In the analysis, we will quantify this.

6.7 Average Path Length in Catalan Trees

What is the average path length of a tree with $N$internal nodes, ifeach $N$-node tree is considered to be equally likely? Our analysis of thisimportant question is prototypical of the general approach to analyzingparameters of combinatorial structures that we introduced in Chapter 3:

• Define a bivariate generating function (BGF), with onevariable marking the size of the tree and the other marking theinternal path length.
• Derive a functional equation satisfied by the BGF, orits associated cumulative generating function (CGF).
• Extract coefficients to derive the result.

In a random binary Catalan tree with $N$ nodes,the probability that the left subtree has$k$ nodes (and the right subtree has $N-k-1$ nodes) is $T_{k}T_{N-k-1}/T_N$ (where $T_N={2N\choose N}\bigm / (N+1)$is the $N$th Catalan number).The denominator is the number of possible $N$-node trees and thenumerator counts the number of ways to make an $N$-node tree byusing any tree with $k$ nodes on the left and any tree with $N-k-1$nodes on the right. We refer to this probability distribution asthe Catalan distribution, illustrated in this figure.

One of the striking facts about the distribution is thatthe probability that one of the subtrees is empty tends toa constant as $N$ grows: it is $2T_{N-1}/T_N\sim 1/2$. Indeed, about halfthe nodes in a random binary tree are likely to have an empty subtree,so such trees are not particularly well balanced.Using the Catalan distribution, we can analyze path length in a manner similar to our Quicksort analysis.The average internalpath length in a random binary Catalan tree is describedby the recurrence$$Q_N=N-1+\sum_{1\le k\le N}{T_{k-1}T_{N-k}\over T_N}(Q_{k-1}+Q_{N-k}) \qquad\hbox{for $N>0$}$$with $Q_0=0$.The argument underlying this recurrence is general, and can be used toanalyze random binary tree structures under other models of randomness,by substituting other distributions for the Catalan distribution.For example, as discussed below, the analysisof binary search trees leads to the uniformdistribution (each subtree size occurs with probability $1/N$) and therecurrence matches the Quicksort recurrence. Continuing along the linesof the Quicksort analysis is possible but leads to intricate calculations, easily avoided with CGFs.

Theorem. (Path length in binary trees)The average internal path length in a random binary tree with $N$ internalnodes is$${(N+1)4^N\over{2N\choose N}}-3N-1 = N\sqrt{\pi N}-3N+O(\sqrt{N}).$$Proof.Define the CGF$$C_T(z) \equiv P_u(1,z) = \sum_{t\in \cal T}\pi(t)z^{|t|}.$$The average path length is $[z^n]C_T(z)/[z^n]T(z)$.The recursive definition of binary trees leads immediately to$$\eqalign{C_T(z) &= \sum_{t_l\in \cal T}\sum_{t_r\in\cal T}(\pi(t_l ) + \pi(t_r ) + |t_l | + | t_r|) z^{|t_l| + |t_r| + 1}\cr&= 2zC_T(z)T(z)+2z^2T(z)T^\prime(z),\cr}$$which yields the solution$$C_T(z) = {2z^2T(z)T^\prime(z)\over 1-2zT(z)}.$$Now, $T(z)=(1-\sqrt{1-4z})/(2z)$, so $1-2zT(z)=\sqrt{1-4z}$ and$zT^\prime(z)=-T(z)+1/\sqrt{1-4z}$. Substituting these gives theexplicit expression$$zC_T(z) = {z \over 1-4z} - {1 -z\over \sqrt {1-4z}} + 1,$$which expands to give the stated result.

This result is illustrated by the large random binary tree shown below:asymptotically, a large tree roughly fits into a $\sqrt{N}$-by-$\sqrt{N}$square.

Theorem. (Path length in general trees)The average path length in a random general tree with $N$ internalnodes is$${N\over 2}\biggl({4^{N-1}\over{2N-2\choose N-1}}-1\biggr)= {N\over2}\bigl(\sqrt{\pi N}-1\bigr)+O({\sqrt{N}}).$$Proof.Proceed as above:$$\eqalign{C_G(z)&\equiv\sum_{t\in\cal G}{\pi(t)}z^{|t|}\cr &=\sum_{k\ge0}\sum_{t_1\in\cal G}\dots\sum_{t_k\in\cal G} (\pi(t_1)+\cdots+\pi(t_k)+|t_1|+\ldots+|t_k|) z^{|t_1|+\ldots+|t_k|+1}\cr}$$This (eventually) leads to the equation$$C_G(z) = {zC_G(z)+z^2G^\prime(z)\over(1-G(z))^2}.$$which simplifies to give$$C_G(z)={1\over2}{z\over1-4z}-{1\over2}{z\over\sqrt{1-4z}}.$$where $G(z)=zT(z)=(1-\sqrt{1-4z})/2$ is the Catalan generatingfunction, which enumerates general trees.Expanding $[z^N]C_G(z)/[z^N]G(z)$ leads to the stated result.

6.8 Path Length in Binary Search Trees

The analysis of path length in binary search trees is actually thestudy of a property of permutations, not trees, since we startwith a random permutation. In Chapter 7, we discuss properties ofpermutations as combinatorial objects in some detail. We mention theanalysis of path length in BSTs here not only because it isinteresting to compare it with the analysis just given for randomtrees. It is virtually identical to our Quicksortanalysis.

Theorem. (Construction cost of BSTs.)The average number of comparisons involved in theprocess of constructing a binarysearch tree by inserting $N$ distinct keys in random order into aninitially empty tree (the average internal path length of a random binarysearch tree) is $$2(N+1)(H_{N+1}-1)-2N\approx 1.386 N\lg N - 2.846 N$$with variance asymptotic to $(7-2\pi^2/3)N^2$.

Asymptotically, a large BST roughly fits into a $\log{N}$-by-$N/\log{N}$rectangle.

6.9 Additive Parameters of Random Trees.

Our analysesfor path length generalize in a straightforward manner to cover anyadditive parameter that can be aligned with the treerecursion as follows: the value of the parameter for a tree is the sumof the values of the parameter for the subtrees plus an additionalterm for the root. Examples of additive parameters include size, pathlength, and number of leaves.

6.10 Height

Generating functions can also be used to study tree height, but the analysisis much more intricate than for additive parameters.

6.11 Summary of Average-Case Results on Properties of Trees

6.12 Lagrange Inversion

6.13 Rooted Unordered Trees

The following are four major types of trees thatarise in the analysis of algorithms, which form a hierarchy:

• The free tree, an acyclic connected graph.
• The rooted tree, a free tree with a distinguished root node.
• The ordered tree, a rooted tree where the order of thesubtrees of a node is significant.
• The binary tree is an orderedtree where every node has degree 0 or 2.

To this point, we have been studying ordered and binary trees.

In the nomenclature that we use, the adjective describes the characteristicthat separates each type of tree from the one above it in the hierarchy.It is also common to use nomenclature that separates each typefrom the one below it in the hierarchy. Thus, we sometimesrefer to free trees as unrooted trees, rooted trees as unordered trees,and ordered trees as general Catalan trees.

Here is an illustration of the hierarchy for trees with five nodes.The 14 different five-node ordered trees are depicted in the figure,and they are further organized into equivalence classes using smallshaded and larger open rectangles. There are 9 different five-node rootedtrees (those in shaded rectangles are identical asrooted trees) and 3 different five-node free trees(those enclosed in large rectangles are identical as free trees).

A few more words on nomenclature are appropriate because of thevariety of terms found in the literature. Ordered trees are oftencalled plane trees and unordered trees are referred to as nonplane trees. The term plane is used because thestructures can be transformed to one another with continuousoperations in the plane. Though this terminology is widely used, weprefer ordered because of its natural implications with regard tocomputer representations. The term oriented is often usedto refer to the factthat the root is distinguished, so there is an orientation of theedges towards the root; we prefer to use the term rooted if it isnot obvious from the context that there is a root involved.

As the definitions get more restrictive, the number of treesthat are regarded as different gets larger, so, for a given size,there are more rooted trees than free trees, more ordered trees thanrooted trees, and more binary trees than ordered trees. It turns outthat the ratio between the number of rooted trees and the number offree trees is proportional to $N$; the corresponding ratio of orderedtrees to rooted trees grows exponentially with $N$; and the ratio ofbinary trees to ordered trees is a constant. These enumerationsresults are classical, available through analysis along the lines wehave been considering (we considered the analysis for orderedand binary trees earlier in this chapter) and summarized in the table below. The constants in the table are approximate and $\alpha\approx 2.9558$.

6.14 Labelled Trees

6.15 Other Types of Trees

It is often convenient to place various local and global restrictionson trees, for example, to suit requirements of a particular applicationor to try rule out degenerate cases. From a combinatorial standpoint,any restriction corresponds to a new class of tree, and a new set of problemsneed to be solved to enumerate the trees and to learn their statisticalproperties.

This table shows examples of eight different types of trees:3-ary and 4-ary, 3-restricted and 4-restricted, 2-3 and 2-3-4, andred-black and AVL.

Selected Exercises

6.2

What proportion of thebinary trees with $N$ internal nodes have both subtreesof the root nonempty? For $N=4$, the answer is $4/14$.

6.6

What proportion of theforests with $N$ nodes have no trees consisting of a single node?For $N=1,2,3,$ and $4$, the answers are $0, 1/2, 2/5,$ and $3/7$, respectively

6.18

[Kraft equality] Let $k_j$ be the number of external nodes at level$j$ in a binary tree. The sequence $\{ k_0, k_1, \ldots, k_h \}$ (where $h$ isthe height of the tree) describes the profile of the tree.Show that a vector of integers describes the profile of a binarytree if and only if $\sum_j2^{-k_j} = 1$.

6.19

Give tight upper and lower bounds on thepath length of a general tree with $N$ nodes.

6.20

Give tight upper and lower bounds on the internal and externalpath lengths of a binary tree with $N$ internal nodes.

6.27

For $N=2^n-1$, what is the probability that a perfectlybalanced tree structure (all $2^n$ external nodes on level $n$)will be built, if all $N!$ key insertion sequencesare equally likely?

6.42

Internal nodes in binary trees fall into one of three classes:they have either two, one, or zero external children. What fraction ofthe nodes are of each type, in a random binary Catalan tree of $N$ nodes?

6.43

Internal nodes in binary trees fall into one of three classes:they have either two, one, or zero external children. What fraction ofthe nodes are of each type, in a random binary search tree of $N$ nodes?

Review Questions

Q6.1

Give an asymptotic approximation (leading term) for the number of unary-binary trees with $n$ nodes.

Q6.2

Rank these trees in order of their likely height for large $n$:(a) random $n$_node Catalan tree(b) random $n$_node BST(c) random $n$_node AVL tree

Q6.3

A binary trie structure is a binary tree with two types of externalnodes (void and nonvoid) with the restriction that void external nodesdo not appear in leaves. The number of different binary triestructures with n external nodes is 1, 4, and 17 when n is 2, 3, and4, respectively. Starting with the construction$$T = Z_V+(Z_I\times T\times T)+2(Z_N\times Z_I\times (T - Z_V)) $$derive an asymptotic approximation to the number of binary trie structures ofwith n external nodes.

Hint: $$\sqrt{12z^2-8z+1} = {\sqrt{1-2z}\over(1-6z)^{-1/2}}$$.

Q6.4

Give an OGF equation for trees whose nodes all have even degree.

Q6.5

(N. Lindenstrauss)Show that the average length of the right branch in a Catalan tree is ~3.