Enumeration of Ordered Trees with Leaf Restrictions

It is our pleasure to dedicate this work to Roberto Grossi, whose broad enthusiasm for algorithms and data structure has significantly shaped the landscape of enumeration algorithms [9]. Over the past decades, his contributions made significant impact on structural and algorithmic aspects of trees, strings, and graphs, inspiring both theoretical advances and practical applications.

In this spirit, we turn our attention to the enumeration of ordered trees, a topic rooted in combinatorics with strong connections to data structures, formal languages, and algorithmic analysis. Ordered trees play a fundamental role in various domains, hierarchical data representations, and the analysis of recursive algorithms are major examples. Enumerating ordered trees uncovers rich combinatorial patterns, with which we hope to offer a tiny tribute to Roberto’s enduring influence, exploring a topic in line with his passion for enumerating combinatorial structures of mathematical beauty.

We here tackle a problem whose restricted version on binary trees has been posed in 2023 as an open problem presented at IWOCA 2023: The question is to efficiently enumerate all rooted full binary trees whose number of leaves at each depth is given as an input. This problem spawned from the research of prefix-free codes in coding theory.

Here, we tackle this enumeration problem in even more general settings: binary (not necessarily full) trees and $\alpha$-ary trees of a fixed depth $d$ for a constant $\alpha \ge 2$. For any of these tree types, our algorithm outputs the first solution in $O(d+n)$ time. Subsequently, it outputs the difference between two successive solutions in $O(m)$ time with constant delay, where $n$ is the number of leaves and $m$ is the maximum number of leaves at any depth. We here define delay as the time between the end of the previous output and the start of the subsequent output.

With respect to the enumeration of rooted ordered trees, we are aware of an algorithm with constant delay to output all trees [3], or with restrictions on a specific diameter [12] or on a fixed number of internal nodes and leaves [17]. Given the number $m$ of internal nodes, Zaks [18] gave an enumeration algorithm for all $\alpha$-ary trees having $m$ internal nodes. This algorithm reports the trees in a lexicographical order based on a bit encoding of the trees. Recently, an algorithm [5] enumerating AVL trees has been proposed. In addition, closed formulas have been studied for counting various properties in rooted ordered trees of unbounded degree [6, 7].

For the enumeration of full binary trees with $n$ leaves, we propose a $2n$-bit encoding of a full binary tree. We use this encoding in the same way as Ruskey and Proskurowski [13] for the enumeration of binary trees by using Gray codes for enumerating bit encodings. Another bit encoding variant has been proposed by Baba et al. [1], who however used a depth-first encoding based on DFUDS [2], while our encoding is level-wise in the spirit of LOUDS [10].

Given a fixed integer $\alpha \ge 2$, an $\alpha$-ary tree is an ordered rooted tree whose nodes each have at most $\alpha$ children, which are ordered. In this paper, we only consider trees that have at least two nodes. Except for the root, the parent of each node is uniquely determined. There is a left-to-right ordering of the child nodes with respect to the parent. A node is called a leaf if it has no child, otherwise it is called an internal node. For a given rooted tree and a node $v$, the number of edges from the root to $v$ is called the depth of $v$, which we denote by $\text{depth}(v)$. In particular, the depth of the root is zero. The height of the tree is the depth of the leaf with the largest depth. A full $\alpha$-ary tree is an $\alpha$-ary tree whose nodes are either leaves or internal nodes with $\alpha$ children. A special case is $\alpha =2$, for which we name a $2$-ary tree a binary tree.

In what follows, we start with the enumeration of full binary trees, which is the easiest case. Then we extend our techniques to arbitrary binary trees, and finally consider $\alpha$-ary trees.

