11institutetext: Department für Elektrotechnik und Informatik, Universität
Siegen, Hölderlinstrasse 3, 57076 Siegen, Germany
11email<EMAIL_ADDRESS>22institutetext: Department of
Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland
7602, South Africa
22email<EMAIL_ADDRESS>33institutetext: Department of Mathematics, Uppsala
Universitet, Box 480, 751 06 Uppsala, Sweden
33email<EMAIL_ADDRESS>
# On the Collection of Fringe Subtrees in Random Binary Trees

Louisa Seelbach Benkner This project has received funding from the European
Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie grant agreement No 731143 and the DFG research project LO
748/10-1 (QUANT-KOMP).11 Stephan Wagner 2233

###### Abstract

A fringe subtree of a rooted tree is a subtree consisting of one of the nodes
and all its descendants. In this paper, we are specifically interested in the
number of non-isomorphic trees that appear in the collection of all fringe
subtrees of a binary tree. This number is analysed under two different random
models: uniformly random binary trees and random binary search trees.

In the case of uniformly random binary trees, we show that the number of non-
isomorphic fringe subtrees lies between $c_{1}n/\sqrt{\ln n}(1+o(1))$ and
$c_{2}n/\sqrt{\ln n}(1+o(1))$ for two constants $c_{1}\approx 1.0591261434$
and $c_{2}\approx 1.0761505454$, both in expectation and with high
probability, where $n$ denotes the size (number of leaves) of the uniformly
random binary tree. A similar result is proven for random binary search trees,
but the order of magnitude is $n/\ln n$ in this case.

Our proof technique can also be used to strengthen known results on the number
of distinct fringe subtrees (distinct in the sense of ordered trees). This
quantity is of the same order of magnitude in both cases, but with slightly
different constants in the upper and lower bounds.

###### Keywords:

Uniformly Random Binary Trees Random Binary Search Trees Fringe Subtrees Tree
Compression

##  1 Introduction

A subtree of a rooted tree that consists of a node and all its descendants is
called a _fringe subtree_. Fringe subtrees are a natural object of study in
the context of random trees, and there are numerous results for various random
tree models, see e.g. [3, 9, 11, 13].

Fringe subtrees are of particular interest in computer science: One of the
most important and widely used lossless compression methods for rooted trees
is to represent a tree as a directed acyclic graph, which is obtained by
merging nodes that are roots of identical fringe subtrees. This compressed
representation of the tree is often shortly referred to as _minimal DAG_ and
its size (number of nodes) is the number of distinct fringe subtrees occurring
in the tree. Compression by minimal DAGs has found numerous applications in
various areas of computer science, as for example in compiler construction [2,
Chapter 6.1 and 8.5], unification [25], symbolic model checking (binary
decision diagrams) [7], information theory [21, 28] and XML compression and
querying [8, 20].

In this work, we investigate the number of fringe subtrees in random binary
trees, i.e. random trees such that each node has either exactly two or no
children. So far, this problem has mainly been studied with respect to ordered
fringe subtrees in random ordered binary trees: A _uniformly random ordered
binary tree_ of size $n$ (with $n$ leaves) is a random tree whose probability
distribution is the uniform probability distribution on the set of ordered
binary trees of size $n$. In [19], Flajolet, Sipala and Steyaert proved that
the expected number of distinct ordered fringe subtrees in a uniformly random
ordered binary tree of size $n$ is asymptotically equal to $c\cdot n/\sqrt{\ln
n}$, where $c$ is the constant $2\sqrt{\ln 4/\pi}$. This result of Flajolet et
al. was extended to unranked labelled trees in [6] (for a different constant
$c$). Moreover, an alternative proof to the result of Flajolet et al. was
presented in [26] in the context of simply-generated families of trees.

Another important type of random trees are so-called _random binary search
trees_ : A random binary search tree of size $n$ is a binary search tree built
by inserting the keys $\\{1,\dots,n\\}$ according to a uniformly chosen random
permutation on $\\{1,\dots,n\\}$. Random binary search trees naturally arise
in theoretical computer science, see e.g. [12]. In [17], Flajolet, Gourdon and
Martinez proved that the expected number of distinct ordered fringe subtrees
in a random binary search tree of size $n$ is $O(n/\ln n)$. This result was
improved in [10] by Devroye, who showed that the asymptotics $\Theta(n/\ln n)$
holds. Moreover, the result of Devroye was generalized from random binary
search trees to a broader class of random ordered binary trees in [27], where
the problem of estimating the expected number of distinct ordered fringe
subtrees in random binary trees was considered in the context of so-called
leaf-centric binary tree sources, which were introduced in [23, 28] as a
general framework for modeling probability distributions on the set of ordered
binary trees of size $n$.

In this work, we focus on estimating the number of _non-isomorphic_ fringe
subtrees in random ordered binary trees, where we call two binary trees non-
isomorphic if they are distinct as unordered binary trees. This question
arises quite naturally for example in the context of XML compression: Here,
one distinguishes between so-called document-centric XML, for which the
corresponding XML document trees are ordered, and data-centric XML, for which
the corresponding XML document trees are unordered. Understanding the
interplay between ordered and unordered structures has thus received
considerable attention in the context of XML (see, for example, [1, 5, 29]).
In particular, in [24], it was investigated whether tree compression can
benefit from unorderedness. For this reason, so-called _unordered minimal
DAGs_ were considered. An unordered minimal DAG of a binary tree is a directed
acyclic graph obtained by merging nodes that are roots of isomorphic fringe
subtrees, i.e. of fringe subtrees which are identical as unordered trees. From
such an unordered minimal DAG, an unordered representation of the original
tree can be uniquely retrieved. The size of this compressed representation is
the number of non-isomorphic fringe subtrees occurring in the tree. So far,
only some worst-case estimates comparing the size of a minimal DAG to the size
of its corresponding unordered minimal DAG are known: Among other things, it
was shown in [24] that the size of an unordered minimal DAG of a binary tree
can be exponentially smaller than the size of the corresponding (ordered)
minimal DAG.

However, no average-case estimates comparing the size of the minimal DAG of a
binary tree to the size of the corresponding unordered minimal DAG are known
so far. In particular, in [24] it is stated as an open problem to estimate the
expected number of non-isomorphic fringe subtrees in a uniformly random
ordered binary tree of size $n$ and conjectured that this number
asymptotically grows as $\Theta(n/\sqrt{\ln n})$.

In this work, as one of our main theorems, we settle this open conjecture by
proving upper and lower bounds of order $n/\sqrt{\ln n}$ for the number of
non-isomorphic fringe subtrees which hold both in expectation and with high
probability (i.e., with probability tending to $1$ as $n\to\infty$). Our
approach can also be used to obtain an analogous result for random binary
search trees, though the order of magnitude changes to $\Theta(n/\ln n)$.
Again, we have upper and lower bounds in expectation and with high
probability. Our two main theorems read as follows.

###### Theorem 1

Let $F_{n}$ be the total number of non-isomorphic fringe subtrees in a
uniformly random ordered binary tree with $n$ leaves. For two constants
$c_{1}\approx 1.0591261434$ and $c_{2}\approx 1.0761505454$, the following
holds:

  1. (i)

$\displaystyle c_{1}\frac{n}{\sqrt{\ln n}}(1+o(1))\leq\mathbb{E}(F_{n})\leq
c_{2}\frac{n}{\sqrt{\ln n}}(1+o(1))$,

  2. (ii)

$\displaystyle c_{1}\frac{n}{\sqrt{\ln n}}(1+o(1))\leq F_{n}\leq
c_{2}\frac{n}{\sqrt{\ln n}}(1+o(1))$ with high probability.

###### Theorem 2

Let $G_{n}$ be the total number of non-isomorphic fringe subtrees in a random
binary search tree with $n$ leaves. For two constants $c_{3}\approx
1.5470025923$ and $c_{4}\approx 1.8191392203$, the following holds:

  1. (i)

$\displaystyle c_{3}\frac{n}{\ln n}(1+o(1))\leq\mathbb{E}(G_{n})\leq
c_{4}\frac{n}{\ln n}(1+o(1))$,

  2. (ii)

$\displaystyle c_{3}\frac{n}{\ln n}(1+o(1))\leq G_{n}\leq c_{4}\frac{n}{\ln
n}(1+o(1))$ with high probability.

To prove the above Theorems 1 and 2, we refine techniques from [26]. Our proof
technique also applies to the problem of estimating the number of distinct
ordered fringe subtrees in uniformly random binary trees or in random binary
search trees. In this case, upper and lower bounds for the expected value have
already been proven by other authors. Our new contribution is to show that
they also hold with high probability.

###### Theorem 3

Let $H_{n}$ denote the total number of distinct fringe subtrees in a uniformly
random ordered binary tree with $n$ leaves. Then, for the constant
$c=2\sqrt{\ln 4/\pi}\approx 1.3285649405$, the following holds:

  1. (i)

$\displaystyle\mathbb{E}(H_{n})=c\frac{n}{\sqrt{\ln n}}(1+o(1))$,

  2. (ii)

$\displaystyle H_{n}=c\frac{n}{\sqrt{\ln n}}(1+o(1))$ with high probability.

Here, the first part (i) was already shown in [19] and [26], part (ii) is new.
Similarly, we are able to strengthen the results of [10] and [27]:

###### Theorem 4

Let $J_{n}$ be the total number of distinct fringe subtrees in a random binary
search tree with $n$ leaves. For two constants $c_{5}\approx 2.4071298335$ and
$c_{6}\approx 2.7725887222$, the following holds:

  1. (i)

$\displaystyle c_{5}\frac{n}{\ln n}(1+o(1))\leq\mathbb{E}(J_{n})\leq
c_{6}\frac{n}{\ln n}(1+o(1))$,

  2. (ii)

$\displaystyle c_{5}\frac{n}{\ln n}(1+o(1))\leq J_{n}\leq c_{6}\frac{n}{\ln
n}(1+o(1))$ with high probability.

