Growing Binary Trees
January 01, 1970
Abstract
This paper introduces a new combinatorial framework for modeling the growth of binary trees through a discrete evolution process that incorporates a growing rule and an extinction rule. Building upon the theory of increasingly labeled structures and the analysis of polynomial iterates, we extend previous models of increasing trees with label repetitions by allowing growth branches to terminate. This mechanism enables a direct connection between dynamic evolutionary processes and classical unlabeled binary trees. We provide a combinatorial outlook for this model, linking our new approach to essential but traditionally complex parameters such as tree height, the maximum number of leaves at the deepest level (for a given tree size), and the overall tree profile. Our approach reveals structural links with Mandelbrot polynomials and coding theory. Furthermore, we leverage these structural insights to develop an efficient, iterative uniform random sampler for binary trees with a prescribed profile, achieving optimal complexity in both time and space and in random bit consumption.
1 Introduction↩︎
The combinatorial modeling of tree evolution serves as a fundamental framework for understanding the growth of discrete structures, bridging the gap between local recursive rules and global structural properties. Historically, a significant portion of the literature has been dedicated to labeled increasing trees, where nodes are integrated into a hierarchy according to specific temporal constraints. Early studies, such as the seminal work of Meir and Moon on recursive trees [@MM78], focused on the typical shape of structures generated by sequential addition. The analysis of functional equations for trees was formalized within the framework of species theory by Bergeron et al. [@BLL88] and the references therein. Later the combinatorics of increasing trees has been extensively studied in the paper [@BFS92]. Those structures comprise for example recursive trees, plane-oriented recursive trees, or binary increasing trees and have been studied through the lens of symbolic functional equations and differential equations. More recently, this research has been extended to include more complex labeling rules and structural synchronizations, notably through the study of increasing Schröder trees and strict monotonic trees [@BGN19; @BGMN22]. These models are particularly relevant in phylogenetics, where node labels encode the chronology of evolutionary branching, and exhibit deep connections to random graphs, such as the one-to-one correspondence between certain increasing Schröder trees and classical labeled graphs [@BGN22].
The mathematical genesis of these evolutionary models lies in the study of recursive processes where each new node is attached to an existing one according to a predefined rule. A seminal contribution to this area is the work of Flajolet and Odlyzko on iterates of polynomials [@FO84] itself extending the paper [@AS73]. Their analysis provided a robust framework for understanding the height and size of trees generated by iterative growth. This approach was then significantly extended in our previous work, On the number of increasing trees with label repetitions [@BGGW20], which explored discrete growth processes where multiple nodes can share the same label. These models, which involve synchronized branching events, typically lead to purely formal power series where the underlying increasing labeling is intrinsically tied to the structural growth.
In these previous frameworks, the growth process was essentially monotonic: the structures could only expand, and every leaf remained a potential site for further development. The present paper introduces a paradigm shift by adding an extinction (or death) rule to the evolution process. By allowing branches to terminate, we reconnect these dynamic growth models with classical unlabeled structures, specifically unlabeled binary trees. In this perspective, nodes are categorized into three types: internal nodes, active leaves (anchors), and dead leaves. This distinction allows us to consider essential but traditionally difficult-to-access parameters from a new perspective. By leveraging some symbolic substitution and the iterative dynamics of the resulting polynomials, we provide a combinatorial interpretation of the tree height, the maximum number of the deepest leaves (for a fixed tree size), and the tree profile (the number of leaves at each level). Finally, we leverage these structural insights to design a uniform random sampler for binary tree respecting a given profile, that is optimal in terms of time and space complexity, and random bits consumption.
The paper is organized as follows. In Section 2, we formally define the growth process under consideration and describe the specific tree families and parameters that arise from this framework. Section 3 focuses on the “bushy” trees (those with a maximum number of leaves at the maximum depth for a given tree size), analyzing their behavior as the overall tree size increases. In this context, we establish structural links to meta-Fibonacci sequences and coding theory. In Section 4, we provide a comprehensive outlook on the growth dynamics of binary trees with respect to their height. Finally, leveraging our study of leaf distribution, Section 5 explores the algorithmic implications of this model, specifically focusing on the uniform random sampling of binary trees satisfying a prescribed profile.
2 Combinatorial modeling of a growth process↩︎
2.1 Growth process↩︎
In our research, we focus on the specific family of binary trees whose nodes are of the following three types: internal nodes (\(\bullet\)), active leaves or anchors (\(\circ\)), and dead leaves or simply leaves (\(\square\)). Each tree is generated by the growth process proceeding as follows.
In the beginning (at the moment \(t=0\)), the tree is reduced to an anchor (\(\circ\)).
At every moment \(t\in\mathbb{Z}_{>0}\), we replace each anchor with a (dead) leaf (\(\square\)) or a subtree consisting of an internal node with two anchors attached as children ().
We refer to a tree obtained after several steps of the growth process as a growing binary tree. Note, that the internal nodes always have two children in our model. Such trees are sometimes called locally complete binary trees.
From the construction, it is seen that the anchors appear exclusively on the last level. An example of a growing binary tree is shown in Figure 1 a) at moment \(t=5\).
2.2 The set of growing binary trees↩︎
Let us denote by \(t_{n,m}\) the total number of growing binary trees with \(n\) internal nodes and \(m\) anchors. From the description of the growth process, it is clear that the number of anchors of a tree is even with the exception of the initial tree. Thus, \(t_{n,2k-1}=0\) for all positive integers \(n\) and \(k\). The first values of \(t_{n,2k}\) are shown in Table [tab:t95n442k].
\(\begin{array}{c|cccccccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline t_{n,2} & 1 & 2 & 4 & 12 & 32 & 104 & 328 & 1\,080 & 3\,648 & 12\,544 & 43\,600 & 153\,504 & 546\,272 & 1\,960\,368 \\ t_{n,4} & 0 & 0 & 1 & 2 & 10 & 24 & 92 & 308 & 1\,028 & 3\,584 & 12\,736 & 45\,160 & 161\,152 & 581\,632 \\ t_{n,6} & 0 & 0 & 0 & 0 & 0 & 4 & 8 & 40 & 176 & 584 & 2\,144 & 8\,192 & 30\,720 & 112\,496 \\ t_{n,8} & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 10 & 84 & 282 & 1\,048 & 4\,368 & 18\,224 \\ t_{n,10} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 24 & 104 & 352 & 1\,616 \\ t_{n,12} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 36 & 96 \\ t_{n,14} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 8 \\ \end{array}\)
Note that there is no need to additionally count the number of (dead) leaves \(\ell\), since it is completely determined by two other parameters: if \(m\) and \(n\) are, respectively, the numbers of anchors and internal nodes in a growing binary tree, then \(\ell = n - m + 1\). Indeed, this relation holds for the initial tree, and the value \(n-m-\ell\) is invariant under replacements of the growth process.
Let us further denote by \[T(x,z) := x + \sum\limits_{n=0}^{\infty} \sum\limits_{k=1}^{\infty} t_{n,2k}x^{2k}z^n\] the generating function of active growing binary trees, that is, trees with at least one anchor. Here, the marking variables \(x\) and \(z\) count the anchors and internal nodes, respectively. The series \(T(x,z)\) satisfies the following relation: \[\label{eq:initial95gf95relation} T(x,z) = x + T(1+zx^2, z) - T(1,z) \, .\tag{1}\] Indeed, replacing an anchor with a leaf corresponds symbolically to the substitution \(x\mapsto1\), while a replacement with a subtree is represented by the substitution \(x\mapsto zx^2\). Note that we have to deduce the term \(T(1,z)\) in order to eliminate trees without anchors. By substituting \(x\) with the generating function \(C(z)\) of Catalan numbers and taking into account that \(C(z)=1+zC(z)^2\), we conclude that \[T(1,z) = C(z) \, , \qquadwhere\quad C(z) = \dfrac{1-\sqrt{1-4z}}{2z} \, .\] Combinatorially, this fact confirms that the growing binary trees without anchors are indeed all binary trees counted by the series \(C(z)\). In particular, the column sums in Table [tab:t95n442k] are Catalan numbers: \[\sum\limits_{m=1}^{n+1} t_{n,m} = C_n \, .\]
Another immediate consequence of Relation 1 is the following recurrent formula for \(t_{n,2k}\): \[\label{eq:initial95recurrence} t_{1,2} = 1 \, , \qquad\quad t_{n,2k} = \sum\limits_{m=1}^{\infty} \binom{2m}{k} t_{n-k,2m} \quad\,\, forn>k\geqslant 1 \, .\tag{2}\] Relation 2 also has a combinatorial explanation: to get a tree with \(n\) internal nodes and \(2k\) anchors, we have to replace \(k\) anchors of the tree obtained in the previous step of the growth process with an internal node with two children; the other anchors become leaves. The binomial coefficient \(\binom{2m}{k}\) then represents the number of choices of \(k\) anchors to be replaced.
2.3 Cumulative anchor counting↩︎
To enumerate the total number of leaves in active growing binary trees, we use the series \(\tilde{T}(1,z)\), where \[\tilde{T}(x,z) := \dfrac{\partial}{\partial x}T(x,z) = 1 + \sum\limits_{n=0}^{\infty} \sum\limits_{k=1}^{\infty} 2kt_{n,2k}x^{2k-1}z^n \, .\] By differentiating Relation 1 with respect to \(x\), we obtain the following relation for \(\tilde{T}(x,z)\): \[\label{eq:tilde40T4195relation} \tilde{T}(x,z) = 1 + 2xz\tilde{T}(1+zx^2, z) \, .\tag{3}\] This relation allows us to express the series \(\tilde{T}(x,z)\) in terms of polynomials \(p_h(x,z)\) that count all growing binary trees that can be obtained after the first \(h\) steps of the growing process. In fact, the polynomials \(p_h(x,z)\) are determined by the following recurrence relation: \[\label{eq:p95h40x44z41} p_0(x,z) = x \, , \qquad\quad p_{h+1}(x,z) = p_h(1+zx^2,z)\quad\,\, forh\geqslant 0 \, .\tag{4}\] Therefore, taking into account that \(1+zx^2=p_1(x,z)\), we can iterate Relation 3 according to 4 . By passing to the limit, this gives us the following expression: \[\tilde{T}(x,z) = 1 + \sum\limits_{i=1}^{\infty} (2z)^i \prod\limits_{j=0}^{i-1}p_j(x,z) \, .\] Note that the polynomials \(p_h(x,z)\) are related to the so-called (shifted) Mandelbrot polynomials [@CCC21]: \[M_h(z) = z\, q_h(1,z) \, .\] From a combinatorial point of view, Mandelbrot polynomials count growing binary trees with an additional internal node attached to the root; see Figure 1 b). By substituting \(x=1\) into the relation for \(\tilde{T}(x,z)\), we obtain an expression for \(\tilde{T}(1,z)\) in terms of Mandelbrot polynomials: \[\tilde{T}(1,z) = 1 + \sum\limits_{i=1}^{\infty} 2^i \prod\limits_{j=0}^{i-1}M_j(z) \, .\]
Remark 1. The formal link to Mandelbrot polynomials highlights a phase transition in the tree growth. The discrete dynamic of the iterates \(p_h(1,z)\) has fixed points satisfying \(x = 1 + zx^2\), which results in a critical bifurcation at \(z_c = 1/4\). For \(|z| < 1/4\), the process contracts towards the Catalan generating function \(C(z)\) (almost-sure extinction), whereas for \(z > 1/4\), it diverges (explosive growth). Consequently, the analyticity domain of the process is intrinsically bounded by the main cardioid of the Mandelbrot set.
3 Maximal number of anchors for a given tree size↩︎
Let us turn our focus to the columns of Table [tab:t95n442k]. We can see that in every column the number of nonzero elements is finite. For the \(n\)th column, we denote this number \(a_n\). In other words, \[a_n = \max\{k \colon t_{n,2k}>0\} \, .\] The first several values of the sequence \((a_n)_{n\geqslant 1}\) are \[(a_n)_{n\geqslant 1} = 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, \ldots\]
The purpose of this section is to provide a description of the sequence \((a_n)_{n\geqslant 1}\) and to show that this sequence is actually A006949 from [@oeis]. First, we show that \((a_n)_{n\geqslant 1}\) can be defined independently of growing binary trees.
Lemma 1. The sequence \((a_n)_{n\geqslant 1}\) satisfies the following recurrent relation: \[a_1 = 1 \, , \qquad\quad a_n = \max\{k\colon k \leqslant 2a_{n-k}\} \quad\,\, forn>1 \, .\]
Proof. Using the sequence \((a_n)_{n\geqslant 1}\), Relation 2 can be rewritten as \[t_{n,2k} = \sum\limits_{m=\lceil k/2\rceil}^{a_{n-k}} \binom{2m}{k} t_{n-k,2m} \, .\] Hence, the condition \(t_{n,2k} \neq 0\) means that there exists a positive integer \(m\) such that \(k \leqslant 2m \leqslant 2a_{n-k}\), which is equivalent to the condition \(k \leqslant 2a_{n-k}\). ◻
From Lemma 1, it follows by induction that the sequence \((a_n)_{n\geqslant 1}\) is increasing in the sense that, for any \(n\in\mathbb{Z}_{>0}\), we have \(a_{n+1} = a_n\) or \(a_{n+1} = a_n+1\). This fact, coupled with the initial condition \(a_1=1\), means that the behavior of the sequence \((a_n)_{n\geqslant 1}\) is completely determined by the number of repetitions: \[a_n = \max\left\{k \colon\, \sum\limits_{i=1}^{k} b_k \geqslant n\right\} \, ,\] where \(b_n\) is the number of elements in \((a_n)_{n\geqslant 1}\) that are equal to \(n\): \[b_n = \#\{k \colon a_k=n\} \, .\] The first several values of the sequence \((b_n)_{n\geqslant 1}\) are \[(b_n)_{n\geqslant 1} = 2, 3, 1, 4, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, \ldots\]
Proposition 2. The sequence \((b_n)_{n\geqslant 1}\) satisfies the following relation: \[b_n = \left\{\begin{array}{ll} p+2\quad & ifn=2^p, \\ p+1\quad & ifn=2^pa,\,\, a is odd,\,\, a>1\, . \\ \end{array}\right.\] In particular, we have \(b_{2n}=b_n+1\) for even indices, \(b_{2n+1}=1\) for odd indices greater than \(1\), and \(b_1=2\).
Proposition 2 allows us to claim that \((a_n)_{n\geqslant 1}\), with an additional value \(a_0=1\), coincides with the entry A006949 from oeis [@oeis] and is known as a meta-Fibonacci
sequence (for the sequence \((b_n)_{n\geqslant 1}\), see the entries A135560 and A241235). In particular, due
to [@T92] and [@RD09], we obtain the following properties of this sequence.
Corollary 1. The sequence \((a_n)_{n\geqslant 1}\) satisfies the following recurrent relation: \[a_0 = a_1 = a_2 = 1 \, , \qquad\quad a_n = a_{n-1-a_{n-1}} + a_{n-2-a_{n-2}} \quad\,\, forn>2 \, .\] Its generating function and asymptotic behavior satisfy, respectively, \[\sum\limits_{n=0}^{\infty} a_n z^n = z\sum\limits_{n=0}^{\infty} \prod\limits_{i=1}^{n} (z + z^{2^i}) \qquadand\qquad \lim\limits_{n\to\infty}\dfrac{a_n}{n} = \dfrac{1}{2} \, .\]
Note that the sequence \((a_n)_{n\geqslant 1}\) also admits another combinatorial interpretation in terms of infinite binary trees [@RD09; @D11] and is related to extremal compact codes [@JR06].
4 Growing binary trees of fixed height↩︎
In this section, we study the behavior of growing binary trees with respect to their heights.
Lemma 2. For any active growing binary tree, the number \(n\) of its internal nodes, the number \(2k\) of its anchors, and its height \(h\) satisfy \[h \leqslant n - k + 1 \leqslant 2^{h-1} \, .\] Both inequalities are sharp.
Let us denote by \(t_{n,m,h}\) the number of active growing binary trees of height \(h\) with \(n\) internal nodes and \(m\) anchors. Clearly, apart from the case \(h=0\), the number of anchors in a tree of height \(h\) is even. For example, for \(h=4\), the values of \(t_{n,2k,h}\) are shown in Figure 2.
Given a positive integer \(h\), we also introduce the domain \(S_h\) of nonzero values of \(t_{n,2k,h}\): \[\label{eq:nonzero95domain95S95h} S_h = \{(n,k)\colon t_{n,2k,h} \neq 0\} \, .\tag{5}\] From Lemma 2, it follows that \(S_h\) is finite. The following results describe its behavior.
Proposition 3. The right boundary \(\Gamma_h\) of the nonzero domain \(S_h\) (blue cells in Figure 2) satisfies \[\label{eq:Gamma95h95exact95form} \Gamma_h = \{(2^{h-1}-1+i,i)\colon 1\leqslant i \leqslant 2^{h-1}\} \, .\tag{6}\] In particular, all elements of \(\Gamma_h\) belong to the line \(n-k = 2^{h-1}-1\).
Proposition 4. The upper boundary \(\Lambda_h\) of the nonzero domain \(S_h\) (red cells in Figure 2) satisfies \[\label{eq:Lambda95h95exact95form} \Lambda_h = \{ (h,\hat{a}_2), (h+1,\hat{a}_3), \ldots, (2^{h}-2,\hat{a}_{2^h-h}), (2^{h}-1,\hat{a}_{2^h-h+1}) \} \, ,\tag{7}\] where \[\hat{a}_n = \max\left\{k \colon\, \sum\limits_{i=1}^{k} \hat{b}_k \geqslant n\right\},\] and \(\hat{b}_n\) is the ruler function, that is, the number of times \(2n\) can be divided by two.
Corollary 2. The area of the nonzero domain \(S_h\) is equal to \(2^{h-2}(2^{h-1}-h+2)\).
Proposition 5. The scaling limit of the nonzero domain \(S_h\) (normalized by \(2^{h-1}\)), as \(h\to\infty\), is the triangle with vertices \((0,0)\), \((1,0)\), and \((2,1)\).
5 Random sampling↩︎
5.1 Combinatorial context↩︎
We are focusing on binary trees, where the atoms under consideration are the leaves. An analogous approach can be applied to binary trees according to their number of internal nodes.
Definition 1. The level of a node in a binary tree is the distance (in terms of traversed edges) from the root to that node. The root is at level \(0\).
Definition 2. The profile of a binary tree is the sequence \((\ell_0, \ell_1, \ldots, \ell_h)\) of the nonnegative numbers of leaves at each level. The index \(h\) corresponds to the height of the tree. The size of the tree (i.e. the total number of leaves it contains) is equal to the sum \(\sum_i \ell_i\).
For a tree reduced to a single leaf (the root), we get the profile \((1)\). For any other binary tree with height \(h > 0\), we have \(\ell_0 = 0\) (the root is not a leaf).
Fact 6 (Kraft-McMillan equality). There exists a binary tree with profile \((\ell_0, \ell_1, \ldots, \ell_h)\) if and only if \[\sum_{i=0}^h \frac{\ell_i}{2^{i}} = 1.\]
This is a classical result in the context of code theory; see, for instance, [@CT06].
Proposition 7. Let \(h\) be a positive integer and \(T\) be a binary tree with profile \((\ell_0, \ell_1, \ldots, \ell_h)\). Its internal node profile (i.e. the sequence of the number of internal nodes at each level) is given by \((i_0 , i_1, \ldots, i_{h-1})\) satisfying \[\begin{cases} i_0 = 1 \\ i_k = 2i_{k-1} - \ell_k, \quad \text{for } 1 \leqslant k \leqslant h-1. \end{cases}\]
Definition 3. We say that a profile \((\ell_0, \ell_1, \ldots, \ell_h)\) is valid if there exists at least one binary tree having this profile.
Proposition 8. There exists a unique binary tree, which is reduced to a single leaf, having the profile \((1)\). Let \((\ell_0, \ell_1, \ldots, \ell_h)\), with \(h\geqslant 1\), be a valid profile. The number of binary trees having this profile is \[\prod_{k=0}^{h-1} \binom{2i_{k}}{\ell_{k+1}},\] where the sequence \((i_k)_{k=0\dots h-1}\) is defined in Proposition 7.
5.2 Uniform random sampling of trees with a given profile↩︎
A natural way to sample binary trees with a given profile is the following. Start with the root of the tree; if the latter is a leaf, then stop; otherwise, we have to decide what are the valid profiles of the two children. In the classical recursive method [@NW75; @FZVC94], even for sampling trees of a given size, the necessary computations are heavy. In our case, the combinatorial complexity is much higher, since we have to consider the profiles of the two subtrees, which are not independent (like in the case of size) but are also constrained to be valid profiles. In the context of binary decision diagram sampling [@CG20], such a top-down approach has been addressed to generate structures with a given profile, but it has finally been overtaken by an iterative approach [@CG23], level by level, only focusing on a given level at a time without the need to consider the rest of the profile.
Here in the context of binary trees, such an iterative approach can be developed as well (and will be more efficient than the one for decision diagrams), but an even more efficient approach is possible, looking to the tree from the bottom to the top (and for a given level, from left to right).
We can sample a binary tree with a given profile by starting from the last level, and then iteratively going up to the root, level by level, and for each level. In fact, in Proposition 8, we can look to the product formula counting the trees with a given profile from the last factor to the first ones, i.e. from the deepest levels of the trees to the root level.
The shuffling operation is presented in detail in Algorithm 3 from [@BDGP17].
Proposition 9. Algorithm 3 is correct and optimal in time, space, and random bit consumption.
Optimality stands for the time complexity, for the space complexity, and for the consumption of random bits (whose derivation comes from Proposition 8 and the shuffling operation from [@BDGP17]).
6 Perspectives↩︎
As a primary perspective, the connection between Mandelbrot polynomials and the framework of Flajolet and Odlyzko [@FO82] allows for a precise characterization of the limit distribution of the deepest leaves. This approach provides a new way to analyze the tree’s boundary and could be generalized to other substitution rules, offering a unified combinatorial view of extinction-based growth processes.
Algorithmically, the iterative bottom-up sampling introduced in Section 5 can be broadly extended. Natural next steps include the uniform generation of binary forests and the sampling of trees with partial profiles (e.g., profiles with "holes" representing intermediate levels of arbitrary sizes).
6.0.0.1 Acknowledgments
This work is partially funded by anr-fwf project PAnDAG ANR-23-CE48-0014 and anr project COMETA-GAE ANR-25-CE48-0602.