Our input is a so-called binary (tree leaf) distribution, a term coined by Buro [4, Lemma 2.3]. It is defined as follows. We call an integer vector $𝒘=(w_1,\mathrm{\dots },w_d)$ a binary distribution if there is a binary tree $T$ with depth $d$ such that $T$ has $w_i$ leaves with depth $i$ for every $i\in [1..d]$. We say that the binary (tree leaf) distribution of $T$ is $𝒘$ – there can be many trees that have the same binary distribution. A binary distribution is also called a full-binary distribution if there is a full binary tree with the same property. Buro [4, Thm. 2.4] showed that the full-binary distribution of a full binary tree with maximum path length is unique. Here we study the connection of arbitrary binary distributions and their corresponding trees. In detail, the first problem we want to tackle in this paper is as follows.

We first characterize the necessary conditions for an integer vector to be a (full) binary distribution. For that, we make use of Kraft’s inequality [11].

Let $f(𝒘)={\sum }_{i=1}^d{w}_i/2^i$ be the weight of a vector $𝒘$ of nonnegative integers. Then $f(𝒘)\le 1$ is a necessary condition according to Kraft’s inequality. We show that it is also sufficient.

In what follows, we present an enumeration algorithm for Problem 1 in the case of full binary trees. Our main idea is to process the trees in a linear order, which we define by a binary encoding of the trees.

For that, we recall the result of Corollary 5 that $g(i,𝒘)$ gives the number of nodes with depth $i\in [1..d]$, which is common to all full binary trees having the full-binary distribution $𝒘$. In short, we define the vector $𝜼=({\eta }_1,\mathrm{\dots },{\eta }_d)$ with ${\eta }_i:=g(i,𝒘)$ for $i\in [1..d]$. Then ${\sum }_{i=1}^d{\eta }_i$ is the number of all nodes. In particular, we can use an ${\eta }_i$-length bit vector to specify which nodes on depth $i$ are internal nodes or leaves. The list of bit vectors on all depths is sufficient to represent a full binary tree. Then ${\sum }_{i=1}^d{\eta }_i={\sum }_{i=1}^d{\sum }_{j=i}^d\frac{w_j}{2^{j-i}}\le 2{\sum }_{i=1}^d{w}_i$. For $n={\sum }_{i=1}^d{w}_i$, this means that we can represent each full binary tree whose full-binary distribution is $𝒘$ in $2n$ bits. We use this bit representation to enumerate these trees. For that, we build on the algorithm of [14].

The connection to our problem is that a bit vector of length $n$ with $m$ “1”s exactly represents such a subset. Since we can impose the natural lexicographic order on the $2n$-length bit vectors, the missing step is to find, given a $2n$-length bit vector representing a full binary tree, the lexicographic succeeding bit vector that represents a tree we want to output.

To facilitate our starting, we assume that $w_i\ge 1$ for every $i\in [1..d]$. Suppose that we have a full-binary tree $T$ whose distribution is $𝒘$. We deduce from $T$ a bit vector ${𝑩}_T$ representing $T$. For explanation, we assume that the least significant bits are on the left. We start with a bit vector ${𝑩}_T$ of length ${\sum }_{i=1}^d{\eta }_i\le 2n$ to represent the order of the internal nodes and leaves on each depth. To do this, we partition ${𝑩}_T$ by depths ${𝑩}_T=({𝒃}^{(1)}\mathrm{\cdots }{𝒃}^{(d)})$ such that ${𝒃}^{(i)}$ is a bit vector of length ${\eta }_i$ with $b_j^{(i)}=1$ if and only if the $j$-th node with depth $i$ is a leaf. In particular, ${𝒃}^{(i)}$ has $w_i$ zeros. As an example, the values of $𝑩$ for the trees depicted in Figure 1 are 001111 (left), 1011 (middle), and 0111 (right). (Recall that ${𝑩}_T$ does not encode the root node, for which we assume it is always an internal node.) As a practical optimization, we can omit the highest depth $d$ since it always contains leaves, i.e., ${𝒃}^{(d)}$ contains only zeros. Since we can reconstruct $T$ from ${𝑩}_T$ uniquely, there is a one-to-one mapping from full binary trees with at least two nodes and a subset of bit strings defined by the above tree encoding. Consequently, each full binary tree has exactly one specific bit vector representation.