The upper bound in part (i) can already be found in [17] and [10]. Moreover, a
lower bound of the form $\mathbb{E}(J_{n})\geq\frac{\alpha n}{\ln n}(1+o(1))$
was already shown in [10] for the constant $\alpha=(\ln 3)/2\approx
0.5493061443$ and in [27] for the constant $\alpha\approx 0.6017824584$. So
our new contributions are part (ii) and the improvement of the lower bound on
$\mathbb{E}(J_{n})$.

##  2 Preliminaries

Let $\mathcal{T}$ denote the set of ordered binary trees, i.e. of ordered
rooted trees such that each node has either exactly two or no children. We
define the _size_ $|t|$ of a binary tree $t\in\mathcal{T}$ as the number of
leaves of $t$ and by $\mathcal{T}_{k}$ we denote the set of binary trees of
size $k$ for every integer $k\geq 1$. It is well known that
$|\mathcal{T}_{k}|=C_{k-1}$, where $C_{k}$ denotes the $k$-th _Catalan number_
[18]: We have

$\displaystyle
C_{k}=\frac{1}{k+1}\binom{2k}{k}\sim\frac{4^{k}}{\sqrt{\pi}k^{3/2}}(1+O(1/k)),$
(1)

where the asymptotic growth of the Catalan numbers follows from Stirling’s
Formula [18]. Analogously, let $\mathcal{U}$ denote the set of unordered
binary trees, i.e. of unordered rooted trees such that each node has either
exactly two or no children. The _size_ $|u|$ of an unordered tree
$u\in\mathcal{U}$ is again the number of leaves of $u$ and by
$\mathcal{U}_{k}$ we denote the set of unordered binary trees of size $k$. We
have $|\mathcal{U}_{k}|=W_{k}$, where $W_{k}$ denotes the $k$-th _Wedderburn-
Etherington number_. Their asymptotic growth is

$\displaystyle W_{k}\sim A\cdot k^{-3/2}\cdot b^{k},$ (2)

for certain positive constants $A,b$ [4, 16]. In particular, we have $b\approx
2.4832535362$.

A _fringe subtree_ of a binary tree is a subtree consisting of a node and all
its descendants. For a binary tree $t$ and a given node $v\in t$, let $t(v)$
denote the fringe subtree of $t$ rooted at $v$. Two fringe subtrees are called
_distinct_ if they are distinct as ordered binary trees.

Every tree $t\in\mathcal{T}$ can be considered as an element of $\mathcal{U}$
by simply forgetting the ordering on $t$’s nodes. If two binary trees
$t_{1},t_{2}$ correspond to the same unordered tree $u\in\mathcal{U}$, we call
them _isomorphic_ : Thus, we obtain a partition of $\mathcal{T}$ into
isomorphism classes. If two binary trees $t_{1},t_{2}\in\mathcal{T}$ belong to
the same isomorphism class, we can obtain $t_{1}$ from $t_{2}$ and vice versa
by reordering the children of some of $t_{1}$’s (respectively, $t_{2}$’s)
inner nodes. An inner node $v$ of an ordered or unordered binary tree $t$ is
called a _symmetrical node_ if the fringe subtrees rooted at $v$’s children
are isomorphic. Let $\operatorname{sym}(t)$ denote the number of symmetrical
nodes of $t$. The cardinality of the automorphism group of $t$ is given by
$\lvert\operatorname{\mathrm{Aut}}(t)\rvert=2^{\operatorname{sym}(t)}$. Thus,
by the orbit-stabilizer theorem, there are $2^{k-1-\operatorname{sym}(t)}$
many ordered binary trees in the isomorphism class of $t\in\mathcal{T}_{k}$,
and likewise $2^{k-1-\operatorname{sym}(t)}$ many ordered representations of
$t\in\mathcal{U}_{k}$.

We consider two types of probability distributions on the set of ordered
binary trees of size $n$:

  * (i)

The _uniform probability distribution_ on $\mathcal{T}_{n}$, that is, every
binary tree of size $n$ is assigned the same probability $\frac{1}{C_{n-1}}$.
A random variable taking values in $\mathcal{T}_{n}$ according to the uniform
probability distribution is called a _uniformly random (ordered) binary tree_
of size $n$.

  * (ii)

The probability distribution induced by the so-called _Binary Search Tree
Model_ (see e.g. [12, 17]): The corresponding probability mass function
$P_{\operatorname{bst}}:\mathcal{T}_{n}\rightarrow[0,1]$ is given by

$\displaystyle P_{\operatorname{bst}}(t)=\prod_{v\in
t\atop|t(v)|>1}\frac{1}{|t(v)|-1},$ (3)

for every $n\geq 1$. A random variable taking values in $\mathcal{T}_{n}$
according to this probability mass function is called a _random binary search
tree_ of size $n$.

Before we start with proving our main results, we need two preliminary lemmas
on the number of fringe subtrees in uniformly random ordered binary trees and
in random binary search trees:

###### Lemma 1

Let $a,\varepsilon$ be positive real numbers with $\varepsilon<\frac{1}{3}$.
For every positive integer $k$ with $a\ln n\leq k\leq n^{\varepsilon}$, let
$\mathcal{S}_{k}\subset\mathcal{T}_{k}$ be a set of ordered binary trees with
$k$ leaves. We denote the cardinality of $\mathcal{S}_{k}$ by $s_{k}$. Let
$X_{n,k}$ denote the (random) number of fringe subtrees with $k$ leaves in a
uniformly random ordered binary tree with $n$ leaves that belong to
$\mathcal{S}_{k}$. Moreover, let $Y_{n,\varepsilon}$ denote the (random)
number of arbitrary fringe subtrees with more than $n^{\varepsilon}$ leaves in
a uniformly random ordered binary tree with $n$ leaves. We have

  1. (1)

$\mathbb{E}(X_{n,k})=s_{k}4^{1-k}n\big{(}1+O(k/n)\big{)}$ for all $k$ with
$a\ln n\leq k\leq n^{\varepsilon}$, the $O$-constant being independent of $k$,

  2. (2)

$\mathbb{V}(X_{n,k})=s_{k}4^{1-k}n(1+O(k^{-1/2}))$ for all $k$ with $a\ln
n\leq k\leq n^{\varepsilon}$, again with an $O$-constant that is independent
of $k$,

  3. (3)

$\mathbb{E}(Y_{n,\varepsilon})=O(n^{1-\varepsilon/2})$ and

  4. (4)

with high probability, the following statements hold simultaneously:

     * (i)

$|X_{n,k}-\mathbb{E}(X_{n,k})|\leq s_{k}^{1/2}2^{-k}n^{1/2+\varepsilon}$ for
all $k$ with $a\ln n\leq k\leq n^{\varepsilon}$,

     * (ii)

$Y_{n,\varepsilon}\leq n^{1-\varepsilon/3}$.

We emphasize (since it will be important later) that the inequality in part
(4), item (i), does not only hold with high probability for each individual
$k$, but that it is satisfied with high probability for all $k$ in the given
range simultaneously.

###### Proof

(1) Recall first that the number of ordered binary trees with $n$ leaves is
the Catalan number $C_{n-1}=\frac{1}{n}\binom{2n-2}{n-1}$. We observe that
every occurrence of a fringe subtree in $\mathcal{S}_{k}$ in a tree with $n$
leaves can be obtained by choosing an ordered tree with $n-k+1$ leaves,
picking one of the leaves and replacing it by a tree in $\mathcal{S}_{k}$.
Thus the total number of occurrences is

$\frac{1}{n-k+1}\binom{2n-2k}{n-k}\cdot(n-k+1)\cdot
s_{k}=\binom{2n-2k}{n-k}s_{k}.$

Consequently, the average number is

$\mathbb{E}(X_{n,k})=\frac{\binom{2n-2k}{n-k}s_{k}}{\frac{1}{n}\binom{2n-2}{n-1}}=s_{k}4^{1-k}n\big{(}1+O(k/n)\big{)},$

by Stirling’s formula (the $O$-constant being independent of $k$ in the
indicated range).

(2) The variance is determined in a similar fashion: we first count the total
number of pairs of fringe subtrees in $\mathcal{S}_{k}$ that appear in the
same ordered tree with $n$ leaves. Each such pair can be obtained as follows:
take an ordered tree with $n-2k+2$ leaves, pick two leaves, and replace them
by fringe subtrees in $\mathcal{S}_{k}$. The total number is thus

$\frac{1}{n-2k+2}\binom{2n-4k+2}{n-2k+1}\cdot\binom{n-2k+2}{2}\cdot
s_{k}^{2}=\frac{n-2k+1}{2}\binom{2n-4k+2}{n-2k+1}s_{k}^{2},$

giving us

$\mathbb{E}\Big{(}\binom{X_{n,k}}{2}\Big{)}=\frac{\frac{n-2k+1}{2}\binom{2n-4k+2}{n-2k+1}s_{k}^{2}}{\frac{1}{n}\binom{2n-2}{n-1}}=s_{k}^{2}4^{2-2k}\frac{n^{2}}{2}\big{(}1+O(k/n)\big{)},$

again by Stirling’s formula. The second moment and the variance are now
derived from this formula in a straightforward fashion: We find

$\displaystyle\mathbb{E}(X_{n,k}^{2})=2\mathbb{E}\Big{(}\binom{X_{n,k}}{2}\Big{)}+\mathbb{E}(X_{n,k})=\left(s_{k}^{2}4^{2-2k}n^{2}+s_{k}4^{1-k}n\right)\big{(}1+O(k/n)\big{)},$

and thus, as $s_{k}/C_{k-1}\leq 1$,

$\displaystyle\mathbb{V}(X_{n,k})$
$\displaystyle=\mathbb{E}(X_{n,k}^{2})-\mathbb{E}(X_{n,k})^{2}=O(s_{k}^{2}4^{2-2k}nk)+s_{k}4^{1-k}n(1+O(k/n))$
$\displaystyle=O\left(\frac{s_{k}^{2}}{C_{k-1}^{2}}\frac{n}{k^{2}}\right)+\frac{s_{k}}{C_{k-1}}\frac{n}{\sqrt{\pi}k^{3/2}}(1+O(1/k))=s_{k}4^{1-k}n(1+O(1/k^{1/2})).$

(3) To obtain the estimate for $\mathbb{E}(Y_{n,\varepsilon})$, we observe
that the average total number of fringe subtrees with $k$ leaves is

$\frac{\binom{2n-2k}{n-k}\cdot\frac{1}{k}\binom{2k-2}{k-1}}{\frac{1}{n}\binom{2n-2}{n-1}}=O\Big{(}\frac{n^{3/2}}{k^{3/2}(n-k+1)^{1/2}}\Big{)},$

where the estimate follows from Stirling’s formula again for
$k>n^{\varepsilon}$. Summing over all $k$, we get

$\mathbb{E}(Y_{n,\varepsilon})=O\Big{(}n^{3/2}\sum_{n^{\varepsilon}<k\leq
n}\frac{1}{k^{3/2}(n-k+1)^{1/2}}\Big{)}=O(n^{1-\varepsilon/2}).$

(4) For the second part, we apply Chebyshev’s inequality to obtain
concentration of $X_{n,k}$:

$\mathbb{P}\Big{(}\big{|}X_{n,k}-\mathbb{E}(X_{n,k})\big{|}\geq
s_{k}^{1/2}2^{-k}n^{1/2+\varepsilon}\Big{)}\leq\frac{\mathbb{V}(X_{n,k})}{s_{k}4^{-k}n^{1+2\varepsilon}}=O\big{(}n^{-2\varepsilon}\big{)}.$

Hence, by the union bound, the probability that the stated inequality fails
for any $k$ in the given range is only $O(n^{-\varepsilon})$, proving that the
first statement holds with high probability. Finally, Markov’s inequality
implies that

$\mathbb{P}\big{(}Y_{n,\varepsilon}>n^{1-\varepsilon/3}\big{)}\leq\frac{\mathbb{E}(Y_{n,\varepsilon})}{n^{1-\varepsilon/3}}=O(n^{-\varepsilon/6}),$

showing that the second inequality holds with high probability as well.
$\scriptstyle\blacksquare$

For the number of fringe subtrees in random binary search trees, a very
similar lemma holds:

###### Lemma 2

Let $a,\varepsilon$ be positive real numbers with $\varepsilon<\frac{1}{3}$
and let $n$ and $k$ denote positive integers. Moreover, for every $k$, let
$\mathcal{S}_{k}\subset\mathcal{T}_{k}$ be a set of ordered binary trees with
$k$ leaves and let $p_{k}$ denote the probability that a random binary search
tree is contained in $\mathcal{S}_{k}$, that is, $p_{k}=\sum
P_{\operatorname{bst}}(t)$, where the sum is taken over all binary trees in
$\mathcal{S}_{k}$. Let $X_{n,k}$ denote the (random) number of fringe subtrees
with $k$ leaves in a random binary search tree with $n$ leaves that belong to
$\mathcal{S}_{k}$. Moreover, let $Y_{n,\varepsilon}$ denote the (random)
number of arbitrary fringe subtrees with more than $n^{\varepsilon}$ leaves in
a random binary search tree with $n$ leaves. We have

  * (1)

$\mathbb{E}(X_{n,k})=\frac{2p_{k}n}{k(k+1)}$ for $1\leq k<n$,

  * (2)

$\mathbb{V}(X_{n,k})=O(p_{k}n/k^{2})$ for all $k$ with $a\ln n\leq k\leq
n^{\varepsilon}$, where the $O$-constant is independent of $k$,

  * (3)

$\mathbb{E}(Y_{n,\varepsilon})=2n/\lceil
n^{\varepsilon}\rceil-1=O(n^{1-\varepsilon})$ and

  * (4)

with high probability, the following statements hold simultaneously:

    * (i)

$|X_{n,k}-\mathbb{E}(X_{n,k})|\leq p_{k}^{1/2}k^{-1}n^{1/2+\varepsilon}$ for
all $k$ with $a\ln n\leq k\leq n^{\varepsilon}$,

    * (ii)

$Y_{n,\varepsilon}\leq n^{1-\varepsilon/2}$.

###### Proof

(1) In order to estimate $\mathbb{E}(X_{n,k})$, we define $Z_{n,k}$ as the
(random) number of arbitrary fringe subtrees with $k$ leaves in a random
binary search tree with $n$ leaves. That is, $Z_{n,k}=X_{n,k}$ for
$\mathcal{S}_{k}=\mathcal{T}_{k}$. Applying the law of total expectation, we
find

$\displaystyle\mathbb{E}(X_{n,k})=\sum_{m=0}^{n}\mathbb{E}(X_{n,k}\mid
Z_{n,k}=m)\mathbb{P}(Z_{n,k}=m).$

As $X_{n,k}$ conditioned on $Z_{n,k}=m$ for some integer $m$ is binomially
distributed with parameters $m$ and $p_{k}$, we find $\mathbb{E}(X_{n,k}\mid
Z_{n,k}=m)=mp_{k}$ and hence

$\displaystyle\mathbb{E}(X_{n,k})=p_{k}\sum_{m=0}^{n}m\mathbb{P}(Z_{n,k}=m)=p_{k}\mathbb{E}(Z_{n,k}).$

With $\mathbb{E}(Z_{n,k})=\frac{2n}{k(k+1)}$ (see for example [14]), the
statement follows.

(2) In order to estimate $\mathbb{V}(X_{n,k})$, we apply the law of total
variance:

$\displaystyle\mathbb{V}(X_{n,k})=\mathbb{V}(\mathbb{E}(X_{n,k}\mid
Z_{n,k}))+\mathbb{E}(\mathbb{V}(X_{n,k}\mid Z_{n,k})).$

Again as $X_{n,k}$ conditioned on $Z_{n,k}=m$ for some integer $m$ is
binomially distributed with parameters $m$ and $p_{k}$, we find
$\mathbb{E}(X_{n,k}\mid Z_{n,k})=p_{k}Z_{n,k}$ and $\mathbb{V}(X_{n,k}\mid
Z_{n,k})=Z_{n,k}p_{k}(1-p_{k})$. Thus, we have

$\displaystyle\mathbb{V}(X_{n,k})=\mathbb{V}(p_{k}Z_{n,k})+\mathbb{E}(Z_{n,k}p_{k}(1-p_{k}))=\mathbb{V}(Z_{n,k})p_{k}^{2}+\mathbb{E}(Z_{n,k})p_{k}(1-p_{k}).$

With $\mathbb{E}(Z_{n,k})=\frac{2n}{k(k+1)}$ and

$\mathbb{V}(Z_{n,k})=\frac{2(k-1)(4k^{2}-3k-4)n}{(k+1)^{2}k(2k-1)(2k+1)},$

(see for example [14]), this yields

$\displaystyle\mathbb{V}(X_{n,k})=\frac{2(k-1)(4k^{2}-3k-4)np_{k}^{2}}{(k+1)^{2}k(2k-1)(2k+1)}+\frac{2np_{k}(1-p_{k})}{k(k+1)}=O\left(\frac{np_{k}}{k^{2}}\right).$

(3) In order to estimate $\mathbb{E}(Y_{n,\varepsilon})$, first observe that

$\displaystyle\mathbb{E}(Y_{n,\varepsilon})=\sum_{k>n^{\varepsilon}}\mathbb{E}(Z_{n,k}).$

With $\mathbb{E}(Z_{n,k})=\frac{2n}{k(k+1)}$ for $n^{\varepsilon}<k<n$ and
$\mathbb{E}(Z_{n,n})=1$, this yields

$\displaystyle\mathbb{E}(Y_{n,\varepsilon})=\sum_{n^{\varepsilon}<k\leq
n-1}\frac{2n}{k(k+1)}+1=\frac{2n}{\lceil
n^{\varepsilon}\rceil}-1=O(n^{1-\varepsilon}).$

(4) For the second part of the statement, we apply Chebyshev’s inequality to
obtain:

$\displaystyle\mathbb{P}\left(\left|X_{n,k}-\frac{2np_{k}}{k(k+1)}\right|\geq
p_{k}^{1/2}n^{1/2+\varepsilon}k^{-1}\right)\leq\frac{\mathbb{V}(X_{n,k})k^{2}}{p_{k}n^{1+2\varepsilon}}=O(n^{-2\varepsilon}).$

Hence, by the union bound, the probability that the stated inequality fails
for any $k$ in the given range is $O(n^{-\varepsilon})$, proving that the
given statement holds with high probability. Furthermore, with Markov’s
inequality, we find

$\displaystyle\mathbb{P}(Y_{n,\varepsilon}>n^{1-\varepsilon/2})\leq\frac{\mathbb{E}(Y_{n,\varepsilon})}{n^{1-\varepsilon/2}}=O(n^{-\varepsilon/2}).$

Thus, the second inequality holds with high probability as well.
$\scriptstyle\blacksquare$

##  3 Fringe Subtrees in Uniformly Random Binary Trees

###  3.1 Ordered Fringe Subtrees

We provide the proof of Theorem 3 first, since it is simplest and provides us
with a template for the other proofs. Basically, it is a refinement of the
proof for the corresponding special case of Theorem 3.1 in [26]. In the
following sections, we refine the argument further to prove Theorems 1, 2 and
4.

######  Proof (Proof of Theorem 3)

We prove the statement in two steps: In the first step, we show that the upper
bound $H_{n}\leq cn/\sqrt{\ln n}(1+o(1))$ holds for $c=2\sqrt{\ln 4/\pi}$ both
in expectation and with high probability. In the second step, we prove the
corresponding lower bound.