In what follows, we represent each full binary tree $T$ having the distribution $𝒘$ with the bit vector ${𝑩}_T$, which is stored as a node in a so-called enumeration tree $E$. The root of $E$ represents the full binary tree $T$ obtained by grouping all internal nodes to the left side, which we expressed by the lexicographic least bit vector, obtained by shifting all “1”s in every ${𝒃}^{(i)}$ of ${𝑩}_T$ to the left. An $E$-node is augmented by a bit vector ${𝑩}_T$ representing a full binary tree $T$ and an integer, which we call the change level. The change level of an $E$-node $v$ states the depth at which the bit vector of $v$ differs from its parent; as an exception, we stipulate that the change level of the root node is 0. The change level is an invariant we impose on $E$ in the sense that, when traversing from a node $u$ to of its children $v$, the tree represented by $u$ and by $v$ can and must differ only at the change level of $v$. A consequence is that $E$-nodes with change level $d$ are leaves.

We organize the children of an $E$-node as follows. Fix one $E$-node $v$ with bit vector ${𝑩}_T=({𝒃}^{(1)}\mathrm{\cdots }{𝒃}^{(d)})$ and change level $\delta \in [0..d-1]$. Then the children of $v$ correspond to all possible rearrangements of the bit patterns in one of the vectors ${𝒃}^{(\delta +1)},\mathrm{\dots },{𝒃}^{(d)}$. We start with the first children of $v$ that enumerate all possible bit patterns of ${𝒃}^{(d)}$ (resulting by permutations). So they have change level $d$ with a bit vector that differs from $v$’s bit vector only at depth $d$. (In particular, these nodes are leaves by the definition of the change level.) Next, we continue with the group of children for ${𝒃}^{(d-1)}$ and change level $d-1$, and so on, up until ${𝒃}^{(\delta +1)}$ and change level $\delta +1$. In particular, we arrange each group of children with the same change level $i$ in lexicographic order of their corresponding bit vector ${𝒃}^{(i)}$. This order of the children and the order of their groups allows us to enumerate all full binary trees by a pre-order traversal of $E$ in lexicographic order. (In particular, the lexicographic order imposes the invariant that we never enumerate a full binary tree twice.) This structure of $E$ warrants the following – see Figure 2 for an example and Figure 3 for a more elaborated example involving a non-binary choice at one level:

• $\mathrm{■}$

  Any subtree rooted at a node of $E$ is an enumeration tree itself. That is because an $E$-node with change level $\delta \in [1..d]$ representing a tree $T$ is the root node of an enumeration tree that considers only the suffix ${𝒃}^{(\delta +1)}\mathrm{\cdots }{𝒃}^{(d)}$ of ${𝑩}_T$ for the enumeration. In detail, for an $E$-node with change level $\delta$ it holds that ${𝒃}^{(i)}=(\stackrel{w_i}{\overbrace{1\mathrm{\cdots }1}}\stackrel{{\eta }_i-w_i}{\overbrace{0\mathrm{\cdots }0}})$ for every $i\in [\delta +1..d-1]$ by the construction $E$ – recall that a node with change level $\delta$ only makes a change on ${𝒃}^{(\delta +1)}$ compared to its parent node, and reading the change levels upwards to the root gives a monotone decreasing sequence of change levels (so there is no way that any deeper level has changed with respect to the initial bit vector of the root.) In particular, an $E$-node is the lexicographically least among all its descendants.

• $\mathrm{■}$

  Since deeper recursion levels only touch shorter suffixes of the bit vectors, the rightmost leaf of an $E$-node $v$ is lexicographically smaller than $v$’s right sibling (if it exists). Therefore, all $E$-nodes represent different vectors, and the sum of all $E$-nodes is the size of the output we want to compute.