_The upper bound:_ Let $k_{0}=\log_{4}n$. The number $H_{n}$ of distinct
fringe subtrees in a uniformly random ordered binary tree with $n$ leaves
equals (i) the number of such distinct fringe subtrees of size at most $k_{0}$
plus (ii) the number of such distinct fringe subtrees of size greater than
$k_{0}$. We upper-bound (i) by the number of all ordered binary trees of size
at most $k_{0}$ (irrespective of their occurrence as fringe subtrees), which
is

$\displaystyle\sum_{k=0}^{k_{0}-1}C_{k}=O\left(\frac{4^{k_{0}}}{k_{0}^{3/2}}\right)=O\left(\frac{n}{(\ln
n)^{3/2}}\right).$

This upper bound holds deterministically. Furthermore, we upper-bound (ii) by
the total number of fringe subtrees of size greater than $k_{0}$ occurring in
the tree: We apply Lemma 1 with $a=1/\ln 4$ and $\varepsilon=1/6$ and let
$\mathcal{S}_{k}$ denote the set $\mathcal{T}_{k}$, such that $s_{k}=C_{k-1}$,
to obtain:

$\displaystyle\left(\sum_{k_{0}<k\leq
n^{\varepsilon}}X_{n,k}\right)+Y_{n,\varepsilon}$
$\displaystyle=\frac{n}{\sqrt{\pi}}\sum_{k_{0}<k\leq
n^{\varepsilon}}k^{-3/2}\left(1+O(k^{-1})\right)+O(n^{1-\varepsilon/3})$
$\displaystyle=\frac{2\sqrt{\ln 4}}{\sqrt{\pi}}\cdot\frac{n}{\sqrt{\ln
n}}+O(n/(\ln n)^{3/2}),$

in expectation and with high probability as well, as the estimate from Lemma 1
(part (4)) holds with high probability simultaneously for all $k$ in the given
range. As we have

$\displaystyle H_{n}\leq\sum_{k\leq k_{0}}C_{k-1}+\Big{(}\sum_{k_{0}<k\leq
n^{\varepsilon}}X_{n,k}\Big{)}+Y_{n,\varepsilon},$

we can combine the two bounds to obtain the upper bound on $H_{n}$ stated in
Theorem 3, both in expectation and with high probability.

_The lower bound:_ Again, let $k_{0}=\log_{4}n$ and $\varepsilon=\frac{1}{6}$.
From the first part of the proof, we find that the main contribution to the
total number of fringe subtrees in a uniformly random binary tree of size $n$
comes from fringe subtrees of sizes $k$ with $k_{0}<k\leq n^{\varepsilon}$.
Hence, in order to lower-bound the number $H_{n}$ of distinct fringe subtrees
in a uniformly random binary tree with $n$ leaves, we only count distinct
fringe subtrees of sizes $k$ with $k_{0}<k\leq n^{\varepsilon}$ and show that
we did not overcount too much in the first part of the proof by upper-bounding
this number by the total number of fringe subtrees of sizes $k$. To this end,
let $X_{n,k}^{(2)}$ denote the number of pairs of identical fringe subtrees of
size $k$ in a uniformly random ordered binary tree of size $n$. Each such pair
can be obtained as follows: Take an ordered tree with $n-2k+2$ leaves, pick
two leaves, and replace them by the same ordered binary tree of size $k$. The
total number of such pairs of identical fringe subtrees of size $k$ is thus

$\displaystyle C_{n-2k+1}\cdot\binom{n-2k+2}{2}\cdot
C_{k-1}=\frac{4^{n-k}}{2\pi k^{3/2}}(n-2k+1)^{1/2}(1+O(1/k)).$

By dividing by $C_{n-1}$, i.e. the total number of binary trees of size $n$,
we thus obtain the expected value:

$\displaystyle\mathbb{E}(X_{n,k}^{(2)})=\frac{1}{C_{n-1}}\frac{4^{n-k}}{2\pi
k^{3/2}}(n-2k+1)^{1/2}(1+O(1/k))=O(4^{-k}n^{2}k^{-3/2}).$

Thus, we find

$\displaystyle\sum_{k_{0}<k\leq
n^{\varepsilon}}\mathbb{E}(X_{n,k}^{(2)})=O\left(n^{2}\frac{4^{-k_{0}}}{k_{0}^{3/2}}\right)=O\left(\frac{n}{(\ln
n)^{3/2}}\right).$

If a binary tree of size $k$ occurs $m$ times as a fringe subtree in a
uniformly random binary tree of size $n$, it contributes $m-\binom{m}{2}$ to
the random variable $X_{n,k}-X_{n,k}^{(2)}$. Since $m-\binom{m}{2}\leq 1$ for
all non-negative integers $m$, we find that $X_{n,k}-X_{n,k}^{(2)}$ is a lower
bound on the number of distinct fringe subtrees with $k$ leaves. Hence, we
have

$\displaystyle H_{n}\geq\sum_{k_{0}<k\leq
n^{\varepsilon}}X_{n,k}-\sum_{k_{0}<k\leq n^{\varepsilon}}X_{n,k}^{(2)}.$

The second sum is $O(n/(\ln n)^{3/2})$ in expectation and thus with high
probability as well by the Markov inequality. As the first sum is
$\frac{2\sqrt{\ln 4}}{\sqrt{\pi}}\cdot\frac{n}{\sqrt{\ln n}}(1+o(1)),$ both in
expectation and with high probability by our estimate from the first part of
the proof, the statement of Theorem 3 follows. $\scriptstyle\blacksquare$

As the main idea of the proof is to split the number of distinct fringe
subtrees into the number of distinct fringe subtrees of size at most $k_{0}$
plus the number of distinct fringe subtrees of size greater than $k_{0}$ for
some suitably chosen integer $k_{0}$, this type of argument is called a _cut-
point argument_ and the integer $k_{0}$ is called the _cut-point_ (see [17]).
This basic technique is applied in several previous papers to similar problems
(see for instance [10], [17], [26], [27]). Moreover, we remark that the
statement of Theorem 3 can be easily generalized to simply generated families
of trees.

###  3.2 Unordered Fringe Subtrees

In this subsection, we prove Theorem 1. For this, we refine the cut-point
argument we applied in the proof of Theorem 3: In particular, for the lower
bound on $F_{n}$, we need a result due to Bóna and Flajolet [4] on the number
of automorphisms of a uniformly random ordered binary tree. It is stated for
random phylogenetic trees in [4], but the two probabilistic models are
equivalent.

######  Theorem 5 ([4], Theorem 2)

Consider a uniformly random ordered binary tree $T_{k}$ with $k$ leaves, and
let $A_{k}=\lvert\operatorname{\mathrm{Aut}}(T_{k})\rvert$ be the cardinality
of its automorphism group. The logarithm of this random variable satisfies a
central limit theorem: For certain positive constants $\gamma$ and
$\sigma_{1}$, we have

$\mathbb{P}(A_{k}\leq 2^{\gamma
k+\sigma_{1}\sqrt{k}x})\overset{k\to\infty}{\to}\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-t^{2}/2}\,dt$

for every real number $x$. The numerical value of the constant $\gamma$ is
$0.2710416936$.

With Theorem 5, we are able to upper-bound the probability that two fringe
subtrees of the same size are isomorphic in our proof of Theorem 1:

######  Proof (Proof of Theorem 1)

We prove the statement in two steps: First, we show that the upper bound on
$F_{n}$ stated in Theorem 1 holds both in expectation and with high
probability, then we prove the respective lower bound.

_The upper bound:_ The proof for the upper bound in Theorem 1 exactly matches
the first part of the proof of Theorem 3, except that we choose a different
cut-point: Let $k_{0}=\log_{b}n$, where $b\approx 2.4832535362$ is the
constant in the asymptotic formula (2) for the Wedderburn-Etherington numbers.
We then find

$\displaystyle F_{n}\leq\sum_{k<k_{0}}W_{k}+\Big{(}\sum_{k_{0}\leq k\leq
n^{\epsilon}}X_{n,k}\Big{)}+Y_{n,\epsilon}=\frac{2\sqrt{\ln
b}}{\sqrt{\pi}}\cdot\frac{n}{\sqrt{\ln n}}+O(n(\ln n)^{-3/2}),$

both in expectation and with high probability, where the estimates for
$X_{n,k}$ and $Y_{n,\varepsilon}$ follow again from Lemma 1. We have
$2\sqrt{\ln b}/\sqrt{\pi}\approx 1.0761505454$.

_The lower bound:_ As a consequence of Theorem 5, the probability that the
cardinality of the automorphism group of a uniformly random binary tree
$T_{k}$ of size $k$ satisfies
$\lvert\operatorname{\mathrm{Aut}}(T_{k})\rvert\leq 2^{\gamma k-k^{3/4}}$
tends to $0$ as $k\to\infty$. We define $\mathcal{S}_{k}$ as the set of
ordered trees with $k$ leaves that do not satisfy this inequality, so that
$s_{k}=|\mathcal{S}_{k}|=C_{k-1}(1+o(1))$. Our lower bound is based on
counting only fringe subtrees in $\mathcal{S}_{k}$ for suitable $k$. The
reason for this choice is that we have an upper bound on the number of ordered
binary trees in the same isomorphism class for every tree in
$\mathcal{S}_{k}$. Recall that the number of possible ordered representations
of an unordered binary tree $t$ with $k$ leaves is given by
$2^{k-1}/\lvert\operatorname{\mathrm{Aut}}(t)\rvert$ by the orbit-stabiliser
theorem. Hence, the number of ordered binary trees in the same isomorphism
class as a tree $t\in\mathcal{S}_{k}$ is bounded above by $2^{k-1-\gamma
k+k^{3/4}}$.

Now set $k_{1}=\frac{1+\delta}{1+\gamma}\log_{2}n$ for some positive constant
$\delta<\frac{2}{3}$, and consider only fringe subtrees that belong to
$\mathcal{S}_{k}$, where $k_{1}\leq k\leq n^{\delta/2}$. By Lemma 1, the
number of such fringe subtrees in a random ordered binary tree with $n$ leaves
is

$s_{k}4^{1-k}n(1+O(k/n+s_{k}^{-1/2}2^{k}n^{(\delta-1)/2}))$

both in expectation and with high probability. Since $s_{k}=C_{k-1}(1+o(1))$,
the number of fringe subtrees that belong to $\mathcal{S}_{k}$ in a random
ordered binary tree of size $n$ becomes $\frac{n}{\sqrt{\pi k^{3}}}(1+o(1))$.
We show that most of these trees are the only representatives of their
isomorphism classes as fringe subtrees. To this end, we consider all fringe
subtrees in $\mathcal{S}_{k}$ for some $k$ that satisfies $k_{1}\leq k\leq
n^{\delta/2}$. Let the sizes of the isomorphism classes of trees in
$\mathcal{S}_{k}$ be $r_{1},r_{2},\ldots,r_{\ell}$, so that
$r_{1}+r_{2}+\cdots+r_{\ell}=s_{k}$. By definition of $\mathcal{S}_{k}$, we
have $r_{i}\leq 2^{k-1-\gamma k+k^{3/4}}$ for every $i$. Let us condition on
the event that their number $X_{n,k}$ is equal to $N$ for some $N\leq n$. Each
of these $N$ fringe subtrees $S_{1},S_{2},\ldots,S_{N}$ follows a uniform
distribution among the elements of $\mathcal{S}_{k}$, so the probability of
being in an isomorphism class with $r_{i}$ elements is $r_{i}/s_{k}$.
Moreover, the $N$ fringe subtrees are also all independent. Let
$X_{n,k}^{(2)}$ be the number of pairs of isomorphic trees among the fringe
subtrees with $k$ leaves. We have

$\displaystyle\mathbb{E}\big{(}X_{n,k}^{(2)}|X_{n,k}=N\big{)}$
$\displaystyle=\binom{N}{2}\sum_{i}\Big{(}\frac{r_{i}}{s_{k}}\Big{)}^{2}\leq\frac{n^{2}}{2s_{k}^{2}}\sum_{i}r_{i}^{2}\leq\frac{n^{2}}{s_{k}}2^{k-2-\gamma
k+k^{3/4}}.$

Since this holds for all $N$, the law of total expectation yields

$\mathbb{E}\big{(}X_{n,k}^{(2)}\big{)}\leq\frac{n^{2}}{s_{k}}2^{k-2-\gamma
k+k^{3/4}}=\sqrt{\pi}n^{2}k^{3/2}2^{-k-\gamma k+k^{3/4}}(1+o(1)).$

Since $k\geq k_{1}=\frac{1+\delta}{1+\gamma}\log_{2}n$, we find that

$\mathbb{E}\big{(}X_{n,k}^{(2)}\big{)}\leq
n^{2}2^{-(1+\gamma)k+O(k^{3/4})}\leq n^{1-\delta}\exp\big{(}O((\ln
n)^{3/4})\big{)}.$

Thus

$\sum_{k_{1}\leq k\leq n^{\delta/2}}\mathbb{E}\big{(}X_{n,k}^{(2)}\big{)}\leq
n^{1-\delta/2}\exp\big{(}O((\ln n)^{3/4})\big{)}=o(n/\sqrt{\ln n}).$

As in the previous proof, we see that $X_{n,k}-X_{n,k}^{(2)}$ is a lower bound
on the number of non-isomorphic fringe subtrees with $k$ leaves. This gives us

$F_{n}\geq\sum_{k_{1}\leq k\leq n^{\delta/2}}X_{n,k}-\sum_{k_{1}\leq k\leq
n^{\delta/2}}X_{n,k}^{(2)}.$

The second sum is negligible since it is $o(n/\sqrt{\ln n})$ in expectation
and thus also with high probability by the Markov inequality. For the first
sum, a calculation similar to that for the upper bound shows that it is

$\frac{2\sqrt{(1+\gamma)\ln 2}}{\sqrt{\pi(1+\delta)}}\cdot\frac{n}{\sqrt{\ln
n}}(1+o(1)),$

both in expectation and with high probability. Since $\delta$ is arbitrary, we
can choose any constant smaller than $\frac{2\sqrt{(1+\gamma)\ln
2}}{\sqrt{\pi}}\approx 1.0591261434$ for $c_{1}$. $\scriptstyle\blacksquare$

##  4 Fringe Subtrees in Random Binary Search Trees

In this section, we prove our results presented in Theorem 2 and Theorem 4 on
the number of distinct, respectively, non-isomorphic fringe subtrees in a
random binary search tree. In order to show the respective lower bounds of
Theorem 2 and Theorem 4, we need two theorems similar to Theorem 5: The first
one shows that the logarithm of the random variable
$B_{k}=P_{\operatorname{bst}}(T_{k})^{-1}$, where $T_{k}$ denotes a random
binary search tree of size $k$, satisfies a central limit theorem and is
needed to estimate the probability that two fringe subtrees in a random binary
search tree are identical. The second one transfers the statement of Theorem 5
from uniformly random binary trees to random binary search trees and is needed
in order to estimate the probability that two fringe subtrees in a random
binary search tree are isomorphic. The first of these two central limit
theorems is shown in [15]:

######  Theorem 6 ([15], Theorem 4.1)

Consider a random binary search tree $T_{k}$ with $k$ leaves, and let
$B_{k}=P_{\operatorname{bst}}(T_{k})^{-1}$. The logarithm of this random
variable satisfies a central limit theorem: For certain positive constants
$\mu$ and $\sigma_{2}$, we have

$\displaystyle\mathbb{P}\left(B_{k}\leq 2^{\mu
k+\sigma_{2}\sqrt{k}x}\right)\overset{k\to\infty}{\to}\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-t^{2}/2}\,dt$

for every real number $x$. The numerical value of the constant $\mu$ is

$\displaystyle\mu=\sum_{k=1}^{\infty}\frac{2\log_{2}k}{(k+1)(k+2)}\approx
1.7363771368.$

The second of these two central limit theorems follows from a general theorem
devised by Holmgren and Janson [22]: Let $f:\mathcal{T}\rightarrow\mathbb{R}$
denote a function mapping an ordered binary tree to a real number. Moreover,
given such a mapping $f$, define
$\mathcal{F}:\mathcal{T}\rightarrow\mathbb{R}$ by

$\displaystyle\mathcal{F}(t)=\sum_{v\in t}f(t(v)).$

The theorem by Holmgren and Janson states:

######  Theorem 7 ([22], Theorem 1.14)

Let $T_{k}$ be a random binary search tree of size $k$. If

$\displaystyle\sum_{k=1}^{\infty}\frac{\mathbb{V}(f(T_{k}))^{1/2}}{k^{3/2}}<\infty,\quad\lim_{k\rightarrow\infty}\frac{\mathbb{V}(f(T_{k}))}{k}=0\quad\text{
and }\quad$
$\displaystyle\sum_{k=1}^{\infty}\frac{\mathbb{E}(f(T_{k}))^{2}}{k^{2}}<\infty,$

then for certain constants $\nu$ and $\sigma\geq 0$, we have

$\mathbb{E}(\mathcal{F}(T_{k}))\sim\nu k\text{ and
}\mathbb{V}(\mathcal{F}(T_{k}))\sim\sigma^{2}k.$

Moreover, if $\sigma\neq 0$, then

$\displaystyle\mathbb{P}(\mathcal{F}(T_{k})\leq\nu
k+\sigma\sqrt{k}x)\overset{k\to\infty}{\to}\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-t^{2}/2}\,dt$

for every real number $x$. In particular, we have

$\displaystyle\nu=\sum_{k=1}^{\infty}\frac{2}{k(k+1)}\mathbb{E}(f(T_{k})).$

Note that in [22], the equivalent binary search model is considered that
allows binary trees to have unary nodes, so that the index of summation has to
be shifted in the sum defining $\nu$. Moreover, note that if we set
$f(t)=\log_{2}(|t|-1)$ for $|t|>1$ and $f(t)=0$ otherwise, we have

$\displaystyle\mathcal{F}(t)=\sum_{v\in t}f(t(v))=\sum_{v\in
t\atop|t(v)|>1}\log_{2}(|t(v)|-1)=\log_{2}(P_{\operatorname{bst}}(t)^{-1}),$

by definition of $P_{\operatorname{bst}}$ in (3), and thus Theorem 6 follows
as a special case of Theorem 7. This special case is also considered in
Example 8.13 of [22].

As our main application of Theorem 7, we transfer the statement of Theorem 5
from uniformly random binary trees to random binary search trees, that is, we
show that if the random number
$A_{k}=\lvert\operatorname{\mathrm{Aut}}(T_{k})\rvert$ denotes the size of the
automorphism group of a random binary search tree $T_{k}$ with $k$ leaves,
then the logarithm of this random variable satisfies a central limit theorem
as well. For this, we define the function $f:\mathcal{T}\rightarrow\mathbb{R}$
in Theorem 7 by

$\displaystyle f(t)=\begin{cases}1\quad&\text{if the root of }t\text{ is a
symmetrical node,}\\\ 0\quad&\text{otherwise.}\end{cases}$

We thus have

$\displaystyle\mathcal{F}(t)=\sum_{v\in t}f(t(v))=\operatorname{sym}(t),$