If we now run the algorithm of Lemma 8 on $d$ nested loops we can traverse the constructed enumeration tree $E$ in a pre-order traversal and output each node upon visiting it. The maximum delay happens when moving to the next value in the lowest $d-1$ loops. This delay is $O(d)$, but $O(1)$ amortized because to reach a depth of $d^{\prime }$ we have already output $d^{\prime }$ nodes.

It is left to argue that we can transform the sequence of outputted $E$-nodes into the full binary trees we want to output. For that, we initially build the full binary tree represented by the root of $E$ from scratch, taking $O(n)$ time. Subsequently, for each $E$-node visit, it suffices to change the order of the nodes of the previously computed full binary tree at a specific depth, costing $O({\max }_{i}g(i,𝒘))$ time.

We can generalize this approach to full-binary distributions having zero values. The obstacle is that we cannot guarantee constant delay since we might traverse long paths with zero weights. As a remedy, we want to skip each depth $i$ with $w_i=0$. To do that, let us denote by $I=\{i\in [1..d]\mid w_i>0\}$ all depths with leaves. Then it suffices to restrict the values of a change level of a node to values of $I\cup \{0\}$. By construction, the root node has change level $0$, and a node with change level $\delta$ has children whose augmented value is the successor of $\delta$ in $I$.

To obtain worst-case constant delay time, we can drop the requirement to output in lexicographic order by using a folklore technique, such as the alternating output technique [15]. The idea is to output nodes on odd depths when visiting them the first time, but postpone the output of nodes on even depths until we backtrack and move outside their respective subtrees.

In what follows, we show how to generalize the enumeration of full binary trees to general binary trees, where internal nodes are allowed to have one or two children.

From Lemmas 3 and 4, the binary distribution $𝒘=(w_1,\mathrm{\dots },w_d)$ of a non-full binary tree also satisfies . We make the connection to full binary trees by adding dummy leaves to all internal nodes that have only one child. To this end, we denote the number of dummy leaves added at depth $i$ by $x_i$, and construct a vector $𝒙=(x_1,\mathrm{\dots },x_d)$. The sum $𝒙+𝒘$ gives a vector that is the binary distribution of a full binary tree because ${\sum }_{i=1}^d(w_i+x_i)/2^i=1$. In what follows, we call $𝒙$ the complement vector of $𝒘$, and $𝒘+𝒙$ the completion of $𝒘$. For such $𝒙$, a nonnegative integer vector $𝒚$ that satisfies $𝒚\le 𝒙$ is called the subcomplement vector of $𝒘$.

In this section, we extend the results of the previous section to general $\alpha$-ary trees for a constant $\alpha \ge 2$. Like for binary trees ($\alpha =2$), we first define the notion of an $\alpha$-ary distribution.

We have addressed the problem to efficiently enumerate trees whose numbers of leaves on each depth are given by a query vector. Specifically, for any leaf distribution $𝒘=(w_1,\mathrm{\dots },w_d)$ of (full) binary or (full) $\alpha$-ary trees, we obtain the following time complexities. First, we can output the first tree in $O(d+n)$ time. We can output every subsequent tree, after constant delay, in $O(m)$ time by encoding this tree as a difference to a previous one using $O(m)$ words. Here, $n={\sum }_{i=1}^d{w}_i$ is the total number of nodes and $m=\max \{w_i\mid i\in [1..d]\}$ is the maximal number of nodes at any depth. These results hold for both full binary trees and full $\alpha$-ary trees with $\alpha \ge 2$, and extend to general binary trees with analogous enumeration guarantees.

As future work, we want to determine the exact number of full binary trees and full $\alpha$-ary trees with distribution $𝒘$ by a closed-form product formulas involving binomial coefficients. We further strive to give practical implementations of our proposed enumeration algorithms.