that is, $\mathcal{F}(t)$ evaluates to the number of symmetrical nodes in $t$.
Recall that $2^{\operatorname{sym}(t)}$ equals the size of the automorphism
group $\operatorname{\mathrm{Aut}}(t)$ of $t$. It is not difficult to check
that $f$ satisfies the conditions of Theorem 7: As $f(t)\in\\{0,1\\}$ for
every $t\in\mathcal{T}$, we have
$\mathbb{E}(f(T_{k})^{2})=\mathbb{E}(f(T_{k}))\in[0,1]$ and thus
$\mathbb{V}(f(T_{k}))\in[0,1]$ as well, so that the assumptions of Theorem 7
are satisfied. In order to determine the corresponding value $\nu$, we start
with estimating the expectation $\mathbb{E}(f(T_{k}))$:

If $k$ is odd, then $\mathbb{E}(f(T_{k}))=0$, as the fringe subtrees rooted at
the root’s children cannot be of the same size in this case and thus cannot be
isomorphic. If $k$ is even, then $\mathbb{E}(f(T_{k}))$ equals the probability
that these two subtrees are of the same size $\frac{k}{2}$ (which is
$\frac{1}{k-1}$) times the probability that these two subtrees of size
$\frac{k}{2}$ are isomorphic.

In order to estimate the latter probability, let $P_{k}^{r}$ for positive
integers $k$ and $r$ denote the probability that $2^{r}$ random binary search
trees of size $k$ are isomorphic, and let $\delta(k)=1$ if $k$ is even and
$\delta(k)=0$ otherwise. We find that $P_{k}^{r}$ satisfies the following
recurrence relation:

$\displaystyle
P_{k}^{r}=\smashoperator[]{\sum_{i=1}^{\lfloor\frac{k-1}{2}\rfloor}}\Big{(}\frac{2}{k-1}\Big{)}^{\\!2^{r}}\\!P_{i}^{r}P_{k-i}^{r}+\delta(k)\Big{(}\frac{1}{k-1}\Big{)}^{\\!2^{r}}\\!\Big{(}2^{2^{r}-1}\big{(}P_{k/2}^{r}\big{)}^{2}\\!-\\!\Big{(}2^{2^{r}-1}-1\Big{)}P_{k/2}^{r+1}\Big{)},$

with $P_{k}^{r}=1$ for $k\in\\{1,2,3\\}$ and every positive integer $r$. To
see that this recurrence relation holds, first consider the case that $k$ is
odd: If all the $2^{r}$ trees are isomorphic, then the respective sizes of the
fringe subtrees rooted at the root nodes’ children must coincide, that is,
there are integers $i$ and $k-i$ with $1\leq
i\leq\lfloor\frac{k-1}{2}\rfloor$, such that for each of the $2^{r}$ trees,
one of those subtrees is of size $i$ while the other is of size $k-i$. This
holds with probability $(2/(k-1))^{2^{r}}$. Moreover, all of the $2^{r}$
subtrees of size $i$ (respectively, $k-i$) have to be isomorphic, which holds
with probability $P_{i}^{r}$ (respectively, $P_{k-i}^{r}$).

If $k$ is even, we furthermore have to consider the case that $i=\frac{k}{2}$,
which holds with probability $(1/(k-1))^{2^{r}}$: In this case pick the first
of the $2^{r}$ trees and let $t_{1}$ (respectively, $t_{2}$) denote the fringe
subtree of size $\frac{k}{2}$ rooted at the root node’s left (respectively,
right) child. For all of the other $2^{r}-1$ trees, one of the fringe subtrees
rooted at the root node’s children has to be isomorphic to $t_{1}$, while the
other has to be isomorphic to $t_{2}$: This holds with probability
$(P_{k/2}^{r})^{2}$. Moreover, for each of those $2^{r}-1$ many trees, we can
choose whether the subtree rooted at the root’s left child or right child is
isomorphic to $t_{1}$, which gives us $2^{2^{r}-1}$ many possibilities.
However, in the case that $t_{1}$ is isomorphic to $t_{2}$ as well (which
means that all the $2^{r+1}$ subtrees are isomorphic, which holds with
probability $P_{k/2}^{r+1}$), this means some overcounting, which is taken
into account by the final term. Thus, the recursion for $P_{k}^{r}$ follows.
We find for a random binary search tree $T_{k}$ of size $k$:

$\displaystyle\mathbb{E}(f(T_{k}))=\begin{cases}\frac{1}{k-1}P^{1}_{k/2}\quad&\text{if
}k\text{ is even,}\\\ 0\quad&\text{otherwise.}\end{cases}$

Thus, we have

$\displaystyle\nu=\sum_{k=1}^{\infty}\frac{2}{k(k+1)}\mathbb{E}(f(T_{k}))=\sum_{k=1}^{\infty}\frac{P_{k}^{1}}{k(2k+1)(2k-1)}\approx
0.3795493473,$

where the numerical value for $\nu$ can be determined using the recurrence
relation for $P_{k}^{r}$. We remark that the constant $\sigma^{2}$ can also be
evaluated numerically. It is approximately $0.115$, thus in particular not
$0$, but we do not need its precise value. The following theorem now follows
from Theorem 7:

###### Theorem 8

Consider a random binary search tree $T_{k}$ with $k$ leaves, and let
$A_{k}=\lvert\operatorname{\mathrm{Aut}}(T_{k})\rvert$ be the cardinality of
its automorphism group. The logarithm of this random variable satisfies a
central limit theorem: for certain positive constants $\nu$ and $\sigma_{3}$,
we have

$\displaystyle\mathbb{P}(A_{k}\leq 2^{\nu
k+\sigma_{3}\sqrt{k}x})\overset{k\to\infty}{\to}\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-t^{2}/2}\,dt$

for every real number $x$. The numerical value of $\nu$ is $\nu\approx
0.3795493473$.

###  4.1 Ordered Fringe Subtrees in Random Binary Search Trees

We are now able to prove Theorem 4:

######  Proof (Proof of Theorem 4)

_The upper bound:_ Let $k_{0}=\log_{4}n$. We upper-bound the number $J_{n}$ of
distinct fringe subtrees in a random binary search tree with $n$ leaves as
follows: The number of distinct fringe subtrees with fewer than $k_{0}$ leaves
is trivially bounded from above by the number of all binary trees of size at
most $k_{0}$ (irrespective of their occurrence as fringe subtrees), which is

$\displaystyle\sum_{k<k_{0}}C_{k-1}=O\left(\frac{4^{k_{0}}}{k_{0}^{3/2}}\right)=O\left(\frac{n}{(\ln
n)^{3/2}}\right).$

This upper bound holds deterministically. The number of distinct fringe
subtrees with at least $k_{0}$ leaves is upper-bounded by the total number of
fringe subtrees with at least $k_{0}$ leaves: For this, we apply Lemma 2 with
$a=\frac{1}{\ln 4}$, $\varepsilon<\frac{1}{3}$ and
$\mathcal{S}_{k}=\mathcal{T}_{k}$, so that $p_{k}=1$ for $k_{0}\leq k\leq
n^{\varepsilon}$. Thus, both in expectation and with high probability, as the
estimate from Lemma 2 (part (4)) holds with high probability simultaneously
for all $k$ in the given range, we obtain:

$\displaystyle\left(\sum_{k_{0}\leq k\leq
n^{\varepsilon}}X_{n,k}\right)+Y_{n,\varepsilon}$
$\displaystyle=\sum_{k_{0}\leq k\leq
n^{\varepsilon}}\frac{2n}{k(k+1)}(1+O(kn^{-1/2+\varepsilon}))+O(n^{1-\frac{\varepsilon}{2}})$
$\displaystyle=2\ln 4\cdot\frac{n}{\ln n}(1+o(1)).$

Hence, we find that $J_{n}$ is both in expectation and with high probability
bounded from above by

$\displaystyle J_{n}\leq\sum_{k<k_{0}}C_{k}+\left(\sum_{k_{0}\leq k\leq
n^{\varepsilon}}X_{n,k}\right)+Y_{n,\varepsilon}=2\ln 4\cdot\frac{n}{\ln
n}(1+o(1)).$

The numerical value of the constant is $c_{6}=2\ln(4)\approx 2.7725887222$.

_The lower bound:_ As a consequence of Theorem 6, the probability that
$P_{\operatorname{bst}}(T_{k})^{-1}\leq 2^{\mu k-k^{3/4}}$ for a random binary
search tree $T_{k}$ of size $k$ tends to $0$ for $k\rightarrow\infty$. Let
$\mathcal{S}_{k}$ denote the set of binary trees of size $k$ that do not
satisfy this inequality: Thus, every binary tree $t\in\mathcal{S}_{k}$
satisfies $P_{\operatorname{bst}}(t)\leq 2^{-\mu k+k^{3/4}}$ and we have
$p_{k}=1+o(1)$. In order to prove the lower bound, we only consider fringe
subtrees in $\mathcal{S}_{k}$ for suitable $k$: Thus, we can suitably upper-
bound the probability that two fringe subtrees of size $k$ in a random binary
search tree are identical. Let $\delta$ denote a positive constant with
$\delta<\frac{2}{3}$, let $k_{1}=(1+\delta)\mu^{-1}\log_{2}n$ and let
$k_{1}\leq k\leq n^{\delta/2}$. By Lemma 2, the number of such fringe subtrees
in a random binary search tree with $n$ leaves is $2np_{k}/(k(k+1))$ in
expectation and

$\displaystyle\frac{2np_{k}}{k(k+1)}(1+O(p_{k}^{-1/2}n^{(\delta-1)/2}k))$

with high probability. Furthermore, let $X^{(2)}_{n,k}$ denote the (random)
number of pairs of identical fringe subtrees among the fringe subtrees with
$k$ leaves that belong to $\mathcal{S}_{k}$, for $k_{1}\leq k\leq
n^{\delta/2}$. Let us condition on the event that $X_{n,k}=N$ for some
nonnegative integer $N\leq n$. Those $N$ fringe subtrees are all independent
random binary search trees, and the probability that such a fringe subtree
equals a given binary tree $t\in\mathcal{S}_{k}$ is
$P_{\operatorname{bst}}(t)/p_{k}$. Thus, we have

$\displaystyle\mathbb{E}(X_{n,k}^{(2)}\mid
X_{n,k}=N)=\binom{N}{2}\sum_{t\in\mathcal{S}_{k}}\left(\frac{P_{\operatorname{bst}}(t)}{p_{k}}\right)^{2}\leq\frac{n^{2}}{2}\frac{1}{p_{k}^{2}}\sum_{t\in\mathcal{S}_{k}}P_{\operatorname{bst}}(t)^{2}.$

As by assumption, $P_{\operatorname{bst}}(t)\leq 2^{-\mu k+k^{3/4}}$ for every
$t\in\mathcal{S}_{k}$, the expected value is upper-bounded by

$\displaystyle\mathbb{E}(X_{n,k}^{(2)}\mid
X_{n,k}=N)\leq\frac{n^{2}}{2}\frac{2^{-\mu
k+k^{3/4}}}{p_{k}^{2}}\sum_{t\in\mathcal{S}_{k}}P_{\operatorname{bst}}(t)=\frac{n^{2}}{p_{k}}2^{-\mu
k-1+k^{3/4}}.$

Since this upper bound for $\mathbb{E}(X_{n,k}^{(2)}\mid X_{n,k}=N)$ holds
independently of $N$, the law of total expectation yields

$\displaystyle\mathbb{E}(X_{n,k}^{(2)})=\sum_{N=0}^{n}\mathbb{E}(X_{n,k}^{(2)}\mid
X_{n,k}=N)\mathbb{P}(X_{n,k}=N)\leq\frac{n^{2}}{p_{k}}2^{-\mu k-1+k^{3/4}}.$

With $p_{k}=1+o(1)$, we obtain

$\displaystyle\mathbb{E}(X_{n,k}^{(2)})\leq n^{2}2^{-\mu
k-1+k^{3/4}}(1+o(1))=n^{2}2^{-\mu k+O(k^{3/4})}.$

As $k\geq k_{1}=\frac{1+\delta}{\mu}\log_{2}n$, we find

$\displaystyle\mathbb{E}(X_{n,k}^{(2)})\leq
n^{2}2^{-(1+\delta)\log_{2}n+O(k^{3/4})}\leq
n^{1-\delta}2^{O((\log_{2}n)^{3/4})}.$

Thus,

$\displaystyle\sum_{k_{1}\leq k\leq n^{\delta/2}}\mathbb{E}(X_{n,k}^{(2)})\leq
n^{1-\delta/2}2^{O((\log_{2}n)^{3/4})}=o(n/\ln n).$

The (random) number $J_{n}$ of distinct fringe subtrees in a random binary
search tree of size $n$ is lower-bounded by the number of distinct fringe
subtrees of sizes $k$ for $k_{1}\leq k\leq n^{\delta/2}$ that belong to
$\mathcal{S}_{k}$, and this number is again lower-bounded by the sum over
$X_{n,k}-X_{n,k}^{(2)}$ for $k_{1}\leq k\leq n^{\delta/2}$. We thus have

$\displaystyle J_{n}\geq\sum_{k_{1}\leq k\leq
n^{\delta/2}}X_{n,k}-\sum_{k_{1}\leq k\leq n^{\delta/2}}X_{n,k}^{(2)}.$

The second sum is $o(n/\ln n)$ in expectation and hence by Markov’s inequality
with high probability as well. The first sum can be estimated using Lemma 2,
as in the proof of the upper bound, which yields

$\displaystyle\sum_{k_{1}\leq k\leq n^{\delta/2}}X_{n,k}=\frac{2\mu\ln
2}{1+\delta}\cdot\frac{n}{\ln n}(1+o(1)),$

in expectation and with high probability. Since $\delta$ can be chosen
arbitrarily, the desired statement holds for any constant

$\displaystyle c_{5}<2\mu\ln 2\approx 2.4071298335.$

###  4.2 Unordered Fringe Subtrees in Random Binary Search Trees

It remains to prove Theorem 2:

######  Proof (Proof of Theorem 2)

_The upper bound_ : The proof for the upper bound exactly matches the first
part of the proof of Theorem 4, except that we choose the cut-point
$k_{0}=\log_{b}(n)$, where $b\approx 2.4832535362$ is the constant determining
the asymptotic growth of the Wedderburn-Etherington numbers.

_The lower bound_ : Let $T_{k}$ denote a random binary search tree with $k$
leaves. As a consequence of Theorem 8, the probability that
$\lvert\operatorname{\mathrm{Aut}}(T_{k})\rvert=A_{k}\leq 2^{\nu k-k^{3/4}}$
tends to $0$ as $k\rightarrow\infty$. Moreover, by Theorem 6 the probability
that $B_{k}=P_{\operatorname{bst}}(T_{k})^{-1}\leq 2^{\mu k-k^{3/4}}$ tends to
$0$ for $k\rightarrow\infty$. Let $\mathcal{S}_{k}$ denote the set of ordered
binary trees with $k$ leaves for which neither of the two inequalities is
satisfied: Thus, every binary tree $t\in\mathcal{S}_{k}$ satisfies
$P_{\operatorname{bst}}(t)\leq 2^{-\mu k+k^{3/4}}$ and
$\lvert\operatorname{\mathrm{Aut}}(t)\rvert\geq 2^{\nu k-k^{3/4}}$, and we
have $p_{k}=1+o(1)$. By the orbit-stabilizer theorem, we find that the number
of ordered binary trees in the same isomorphism class as a tree
$t\in\mathcal{S}_{k}$ is bounded from above by

$\displaystyle\frac{2^{k-1}}{\lvert\operatorname{\mathrm{Aut}}(t)\rvert}\leq\frac{2^{k-1}}{2^{\nu
k-k^{3/4}}}=2^{(1-\nu)k-1+k^{3/4}}.$

In order to prove the lower bound, we only consider fringe subtrees in
$\mathcal{S}_{k}$ for suitable $k$: Thus, we are able to suitably upper-bound
the probability that two fringe subtrees of size $k$ in a random binary search
tree are identical as unordered binary trees. Let $\delta<\frac{2}{3}$, let
$k_{1}=(1+\delta)\log_{2}n/(\mu+\nu-1)$ and let $k_{1}\leq k\leq
n^{\delta/2}$. By Lemma 2, the number of fringe subtrees of size $k$ with
$k_{1}\leq k\leq n^{\delta/2}$ is $2np_{k}/(k(k+1))$ in expectation and

$\displaystyle\frac{2np_{k}}{k(k+1)}(1+O(p_{k}^{-1/2}n^{(\delta-1)/2}k))$

with high probability. For $k_{1}\leq k\leq n^{\delta/2}$, let $X_{n,k}^{(2)}$
denote the (random) number of pairs of isomorphic binary trees among the
fringe subtrees of size $k$ that belong to $\mathcal{S}_{k}$. Moreover, let
$l$ denote the number of isomorphism classes of binary trees in
$\mathcal{S}_{k}$ and for each isomorphism class, pick one representative: Let
$t_{1},t_{2},\dots,t_{l}$ denote those representatives. If a binary tree $t$
is in the same isomorphism class as tree $t_{i}$, then
$P_{\operatorname{bst}}(t)=P_{\operatorname{bst}}(t_{i})$ and
$\lvert\operatorname{\mathrm{Aut}}(t)\rvert=\lvert\operatorname{\mathrm{Aut}}(t_{i})\rvert$.
In particular, if $t\in\mathcal{T}_{k}$ is isomorphic to a representative
$t_{i}$, then $t\in\mathcal{S}_{k}$ as well, that is, all binary trees that
are isomorphic to a binary tree in $\mathcal{S}_{k}$ are automatically
contained in $\mathcal{S}_{k}$ as well. As there are
$2^{k-1}/\lvert\operatorname{\mathrm{Aut}}t_{i}\rvert$ many trees in the same
isomorphism class as the binary tree $t_{i}$, we find

$\displaystyle\sum_{i=1}^{l}P_{\operatorname{bst}}(t_{i})\frac{2^{k-1}}{\lvert\operatorname{\mathrm{Aut}}t_{i}\rvert}=\sum_{t\in\mathcal{S}_{k}}P_{\operatorname{bst}}(t)=p_{k}.$

Let us condition on the event that $X_{n,k}=N$ for some integer $0\leq N\leq
n$. Those $N$ fringe subtrees are all independent random binary search trees,
and the probability that such a fringe subtree is isomorphic to a given binary
tree $t_{i}\in\mathcal{S}_{k}$ is
$(P_{\operatorname{bst}}(t_{i})/p_{k})\cdot(2^{k-1}/\lvert\operatorname{\mathrm{Aut}}(t_{i})\rvert)$.
Thus, we find

$\displaystyle\mathbb{E}(X_{n,k}^{(2)}\mid
X_{n,k}=N)\\!=\\!\binom{N}{2}\sum_{i=1}^{l}\left(\frac{2^{k-1}P_{\operatorname{bst}}(t_{i})}{\lvert\operatorname{\mathrm{Aut}}t_{i}\rvert
p_{k}}\right)^{2}\\!\leq\frac{n^{2}}{2}\frac{1}{p_{k}^{2}}\sum_{i=1}^{l}\left(\frac{2^{k-1}P_{\operatorname{bst}}(t_{i})}{\lvert\operatorname{\mathrm{Aut}}t_{i}\rvert}\right)^{2}\\!.$

As $t_{1},\dots,t_{l}\in\mathcal{S}_{k}$, we have
$P_{\operatorname{bst}}(t_{i})\leq 2^{-\mu k+k^{3/4}}$ and thus

$2^{k-1}/\lvert\operatorname{\mathrm{Aut}}t_{i}\rvert\leq
2^{(1-\nu)k-1+k^{3/4}}$

for every $i\in\\{1,2,\dots,l\\}$. Hence

$\displaystyle\mathbb{E}(X_{n,k}^{(2)}\mid X_{n,k}=N)$
$\displaystyle\leq\frac{n^{2}2^{(1-\nu-\mu)k+2k^{3/4}-2}}{p_{k}^{2}}\sum_{i=1}^{l}\left(\frac{2^{k-1}P_{\operatorname{bst}}(t_{i})}{\lvert\operatorname{\mathrm{Aut}}t_{i}\rvert}\right)$
$\displaystyle=p_{k}^{-1}n^{2}2^{(1-\nu-\mu)k+2k^{3/4}-2}.$

As this upper bound on the expectation is independent of $N$, we find by the
law of total expectation:

$\displaystyle\mathbb{E}(X_{n,k}^{(2)})\leq
p_{k}^{-1}n^{2}2^{(1-\nu-\mu)k+2k^{3/4}-2}=n^{2}2^{-(\nu+\mu-1)k+2k^{3/4}-2}(1+o(1)).$

With $k\geq k_{1}=(1+\delta)/(\mu+\nu-1)\log_{2}n$, we obtain

$\displaystyle\mathbb{E}(X_{n,k}^{(2)})\leq
n^{2}2^{-(1+\delta)\log_{2}n+O((\log_{2}n)^{3/4})}=n^{1-\delta}2^{O((\log_{2}n)^{3/4})}.$

Thus,

$\displaystyle\sum_{k_{1}\leq k\leq n^{\delta/2}}\mathbb{E}(X_{n,k}^{(2)})\leq
n^{1-\frac{\delta}{2}}2^{O((\log_{2}n)^{3/4})}=o(n/\ln n).$

Analogously as in the previous proofs, we lower-bound the random number
$G_{n}$ of non-isomorphic fringe subtrees in a random binary search tree of
size $n$ by the number of such fringe subtrees of sizes $k$ for $k_{1}\leq
k\leq n^{\delta/2}$ that belong to $\mathcal{S}_{k}$, and this number is again
lower-bounded by the sum over $X_{n,k}-X_{n,k}^{(2)}$ for $k_{1}\leq k\leq
n^{\delta/2}$ by the inclusion-exclusion principle. We thus have

$\displaystyle G_{n}\geq\sum_{k_{1}\leq k\leq
n^{\delta/2}}X_{n,k}-\sum_{k_{1}\leq k\leq n^{\delta/2}}X_{n,k}^{(2)}.$

The second sum is $o(n/\ln n)$ in expectation and hence by Markov’s inequality
with high probability as well. The first sum is bounded similarly as in the
estimate for the upper bound, which yields

$\displaystyle\sum_{k_{1}\leq k\leq n^{\delta/2}}X_{n,k}=\frac{2(\mu+\nu-1)\ln
2}{1+\delta}\cdot\frac{n}{\ln n}(1+o(1)).$

Since $\delta$ can again be chosen arbitrarily, the desired statement holds
for any constant $c_{3}<2(\mu+\nu-1)\ln 2\approx 1.5470025923.$
$\scriptstyle\blacksquare$

##  5 Open Problems

The following natural question arises from our results: Is it possible to
determine constants $\alpha_{1},\alpha_{2},\alpha_{3}$ with
$c_{1}\leq\alpha_{1}\leq c_{2}$, $c_{3}\leq\alpha_{2}\leq c_{4}$ and
$c_{5}\leq\alpha_{3}\leq c_{6}$, such that

$\displaystyle\mathbb{E}(F_{n})=\frac{\alpha_{1}n}{\sqrt{\log n}}(1+o(1)),\
\mathbb{E}(G_{n})=\frac{\alpha_{2}n}{\log n}(1+o(1)),\
\mathbb{E}(J_{n})=\frac{\alpha_{3}n}{\log n}(1+o(1)),$

respectively, and

$\displaystyle\frac{F_{n}}{n/\sqrt{\log n}}\overset{P}{\to}\alpha_{1},\
\frac{G_{n}}{n/\log n}\overset{P}{\to}\alpha_{2},\ \text{and}\
\frac{J_{n}}{n/\log n}\overset{P}{\to}\alpha_{3}\ ?$

In order to prove such estimates, it seems essential to gain a better
understanding of the random variables $P_{\operatorname{bst}}(T_{k})^{-1}$ and
$\lvert\operatorname{\mathrm{Aut}}(T_{k})\rvert$, in particular their
distributions further away from the mean values, for random binary search
trees or uniformly random ordered binary trees $T_{k}$ of size $k$.

## References

  * [1] Serge Abiteboul, Pierre Bourhis, and Victor Vianu.  Highly expressive query languages for unordered data trees.  Theory of Computing Systems, 57(4):927–966, 2015.
  * [2] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman.  Compilers: Principles, Techniques, and Tools.  Addison-Wesley series in computer science / World student series edition. Addison-Wesley, 1986.
  * [3] David Aldous.  Asymptotic fringe distributions for general families of random trees.  The Annals of Applied Probability, 1(2):228–266, 1991.
  * [4] Miklós Bóna and Philippe Flajolet.  Isomorphism and symmetries in random phylogenetic trees.  Journal of Applied Probability, 46(4):1005–1019, 2009.
  * [5] Iovka Boneva, Radu Ciucanu, and Slawek Staworko.  Schemas for unordered XML on a DIME.  Theory of Compuing Systems, 57(2):337–376, 2015.
  * [6] Mireille Bousquet-Mélou, Markus Lohrey, Sebastian Maneth, and Eric Noeth.  XML compression via DAGs.  Theory of Computing Systems, 57(4):1322–1371, 2015.
  * [7] Randal E. Bryant.  Symbolic boolean manipulation with ordered binary-decision diagrams.  ACM Computing Surveys, 24(3):293–318, 1992.
  * [8] Peter Buneman, Martin Grohe, and Christoph Koch.  Path queries on compressed XML.  In Johann Christoph Freytag et al., editors, Proceedings of the 29th Conference on Very Large Data Bases, VLDB 2003, pages 141–152. Morgan Kaufmann, 2003.
  * [9] Florian Dennert and Rudolf Grübel.  On the subtree size profile of binary search trees.  Combinatorics, Probability and Computing, 19(4):561–578, 2010.
  * [10] Luc Devroye.  On the richness of the collection of subtrees in random binary search trees.  Information Processing Letters, 65(4):195–199, 1998.
  * [11] Luc Devroye and Svante Janson.  Protected nodes and fringe subtrees in some random trees.  Electronic Communications in Probability, 19:1–10, 2014.
  * [12] Michael Drmota.  Random Trees: An Interplay Between Combinatorics and Probability.  Springer Publishing Company, Incorporated, 1st edition, 2009.
  * [13] Qunqiang Feng and Hosam M. Mahmoud.  On the variety of shapes on the fringe of a random recursive tree.  Journal of Applied Probability, 47(1):191–200, 2010.
  * [14] Qunqiang Feng, Hosam M. Mahmoud, and Alois Panholzer.  Phase changes in subtree varieties in random recursive and binary search trees.  SIAM Journal on Discrete Mathematics, 22(1):160–184, 2008.
  * [15] James Allen Fill.  On the distribution of binary search trees under the random permutation model.  Random Structures & Algorithms, 8(1):1–25, 1996.
  * [16] Steven R. Finch and Gian-Carlo Rota.  Mathematical Constants.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2003.
  * [17] Philippe Flajolet, Xavier Gourdon, and Conrado Martínez.  Patterns in random binary search trees.  Random Structures & Algorithms, 11(3):223–244, 1997.
  * [18] Philippe Flajolet and Robert Sedgewick.  Analytic Combinatorics.  Cambridge University Press, 2009.
  * [19] Philippe Flajolet, Paolo Sipala, and Jean-Marc Steyaert.  Analytic variations on the common subexpression problem.  In Proceedings of the 17th International Colloquium on Automata, Languages and Programming, ICALP 1990, volume 443 of Lecture Notes in Computer Science, pages 220–234. Springer, 1990.
  * [20] Markus Frick, Martin Grohe, and Christoph Koch.  Query evaluation on compressed trees (extended abstract).  In Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, LICS 2003, pages 188–197. IEEE Computer Society Press, 2003.
  * [21] Moses Ganardi, Danny Hucke, Markus Lohrey, and Louisa Seelbach Benkner.  Universal tree source coding using grammar-based compression.  IEEE Transactions on Information Theory, 65(10):6399–6413, 2019\.
  * [22] Cecilia Holmgren and Svante Janson.  Limit laws for functions of fringe trees for binary search trees and random recursive trees.  Electronic Journal of Probability, 20:1–51, 2015.
  * [23] John C. Kieffer, En-Hui Yang, and Wojciech Szpankowski.  Structural complexity of random binary trees.  In Proceedings of the 2009 IEEE International Symposium on Information Theory, ISIT 2009, pages 635–639. IEEE, 2009.
  * [24] Markus Lohrey, Sebastian Maneth, and Carl Philipp Reh.  Compression of unordered XML trees.  In 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, pages 18:1–18:17, 2017.
  * [25] Mike Paterson and Mark N. Wegman.  Linear unification.  Journal of Computer and System Sciences, 16(2):158–167, 1978.
  * [26] Dimbinaina Ralaivaosaona and Stephan G. Wagner.  Repeated fringe subtrees in random rooted trees.  In Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015, pages 78–88. SIAM, 2015.
  * [27] Louisa Seelbach Benkner and Markus Lohrey.  Average case analysis of leaf-centric binary tree sources.  In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, pages 16:1–16:15, 2018.
  * [28] Jie Zhang, En-Hui Yang, and John C. Kieffer.  A universal grammar-based code for lossless compression of binary trees.  IEEE Transactions on Information Theory, 60(3):1373–1386, 2014\.
  * [29] Sen Zhang, Zhihui Du, and Jason Tsong-Li Wang.  New techniques for mining frequent patterns in unordered trees.  IEEE Transactions on Cybernetics, 45(6):1113–1125, 2015.