Keywords: breadth-first search, depth-first search, average-case complexity, trees, Galton–Watson trees, random graphs.

1 Introduction↩︎

Several important problems in computer science and artificial intelligence can be formulated as search problems [1]. Some examples include the traveling salesman problem, scheduling problems, and the problem of finding optimal moves in various games. Most decision-making problems can be also naturally thought of as search problems, where the decision space is modeled as a graph or a tree. For many of these problems, a different search algorithm is optimal, depending on the instance [2]. Some machine learning approaches exist for algorithm selection [3] depending on the instance, but they are usually less useful than having an exact average-case comparison.

In this paper, we find the average time complexity of the classical tree search algorithms—breadth-first search (BFS) and depth-first search (DFS)—when we perform a search for a random target node at a fixed level, given that we begin at the root of an ordered tree with a prescribed number of edges. We consider the most simple scenario when no additional information about the tree is available. Then, it is reasonable to assume that the target node is sampled uniformly from all nodes at the prescribed level among all trees with the given number of edges. BFS and DFS are compared in terms of their complexities for each target node level, yielding an optimal criterion for choosing between them.

In particular, by using a folklore correspondence between ordered trees and Dyck paths, we find that the expected number of steps made by DFS, when we search for a unique target node on level \(\ell\) in a tree with \(n\) edges, is \(\frac{\ell}{2\ell +1}(n+\ell + 1)\). Then, we find the expected number of steps made by BFS via results of Takács [4] on the occupation measure of Brownian excursions. A connection between the generating function for the BFS time-complexity and the so-called Fibonacci polynomials is also established. The average time complexities of the two algorithms are compared in the asymptotic case, when \(\ell,n\to \infty\), and when \(\ell\) is a function of \(n\). Consequently, we find a unique threshold \(\lambda_{n}\approx 0.789\sqrt{n}\), such that BFS is asymptotically faster than DFS if and only if \(\ell\leq \lambda_n\). This confirms the intuition that BFS should have advantage when the target is close to the root, while DFS is superior when the target is far from the root. The limit of the ratio of the two complexities is also found for certain intervals for the target level \(\ell\).

While ordered trees are a very general class of structures used to model various recursive processes, we also find the asymptotic average time complexity of BFS for an arbitrary class of Galton–Watson trees, which includes ordered trees, binary and \(m\)-ary trees, labeled trees and other classes. This generalization is obtained by utilizing some results on stochastic process and the limiting shape of trees by Aldous [5]. Finally, we propose a variation of DFS called truncated DFS, and we show that it has a better average time performance than both BFS and DFS when the target level \(\ell\) is known in advance. It is also shown that the average-case time complexity of the truncated DFS is half of those of BFS, when \(\ell = s\sqrt{n}\), for any constant \(s\).

Our results have several possible applications, since they are related to the complexity of the two most popular search algorithms in the universal scenario of traversing a tree. Note that in the cases when the size of the tree, \(n\), is not known in advance, one may first use the well-known method of Knuth [6] to estimate that size, before using our formulas to find the better search method for different levels \(\ell\).

1.1 Problem formulation and main result↩︎

Consider the set \(\mathcal{T}\) of all unlabeled rooted ordered trees, which we simply refer to as ordered trees or trees. In each ordered tree, we have a fixed node called a root, as well as a fixed ordering for the children of each node. Let \(\mathcal{T}_{n}\) denote the subset of trees in \(\mathcal{T}\) having exactly \(n\) edges; it is well known that the number of trees in \(\mathcal{T}_{n}\) is the \(n\)th Catalan number \[C_{n} = \frac{1}{n+1}\binom{2n}{n}.\] Note that each tree in \(\mathcal{T}_{n}\) has \(n+1\) nodes. The level of a node \(v\) is the length of the unique path from \(v\) to the root; thus the root is at level \(0\). Trees will be drawn with the root at the top.

For trees, BFS explores the entire neighborhood of the current node and then continues its execution recursively with the children of the current node one-by-one, while DFS follows one path for as long as possible and backtracks when stuck. DFS is equivalent to a pre-order traversal of the tree, that is, the root is visited first and then recursively the subtrees from left to right. Figure 1 illustrates the orders in which BFS and DFS will explore the nodes of a particular tree, if the initial node is the root.

Let us call the label received by a node \(v\), when doing the traversals, the bfsScore and the dfsScore of \(v\), respectively. We define them formally as follows: \[\begin{align} \mathop{\mathrm{bfsScore}}(v) &\mathrel{\vcenter{:}}= \text{the number of nodes visited before v when using BFS}. \\ \mathop{\mathrm{dfsScore}}(v) &\mathrel{\vcenter{:}}= \text{the number of nodes visited before v when using DFS}. \end{align}\] It is important to note that \(\mathop{\mathrm{bfsScore}}(v)\) and \(\mathop{\mathrm{dfsScore}}(v)\) also give the number of steps taken in searching for \(v\) when one starts at the root and uses BFS and DFS, respectively. Thus, these two quantities measure the time complexity of the two algorithms when the target is \(v\).

Our goal will be to compare the average time complexity of BFS and DFS—i.e., the average \(\mathop{\mathrm{bfsScore}}\) and the average \(\mathop{\mathrm{dfsScore}}\)—under a minimal set of assumptions for the search. In particular, consider a search from the root of some tree \(T\in \mathcal{T}_{n}\) to a specific target node \(x\) in \(T\), by using BFS or DFS. We assume that we have a function telling us whether the current node is the target \(x\), but we do not know the number of children of the current node or anything else about it. If the target \(x\) is chosen uniformly at random among all the nodes in the trees in \(\mathcal{T}_{n}\), then it is readily seen that the expected number of steps needed to reach \(x\) is the same for both BFS and DFS, namely \[\frac{|\mathcal{T}_{n}|\sum_{i=1}^{n}i}{n|\mathcal{T}_{n}|} = \frac{1}{n}\frac{n(n+1)}{2} = \frac{n+1}{2}.\] Would this change if the level of the target node is fixed? We compare the expected number of steps of the two algorithms, if \(x\) is selected uniformly at random from all nodes at a fixed level \(\ell\) among the trees in \(\mathcal{T}_{n}\)? For instance, when \(n=3\) and \(\ell=2\), we have \(5\) such nodes as seen in Figure 2. Note that under this setting, the chance for \(T\) to be each of the trees in \(\mathcal{T}_{n}\) is not the same, but it is proportional to the number of nodes at level \(\ell\).

Intuition suggests that BFS is a better choice if \(\ell\) is relatively small, while DFS should be preferred when \(\ell\) is large. What is the exact place where DFS becomes faster, and is this place unique? To answer this question, we need to compute and compare the two expectations given below, where \(\mathop{\mathrm{lev}}(T,\ell)\) denotes the set of nodes at level \(\ell\) in the tree \(T\): \[\mathop{\mathbb{E}}_{\substack{x\in \mathop{\mathrm{lev}}(T,\ell) \\T\in \mathcal{T}_{n}}}(\mathop{\mathrm{bfsScore}}(x)) \quad\text{and}\quad \mathop{\mathbb{E}}_{\substack{x\in \mathop{\mathrm{lev}}(T,\ell) \\T\in \mathcal{T}_{n}}}(\mathop{\mathrm{dfsScore}}(x)).\] Each of the two expectations is a fraction with denominator equal to the total number of nodes at level \(\ell\) among the trees in \(\mathcal{T}_{n}\). A result of Dershowitz and Zaks gives us this denominator.

Therefore, comparing the average time complexity of BFS and DFS is equivalent to comparing the two sums defined below: \[\mathop{\mathrm{totalB}}(n,\ell ) \mathrel{\vcenter{:}}=\sum_{T\in{\mathcal{T}}_{n}} \sum\limits_{v\in \mathop{\mathrm{lev}}(T,\ell )} \mathop{\mathrm{bfsScore}}(v) \quad \text{and} \quad \mathop{\mathrm{totalD}}(n,\ell ) \mathrel{\vcenter{:}}=\sum_{T\in{\mathcal{T}}_{n}} \sum\limits_{v\in \mathop{\mathrm{lev}}(T,\ell )} \mathop{\mathrm{dfsScore}}(v).\] The main result of this paper is the following theorem.

Therefore, BFS is asymptotically faster than DFS if and only if \(\ell\leq \lambda\sqrt{n}\), for the given constant \(\lambda\). We also give explicit formulas for \(\mathop{\mathrm{totalB}}(n,\ell )\) and \(\mathop{\mathrm{totalD}}(n,\ell )\), and thus for the average time complexities of BFS and DFS in the considered settings.

1.2 Related works↩︎

The average performance of search algorithms over different families of graphs is a direction in which not many exact results are known. An article of Everitt and Hutter [8] contains the only study we found considering the average-case complexities of BFS and DFS on trees for a fixed target level. However, their results are about complete binary trees with given depth as opposed to ordered trees with arbitrary depth, as in our case. Furthermore, the way they sample the target nodes is different and the obtained expressions for the expected running times, in case of a single target node, are only approximations (see [8]). Another article by Stone and Sipala [9] investigates the average time complexity of two variations of DFS in binary trees.

If the number of the vertices in the tree is not known in advance, one can use the simple algorithm of Knuth [6] to obtain an unbiased estimator of this number, before using our results. Knuth’s method can be applied when having a tree in any given family of Galton–Watson trees. Some alternative methods for estimation of the size of the tree were suggested by Kilby et al. [10]. Two useful articles on algorithm selection for combinatorial search problems are the work of Rice [11] and the survey by Kotthoff [3].

Several other results exist on both BFS and DFS, and their variations. The average performance of the \(A^{*}\) algorithm (which reduces to BFS if no heuristic information is available) is studied in [12], when searching in graphs. A recent article by Jacquet and Janson [13] gives asymptotic results concerning several statistics when DFS begins at a random node of a random directed graph with certain distribution of the outdegrees for its vertices. In addition, DFS has been used to obtain some classical results in enumerative combinatorics [14], [15].

1.3 Outline of the paper↩︎

The organization of our paper is as follows:

• In Section 2, we find a simple exact formula for \(\mathop{\mathrm{totalD}}(n,\ell )\). Our proof for this formula utilizes a classical bijection between ordered trees and Dyck paths; this allows us to translate the problem to establishing an identity, for which we give a combinatorial proof by interpreting both sides as counting certain lattice paths.

• In Section 3, we obtain a summation formula for \(\mathop{\mathrm{totalB}}(n,\ell )\) via results of Takács [4] used to study the occupation measure of Brownian excursions. In addition, we find the asymptotic behavior of \(\mathop{\mathrm{totalB}}(n,\ell )\) depending on \(\ell\).

• Section 4 is devoted to the proof of our main result—Theorem 2—which establishes a unique threshold for which BFS becomes asymptotically faster than DFS. In Section 4.1, we show that when \(n^{1/3}\prec\ell\prec\sqrt n\), then BFS can be arbitrarily faster than DFS, while if \(\sqrt{n}\prec \ell \prec \sqrt{n\ln{n}}\), then DFS can be at most twice as fast. Here and throughout the paper, \(f(x) \prec g(x)\) means \(f(x) = o(g(x))\).

• In Section 5, we find a different formula for \(\mathop{\mathrm{totalB}}(n,\ell )\) by using generating function techniques. This approach reveals a curious identity expressing the generating function for \(\mathop{\mathrm{totalB}}(n,\ell )\) in terms of the Catalan generating function and Fibonacci polynomials; see Theorem 9 (b). We then derive an alternative formula for \(\mathop{\mathrm{totalB}}(n,\ell )\) by extracting coefficients from the generating function formula we found; see Theorem 14. Along the way—in Section 5.1—we give several identities related to Fibonacci polynomials needed for proving Theorem 9.

• Section 6 establishes an expression for the asymptotic value of \(\mathop{\mathrm{totalB}}(n,\ell)\), for any given \(\ell\), when we have an arbitrary Galton–Watson tree; see Equation 35 .

• In Section 7, we introduce a new algorithm called truncated DFS, which is faster in expectation than both BFS or DFS when we know the level \(\ell\) in advance. We show that this algorithm is twice as fast as BFS, when \(\ell = s\sqrt{n}\), for any constant \(s\).

• We conclude in Section 8 by presenting several questions for future study.

2 Exact formula for the average time complexity of DFS↩︎

In this section, we establish a surprisingly simple formula for \(\mathop{\mathrm{totalD}}(n,\ell )\) by using a classical correspondence between ordered trees and lattice paths. When we refer to a lattice path from \((a,b)\) to \((c,d)\), we will mean a path in \(\mathbb{Z}^{2}\) starting at \((a,b)\), ending at \((c,d)\), and consisting of a sequence of steps from a prescribed step set \(S\). We will work with two kinds of lattice paths, defined as follows:

• A diagonal path is a lattice path with step set \(S = \{(0,1), (1,0)\}\), with \((0,1)\) and \((1,0)\) called \(N\) and \(E\) steps, respectively (from North and East).

• A horizontal path is a lattice path with step set \(S = \{(1,1), (1,-1)\}\), with \((1,1)\) and \((1,-1)\) called \(U\) and \(D\) steps, respectively (from Up and Down).

A Dyck path of semilength \(n\) is a diagonal path from \((0,0)\) to \((n,n)\) that stays weakly above the diagonal \(y=x\). Note that a simple bijection between horizontal and diagonal paths is to send a horizontal \(U\) (respectively \(D\)) step to a diagonal \(N\) (respectively \(E\)) step. Note also that the set of Dyck paths maps to the set of horizontal paths from \((0,0)\) to \((2n,0)\), staying weakly above \(y=0\).

Given \(a\leq b\) and \(c \leq d\), let \([(a,b)\rightarrow(c,d)]\) denotes the number of diagonal paths from \((a,b)\) to \((c,d)\) that stay weakly above the diagonal \(y=x\). We shall need the following well-known fact from lattice path enumeration.

For example, when \(i=n\) and \(j=n\), we get that the number of Dyck paths of semilength \(n\) is \[[(0,0)\rightarrow(n,n)] = \frac{1}{2n+1}\binom{2n+1}{n} = \frac{1}{n+1}\binom{2n}{n} = C_n,\] the \(n\)th Catalan number.

Below is our main result of this section.

Using Theorems 1 and 3, we can now obtain the expected \(\mathop{\mathrm{dfsScore}}\) over all nodes at a given level \(\ell\) among the trees in \(\mathcal{T}_{n}\): \[\mathop{\mathbb{E}}_{\substack{x\in \mathop{\mathrm{lev}}(T,\ell ) \\T\in \mathcal{T}_{n}}}(\mathop{\mathrm{dfsScore}}(x)) = \frac{\ell\binom{2n}{n-\ell }}{\frac{2\ell +1}{2n+1}\binom{2n+1}{n-\ell }} = \frac{\ell }{2\ell +1}(n+\ell +1).\] When \(\ell \to \infty\) and \(n \to \infty\), with \(l\prec n\), this expectation is approximately \(n/2\).

3 Exact formula for the average time complexity of BFS↩︎

In this section, we give an exact summation formula for \(\mathop{\mathrm{totalB}}(n,\ell )\). To begin, let us define some random variables on the trees in \(\mathcal{T}_{n}\): \[\label{def:Random32variables} \begin{align} h_n(\ell ) &\mathrel{\vcenter{:}}= \text{total number of vertices at level \ell},\\ H_n(\ell ) &\mathrel{\vcenter{:}}= \text{total number of vertices at levels \leq \ell },\\ \nu_n(\ell ) &\mathrel{\vcenter{:}}= \text{total number of vertices at levels \geq \ell },\\ S_n(\ell ) &\mathrel{\vcenter{:}}= \text{sum of bfsScores on level \ell}. \end{align}\tag{4}\] For a sample realization of these random variables, see Figure 5.

We can express \(\mathop{\mathrm{totalB}}(n,\ell )\) in terms of these quantities in the following way: \[\begin{align} \mathop{\mathrm{totalB}}(n,\ell ) = \mathopen{}\mathclose{\left|\mathcal{T}_n}\right|\cdot \mathbb{E}\mathopen{}\mathclose{\left[S_n(\ell )}\right] &= C_n \cdot \mathbb{E}\mathopen{}\mathclose{\left[\binom{H_n(\ell )}{2}-\binom{H_n(\ell -1)}{2}}\right] \nonumber\\ &= C_n \cdot \mathbb{E}\mathopen{}\mathclose{\left[\binom{n+1-v_n(\ell +1)}{2}-\binom{n+1- v_n(\ell )}{2}}\right] \nonumber\\ &=C_n\cdot\mathbb{E}\mathopen{}\mathclose{\left[\binom{v_n(\ell +1)}{2} - \binom{v_n(\ell )}{2} - n\mathopen{}\mathclose{\left(v_n(\ell +1) - v_n(\ell ) }\right)}\right]. \label{eq:totB32expectation} \end{align}\tag{5}\] Moreover, in what follows, we shall use the following results of Takács [4]: \[\begin{align} C_n \cdot \mathbb{E}\mathopen{}\mathclose{\left[v_n(\ell )}\right] &= \binom{2n}{n-\ell }, \quad \text{and} \tag{6}\\ C_n\cdot \mathbb{E}\mathopen{}\mathclose{\left[\binom{v_n(\ell )}{2}}\right] &= (n+\ell )\binom{2n}{n-\ell } - \frac{n+2\ell }{2} \binom{2n}{n-2\ell }- 2 \ell\sum_{j=\ell }^{2\ell -1}\binom{2n}{n-j}. \tag{7} \end{align}\] The motivation of Takács was to find explicit expressions for the moments of the occupation measure of a Brownian excursion as a limit of the respective moments for simple Bernoulli excursions. Using our notation, the occupation measure of the Bernoulli excursion is exactly \(v_n(\ell )\), and the Brownian excursion is the natural encoding of the limit of properly scaled random trees from \(\mathcal{T}_n\)—that is, the continuum random tree introduced by Aldous in [20]–[22]. In fact, this link allow us to generalize our asymptotics for \(\mathop{\mathrm{totalB}}(n,\ell )\) on \(\mathcal{T}_n\) to all classes of trees which can be constructed as conditioned Galton–Watson trees (see Section 6).

A formula for \(\mathop{\mathrm{totalB}}(n,\ell )\) is obtained below. In the statement of this result, \(\Phi\) denotes the cumulative distribution function of the standard normal distribution: \[\Phi(s) \mathrel{\vcenter{:}}= \frac{1}{\sqrt{2\pi}}\int_{-\infty}^s e^{-x^2/2}\, \mathrm{d}x.\] As noted in Section 1.3, we use the notation \(a_n\prec b_n\) to mean that \(a_n=o(b_n)\), that is, \(a_n/b_n\to 0\) as \(n\to\infty\). Similarly, \(a_n\succ b_n\) means that \(a_n=\omega(a_n)\).

4 Comparing the average time complexity of BFS and DFS.↩︎

Now, we are ready to prove the main result of this paper.

Theorem 2 gives us a unique threshold occurring at \(\lambda\sqrt{n}\), where \(\lambda\approx 0.789004\). It is natural to suspect that this threshold will be close to the average level of a node in \(\mathcal{T}_n\), when \(n\to\infty\). In order to make this comparison, we will use the following result of Flajolet and Sedgewick.

We have that \(\frac{1}{2}\sqrt{\pi}\approx 0.8862>0.789\approx\lambda\) and thus for ordered trees, the unique threshold occurs around the average level for the nodes in \(\mathcal{T}_{n}\), but slightly below it. In Section 8, we ask whether this is a general phenomenon that applies to other families of trees. For instance, is there a similar transition for binary trees around the average level for the nodes in them? We also ask for an explanation of the obtained small discrepancy in the case of ordered trees.

4.1 The BFS and DFS complexity ratio for certain intervals of target levels↩︎

We will also show that the ratios between the average complexities of BFS and DFS are the constants \(0\) and \(2\), in two large intervals for \(\ell\) around \(\ell = \sqrt{n}\).

First, observe that Theorem 3 and the local limit theorem (see Equation 12 ) imply that for any \(\ell = s\sqrt{n}\), \[\frac{\mathop{\mathrm{totalD}}(n,s\sqrt n)}{4^n}\longrightarrow g(s):=\frac{s}{\sqrt\pi}e^{-s^2}.\] In addition, recall that Equation 9 gives that for any \(\ell = s\sqrt{n}\), \[\frac{\mathop{\mathrm{totalB}}(n,s\sqrt n)}{4^n} \;\longrightarrow\; B(s) := \frac{2s}{\sqrt\pi}e^{-s^2} - 2\Delta(s) = 2(g(s)-\Delta(s)), \qquad n\to\infty, \label{eq:Bform}\tag{17}\] where \[\Delta(s) := \Phi(2\sqrt2\,s) - \Phi(\sqrt2\,s).\]

We then have \[\label{eq:BDratio} \frac{\mathop{\mathrm{totalB}}(n,s\sqrt n)}{\mathop{\mathrm{totalD}}(n,s\sqrt n)}\to \frac{B(s)}{g(s)} = 2\mathopen{}\mathclose{\left(1-\frac{\Delta(s)}{g(s)}}\right).\tag{18}\] To investigate this ratio at \(s\to 0\), we will need the expansion of \(\Phi\) near \(0\) to third order.

Apply Lemma 2 at \(x=2\sqrt2\,s\) and \(x=\sqrt2\,s\). Using \((2\sqrt2\,s)^3 = 8\cdot2\sqrt2\,s^3=16\sqrt2\,s^3\) and \((\sqrt2\,s)^3=2\sqrt2\,s^3\), \[\Phi(2\sqrt2\,s) = \frac{1}{2}+\frac{1}{\sqrt{2\pi}}\mathopen{}\mathclose{\left(2\sqrt2\,s-\frac{16\sqrt2}{6}s^3}\right)+O(s^5) = \frac{1}{2}+\frac{1}{\sqrt{2\pi}}\mathopen{}\mathclose{\left(2\sqrt2\,s-\frac{8\sqrt2}{3}s^3}\right)+O(s^5),\] \[\Phi(\sqrt2\,s) = \frac{1}{2}+\frac{1}{\sqrt{2\pi}}\mathopen{}\mathclose{\left(\sqrt2\,s-\frac{2\sqrt2}{6}s^3}\right)+O(s^5) = \frac{1}{2}+\frac{1}{\sqrt{2\pi}}\mathopen{}\mathclose{\left(\sqrt2\,s-\frac{\sqrt2}{3}s^3}\right)+O(s^5).\] After simplification, we obtain that when \(s\to0\), \[\Delta(s) = \Phi(2\sqrt2\,s)-\Phi(\sqrt2\,s) = \frac{1}{\sqrt{2\pi}}\mathopen{}\mathclose{\left(\sqrt2\,s-\frac{7\sqrt2}{3}s^3}\right)+O(s^5) = \frac{s}{\sqrt\pi} - \frac{7}{3\sqrt\pi}\,s^3 + O(s^5).\]

Meanwhile \[g(s)=\dfrac{s}{\sqrt\pi}e^{-s^2}=\dfrac{s}{\sqrt\pi}\bigl(1-s^2+O(s^4)\bigr)=\dfrac{s}{\sqrt\pi}-\dfrac{s^3}{\sqrt\pi}+O(s^5).\] Hence in \(B(s)=2g(s)-2\Delta(s)\) the linear terms cancel exactly, and only the cubic terms survive: \[B(s) = 2\mathopen{}\mathclose{\left(-\frac{s^3}{\sqrt\pi}}\right)-2\mathopen{}\mathclose{\left(-\frac{7}{3\sqrt\pi}s^3}\right)+O(s^5) = \mathopen{}\mathclose{\left(-2+\frac{14}{3}}\right)\frac{s^3}{\sqrt\pi}+O(s^5) = \frac{8}{3\sqrt\pi}\,s^3+O(s^5).\] Consequently, when \(s\to 0\), \[\frac{\mathop{\mathrm{totalB}}(n,s\sqrt n)}{\mathop{\mathrm{totalD}}(n,s\sqrt n)} \;\longrightarrow\;\frac{B(s)}{g(s)} \sim \frac{8}{3}s^2 \;\longrightarrow\;0. \label{eq:ratio0}\tag{19}\] In fact, this conclusion is not limited to a fixed constant \(s\), but extends to any sequence of target levels tending to \(0\) relative to \(\sqrt n\), at a suitable rate, as follows.

When \(s\to\infty\), we will need the Lemma below which can be proven via integration by parts.

Write \(\Delta(s)\) as a difference of two upper tails, \[\Delta(s) = \Phi(2\sqrt2\,s)-\Phi(\sqrt2\,s) = \bigl[1-\Phi(\sqrt2\,s)\bigr] - \bigl[1-\Phi(2\sqrt2\,s)\bigr],\] and apply Lemma 3. Since \((\sqrt2\,s)^2/2 = s^2\), we have \(\varphi(\sqrt2\,s)=\frac{1}{\sqrt{2\pi}}e^{-s^2}\) and thus \[1-\Phi(\sqrt2\,s) = \frac{\varphi(\sqrt2\,s)}{\sqrt2\,s}\bigl(1+O(s^{-2})\bigr) = \frac{e^{-s^2}}{\sqrt{2\pi}\cdot\sqrt2\,s}\bigl(1+O(s^{-2})\bigr) = \frac{e^{-s^2}}{2\sqrt\pi\,s}\bigl(1+O(s^{-2})\bigr).\] For the second tail, since \((2\sqrt2\,s)^2/2=4s^2\), we have \(\varphi(2\sqrt2\,s)=\frac{1}{\sqrt{2\pi}}e^{-4s^2}\), so \[1-\Phi(2\sqrt2\,s) = \frac{\varphi(2\sqrt2\,s)}{2\sqrt2\,s}\bigl(1+O(s^{-2})\bigr) = \frac{e^{-4s^2}}{\sqrt{2\pi}\cdot2\sqrt2\,s}\bigl(1+O(s^{-2})\bigr) = \frac{e^{-4s^2}}{4\sqrt\pi\,s}\bigl(1+O(s^{-2})\bigr).\] The second tail is exponentially smaller than the first since when \(s\to\infty\) their ratio is \[\frac{e^{-4s^2}/(4\sqrt\pi\,s)}{e^{-s^2}/(2\sqrt\pi\,s)} = \frac{1}{2}\,e^{-3s^2} \longrightarrow 0\] Thus, after subtracting we obtain \[\Delta(s) = \frac{e^{-s^2}}{2\sqrt\pi\,s}\bigl(1+O(s^{-2})\bigr) - \frac{e^{-4s^2}}{4\sqrt\pi\,s}\bigl(1+O(s^{-2})\bigr) = \frac{e^{-s^2}}{2\sqrt\pi\,s}\bigl(1+O(s^{-2})\bigr).\] Therefore, \[\frac{\Delta(s)}{g(s)} = \frac{\dfrac{e^{-s^2}}{2\sqrt\pi\,s}\bigl(1+O(s^{-2})\bigr)}{\dfrac{s}{\sqrt\pi}e^{-s^2}} = \frac{1}{2\sqrt\pi\,s}\cdot\frac{\sqrt\pi}{s}\,\bigl(1+O(s^{-2})\bigr) = \frac{1}{2s^2}\bigl(1+O(s^{-2})\bigr) \;\longrightarrow\;0.\] In particular \(\Delta(s)=o(g(s))\). Hence, when \(s\to\infty\), by Equation 18 we have \[B(s) \sim 2g(s)\qquad\text{ and } \qquad \frac{\mathop{\mathrm{totalB}}(n,s\sqrt n)}{\mathop{\mathrm{totalD}}(n,s\sqrt n)} \;\longrightarrow\;2. \label{eq:ratioinf}\tag{20}\] As with the previous limit, this conclusion is not limited to a fixed \(s\), and extends as follows.

Together, Theorems 7 and 8 show that the ratio \(\mathrm{totalB}(n,\ell)/\mathrm{totalD}(n,\ell)\) already exhibits its limiting behavior \(0\), respectively \(2\), for every target level in certain large intervals. The exponents \(\tfrac13\) and \(\tfrac12\) in these two theorems are not claimed to be sharp. In fact, we suspect that the two theorems hold whenever \(\ell\prec \sqrt{n}\) and \(\ell\succ \sqrt{n}\), respectively. Yet, we were not able to show that. One reason for us to believe the mentioned extension is possible (at least for the latter interval) is Theorem 17, its possible extension mentioned in Remark 18, and the fact that the truncated DFS algorithm is almost identical to the DFS algorithm for large target levels \(\ell\).

5 The generating function for \(\mathop{\mathrm{totalB}}\) and Fibonacci polynomials↩︎

In this section, we obtain an expression for the generating function of \(\mathop{\mathrm{totalB}}(n,\ell )\), without using the results in the previous Section 3. Instead, we use a generating function approach which demonstrates a surprising connection between the generating function of \(\mathop{\mathrm{totalB}}(n,\ell )\) and Fibonacci polynomials. Furthermore, we leverage this connection to find a formula for \(\mathop{\mathrm{totalB}}(n,\ell )\) as a difference of two alternating sums, which is different from the one from Equation 8 . We begin by defining the generating functions \[F_{\ell }(x,y,z) \mathrel{\vcenter{:}}= \sum_{n=0}^{\infty} \sum\limits_{T\in \mathcal{T}_n} x^{k(T)}y^{m(T)}z^{n},\] where \(k(T)\) is the number of non-root nodes in \(T\) at levels smaller than \(\ell\) and \(m(T)\) is the number of nodes in \(T\) at level \(\ell\). Now, consider the ordinary generating function \[C=C(z)\mathrel{\vcenter{:}}= \sum_{n=0}^{\infty} C_n z^n = \frac{1-\sqrt{1-4z}}{2z} = \frac{2}{1+\sqrt{1-4z}}\] for the Catalan numbers \(C_n\). Since \(C_n\) counts ordered trees with \(n\) edges and every ordered tree has a single node (the root) at level 0, it follows that \[F_0 = yC = \frac{2y}{1+\sqrt{1-4z}}.\] Using one of the standard decompositions of ordered trees, which gives that the children of the root of every ordered tree are themselves roots of ordered trees, implies the equations \[\label{eq:F-1} F_{1} = 1 + zF_{0} + (zF_{0})^2 + \cdots = \frac{1}{1-zF_{0}} = \frac{1}{1-yzC}\tag{21}\] and \[\label{eq:F-l} F_{\ell } = 1 + xzF_{\ell -1} + (xzF_{\ell -1})^2 + \cdots = \frac{1}{1-xzF_{\ell -1}} \quad (\ell\geq 2).\tag{22}\] This recursive relation shows that \(F_\ell\) can be written as a continued fraction as, for example, in the work of de Bruijn, Knuth and Rice [28]. The formula for \(F_\ell\) that one can obtain via this approach, will be proven directly in Section 5.2. Then, since our goal is to find \(\mathop{\mathrm{totalB}}(n,\ell )\), we will use the obtained formula for \(F_\ell\) to find the generating function \[B_{\ell }=B_{\ell }(z)\mathrel{\vcenter{:}}=\sum_{n=0}^{\infty}\mathop{\mathrm{totalB}}(n,\ell )z^{n}.\] If \(m(T)=m\) and \(k(T)=k\), then a straightforward counting argument yields \[\sum\limits_{v\in \mathop{\mathrm{lev}}(T,\ell )} \mathop{\mathrm{bfsScore}}(v) = mk + \frac{m(m+1)}{2}.\] The latter equation gives us the following expression for \(B_\ell\) in terms of \(F_\ell\) and its derivatives. \[\label{e-BF} B_{\ell }=\mathopen{}\mathclose{\left[\Big(\frac{\partial^{2}}{\partial x\partial y}+\frac{1}{2}\cdot\frac{\partial^{2}}{\partial y^{2}}+\frac{\partial}{\partial y}\Big)\,F_{\ell }}\right]_{\substack{x=1,\,y=1} }.\tag{23}\]

5.1 Fibonacci polynomials and some identities↩︎

In this section, we prove some lemmas that will be needed to show that the generating functions \(F_{\ell }\) and \(B_{\ell }\) can be expressed in terms of the Fibonacci polynomials \(f_{n}(z)\) defined by \[f_{n}(z)\mathrel{\vcenter{:}}=\sum_{k=0}^{\mathopen{}\mathclose{\left\lfloor n/2}\right\rfloor }{n-k \choose k}z^{k}\] for \(n\geq0\) (and \(f_{n}(z)\mathrel{\vcenter{:}}= 0\) for \(n<0\)). The first few polynomials \(f_{n}(z)\) are displayed in Table ¿tbl:tb-fibpoly?. It is well known that the \(n\)th Fibonacci number \(f_n\) (defined with initial terms \(f_0=1\) and \(f_1=1\)) counts square-domino tilings of a \(1\times n\) rectangle, and the coefficient \({n-k \choose k}\) of \(f_{n}(z)\) counts such tilings with \(k\) dominoes and \(n-2k\) squares.¹ Thus setting \(z=1\) in \(f_{n}(z)\) recovers the \(n\)th Fibonacci number \(f_n\).

Next, we prove several technical lemmas related to Fibonacci polynomials.

5.2 Alternative \(\mathop{\mathrm{totalB}}\) formula↩︎

We are now ready to establish the connection between the generating functions \(F_\ell\) and \(B_\ell\) and Fibonacci polynomials, which will lead to an explicit formula for \(\mathop{\mathrm{totalB}}(n,\ell )\) as a difference of two alternating sums.

By extracting coefficients from the generating function \(B_{\ell }\), we get an explicit formula for \(\mathop{\mathrm{totalB}}(n,\ell )\), for which we give a proof below. In this proof, we use the standard notation \([z^n]\, f\) for the coefficient of \(z^n\) in \(f\).

It would be interesting to give a direct proof that our two expressions for \(\mathop{\mathrm{totalB}}(n,\ell )\)—in Equations 8 and 30 —are in fact equal. Recovering the asymptotics of \(\mathop{\mathrm{totalB}}(n,\ell)\) obtained in Theorem 4 from Equation 30 would be also interesting and we were not able to do that.

6 General results on the asymptotics of totalB for Galton–Watson trees↩︎

A well-known class of random rooted trees are the Galton–Watson trees. In this section, we generalize Theorem 4 to Galton–Watson trees. Here, we present a short overview of these objects. For a thorough and rigorous presentation of Galton–Watson trees, and random trees in general, we refer to the surveys by Le Gall [33] and Janson [34], as well as the book of Drmota [35].

Let \(Z\) be a random variable on \(\{0,1,2,\dots\}\) with \[\mathbb{E}\mathopen{}\mathclose{\left[Z}\right] = 1 \quad \text{and} \quad \mathbb{V}\mathrm{ar}{Z} = \sigma^2.\] We define a Galton–Watson tree \(T^{(Z)}\) with an offspring distribution \(Z\) recursively, by giving each node independently a random number of children distributed as \(Z\). Let us define \(\mathcal{T}^{(Z)}_n\) to be the set of all possible trees \(T^{(Z)}\) with \(n\) edges, endowed with the conditional probability induced by \(Z\). As observed by Aldous (see [21] and [35]), the uniform distribution on some frequently used sets of rooted trees is generated by \(\mathcal{T}_n^{(Z)}\) for a suitable \(Z\). For example:

• ordered trees, when \(Z\) has a geometric distribution—i.e., \(\mathbb{P}(Z=k) = 1/2^{k+1}\) for \(k \geq 0\).

• strict \(m\)-ary trees (every node has \(0\) or \(m\) children), when \(\mathbb{P}(Z=0) = \mathbb{P}(Z=m) = 1/2\).

• \(m\)-ary trees when \(Z\) has a binomial \(\operatorname{Bin}(m,1/m)\) distribution.

• labeled trees when \(Z\) has a Poisson distribution with parameter 1—i.e., when \(\mathbb{P}(Z = k) = e^{-1}/k!\).

We obtain the asymptotics of \(\mathop{\mathrm{totalB}}(n,s\sqrt{n})\) on all these sets of trees; see Corollary 1.

As we have already seen in Section 2, an ordered tree with \(n\) edges can be associated with a discrete excursion from \(0\) to \(2n\) via its corresponding Dyck path. It is therefore natural to expect that, after scaling, the corresponding Dyck path converges weakly to a standard Brownian excursion \(\mathbf{e}\) of length 1, and thus the trees themselves will have a weak limit in some abstract sense. This was formalized in the classical works of Aldous [20]–[22], who called this limiting object the continuum random tree.

Using the random variables defined in Equation 4 , in order to find \(\mathop{\mathrm{totalB}}(n,l)\) in the general case, we can use the equation \[\begin{align} S_n(\ell ) = \binom{H_n(\ell )}{2} - \binom{H_n(\ell -1)}{2} &= \frac{1}{2}\mathopen{}\mathclose{\left(H_n(\ell ) - H_n(\ell -1) }\right) \mathopen{}\mathclose{\left(H_n(\ell ) + H_n(\ell -1) - 1 }\right) \nonumber \\ &= \frac{1}{2} h_n(\ell )\mathopen{}\mathclose{\left(2H_n(\ell ) + h_n(\ell )-1 }\right). \label{eq:32S95n40l41} \end{align}\tag{32}\] Following the work of Aldous, the random variables \(h_n(\ell )\) and \(H_{n}(\ell )\)—giving the number of vertices at level \(\ell\) and the accumulated number of vertices up to level \(\ell\), respectively—should converge to the respective quantities for the Brownian excursion. To formalize this, first extend \(h_n\) and \(H_n\) by linear interpolation to be defined on all reals in \([0,2n]\) instead of only on integers. That is, define \[h_n(t) \mathrel{\vcenter{:}}= \mathopen{}\mathclose{\left(\lfloor t\rfloor+1-t }\right)h_n\mathopen{}\mathclose{\left(\lfloor t\rfloor }\right) + \mathopen{}\mathclose{\left(t-\lfloor t\rfloor }\right)h_n\mathopen{}\mathclose{\left(\lfloor t\rfloor+1 }\right)\] for \(t \in [0,2n]\), and \(h_n(t) \mathrel{\vcenter{:}}= 0\) for \(t\notin [0,2n]\). Next, let us define \[\mu_s \mathrel{\vcenter{:}}= \int_0^1 \mathbb{1}_{\mathopen{}\mathclose{\left\{{\mathbf{e}_t \leq s}}\right\}}\, \mathrm{d}s \quad \text{and} \quad L_s \mathrel{\vcenter{:}}= \frac{\mathrm{d}}{\mathrm{d}s}\mu_s = \lim_{\epsilon \to 0}\frac{1}{\epsilon} \int_0^1 \mathbb{1}_{\mathopen{}\mathclose{\left\{{\mathbf{e}_t \in [s, s+\epsilon]}}\right\}}\,\mathrm{d}t,\] called, respectively, the occupation measure and occupation density (or local time) of \(\mathbf{e}\). It was proven by Aldous in [21] that for a tree in \(\mathcal{T}_n^{(Z)}\), \[\mathopen{}\mathclose{\left(\frac{1}{n}H_n\mathopen{}\mathclose{\left(s\sqrt{n} }\right) }\right)_{s\geq 0} \xrightarrow[\quad]{d} \mathopen{}\mathclose{\left(\mu_{\sigma s/2} }\right)_{s\geq 0},\] as processes on the set of continuous real functions on \([0,1]\), endowed with the uniform norm. It was also conjectured therein (see [21] Conjecture 4), and proven by Drmota and Gittenberger in [36], that \[\label{eq:32h95n40l4132limit} \mathopen{}\mathclose{\left(\frac{1}{\sqrt{n}}h_n\mathopen{}\mathclose{\left(s\sqrt{n} }\right) }\right)_{s\geq 0} \xrightarrow[\quad]{d} \mathopen{}\mathclose{\left(\frac{\sigma}{2}L_{\sigma s/2} }\right)_{ s\geq 0}.\tag{33}\] We now have the needed background to state the main result of this section.

7 Search in case of a known target level↩︎

In Section 4, we compared the average performance of BFS and DFS when searching for a random node at a fixed level \(\ell\), and we determined which of the two algorithms has an advantage depending on \(\ell\). However, if we know \(\ell\) in advance, it is reasonable to use a simple modification of the DFS algorithm that we call truncated DFS, which does not visit nodes at levels larger than \(\ell\).

Let us define \[\mathop{\mathrm{dfsTruncScore}}(v)\mathrel{\vcenter{:}}= \text{the number of nodes visited before v when using truncated DFS.}\] Figure 6 gives an example of a tree traversal when using truncated DFS with \(\ell=2\). Each node is labeled with its \(\mathop{\mathrm{dfsTruncScore}}\). Note that nodes at levels above \(\ell=2\) are not visited and that \(\mathop{\mathrm{dfsTruncScore}}(v)\) gives the number of steps made by the algorithm if the target is \(v\).

One can see that the truncated DFS has a smaller expected number of steps compared to both BFS and DFS. For DFS, this is immediate, since while using DFS we visit additional nodes that are skipped when using the truncated version. For BFS, observe that in any tree the nodes at level \(\ell\) have the largest bfsScores among all nodes at levels below \(\ell+1\). However, for the truncated DFS, for most of the trees, the nodes at level \(\ell\) are not those with the largest \(\mathop{\mathrm{dfsTruncScore}}\). Thus the truncated DFS is also faster than BFS on average.

Our next goal will be to prove a statement on \(\mathop{\mathrm{totalDTrunc}}(n,\ell )\) exploiting a particular symmetry, which will be used later to find the asymptotic average time complexity of the truncated DFS algorithm. Recall from Section 5 that \[F_{\ell }=\sum_{n=0}^{\infty}\sum_{T\in{\mathcal{T}}_n}x^{k(T)}y^{m(T)}z^{n},\] where \(k=k(T)\) is the number of non-root nodes in \(T\) at levels smaller than \(\ell\) and \(m=m(T)\) is the number of nodes in \(T\) at level \(\ell\).

The latter theorem implies that if we define the generating function \(D_{\ell }\) by \[\begin{align} D_{\ell }=D_{\ell }(z) & \mathrel{\vcenter{:}}=\sum_{n=0}^{\infty} \sum_{T \in \mathcal{T}_n} (m(T)-1)(n-k(T)-m(T))z^{n} \nonumber \\ & =\mathopen{}\mathclose{\left[\Bigg(z\frac{\partial^{2}}{\partial yz}-\frac{\partial^{2}}{\partial xy}-z\frac{\partial}{\partial z}+\frac{\partial}{\partial x}-\frac{\partial^{2}}{\partial y^{2}}\Bigg)F_{\ell }}\right]_{x=1,\,y=1}, \label{e-Dl} \end{align}\tag{40}\] the coefficient of \(z^{n}\) in \(D_{\ell }\) will be twice the difference between \(\mathop{\mathrm{totalD}}(n,\ell )\) and \(\mathop{\mathrm{totalDTrunc}}(n,\ell )\). One can use this expression for \(D_\ell\) to obtain an alternating summation formula for \(\mathop{\mathrm{totalDTrunc}}(n,\ell )\), as the one in Equation 30 for \(\mathop{\mathrm{totalB}}(n,\ell)\). This can be done again by a similar generating function approach to the one used in Section 5.2. We will not include this explicit \(\mathop{\mathrm{totalDTrunc}}(n,\ell )\) formula here, since the obtained expression is comprised of several complicated alternating sums, and the generating function approach is very technical. Instead, we will prove that the truncated DFS algorithm is twice as fast as BFS, in the average case, for any given level \(\ell = s\sqrt{n}\), where \(s\) is a constant.

7.1 Asymptotic complexity of the truncated DFS↩︎

Here, we find an expression (Equation@eq:eq:exact ) for the complexity of the truncated DFS algorithm, \(totalDTrunc(n,\ell)\), for any target level \(\ell\). We also evaluate this expression when \(s\) is a constant. Recall from Section 3, that \(h_n(\ell)\), \(H_n(\ell)\) and \(\nu_n(\ell)\) are denoting the number of vertices at levels \(\ell\), less or equal to \(\ell\) and greater or equal to \(\ell\), respectively. If \(N(n,\ell) := C_n\,\mathbb{E}[h_n(\ell)]\) denotes the exact total number of nodes at level \(\ell\) among trees in \(T_n\), then Theorem 1 gives \[N(n,\ell) := C_n\,\mathbb{E}[h_n(\ell)] = \frac{2\ell+1}{2n+1}\binom{2n+1}{n-\ell},\] Recall from Section 4.1 that \[\frac{\mathop{\mathrm{totalB}}(n,s\sqrt n)}{4^n} \;\longrightarrow\; B(s) := \frac{2s}{\sqrt\pi}e^{-s^2} - 2\Delta(s), \qquad n\to\infty, \label{hwaokisj}\tag{41}\] where \[\Delta(s) := \Phi(2\sqrt2\,s) - \Phi(\sqrt2\,s).\] Recall also that \[\frac{\mathop{\mathrm{totalD}}(n,s\sqrt n)}{4^n}\longrightarrow g(s):=\frac{s}{\sqrt\pi}e^{-s^2}.\] By Theorem 16, \[\begin{align} \mathop{\mathrm{totalD}}(n,\ell) - \mathop{\mathrm{totalDTrunc}}(n,\ell) &= \tfrac12\sum_{T\in T_n}\bigl(m(T)-1\bigr)\bigl(n-k(T)-m(T)\bigr) \notag\\[4pt] &= \tfrac12\,C_n\,\mathbb{E}\bigl[(h_n(\ell)-1)\,\nu_n(\ell+1)\bigr], \label{eq:thm72} \end{align}\tag{42}\] Here, we are using that \(n-k(T)-m(T)=\nu_n(\ell+1)=n+1-H_n(\ell)\), which follows directly from the definitions of \(k(T)\) and \(m(T)\) given before Theorem 16.

For a tree with \(m=h_n(\ell)\) nodes at level \(\ell\), visited in BFS order, right after all of the \(H_n(\ell-1)\) nodes at levels less than \(\ell\), we get \(H_n(\ell-1), H_n(\ell-1)+1,\dots,H_n(\ell-1)+m-1\) for the BFS scores of the nodes on level \(\ell\). Summing up and using that \(h_{n} = m\), we obtain \[S_n(\ell) = m\,H_n(\ell-1) + \binom m2 = m\bigl(H_n(\ell)-m\bigr) + \binom m2 = h_n(\ell)H_n(\ell) - \tfrac{1}{2}h_n(\ell)\bigl(h_n(\ell)+1\bigr).\] Since \(C_n\mathbb{E}[S_n(\ell)] = \mathop{\mathrm{totalB}}(n,\ell)\) by definition, then taking the expectation on both sides, multiplying by \(C_n\) and reordering leads to \[C_n\,\mathbb{E}[h_n(\ell)H_n(\ell)] \;=\; \mathop{\mathrm{totalB}}(n,\ell) + \tfrac12\,C_n\,\mathbb{E}[h_n(\ell)^2] + \tfrac12\,N(n,\ell). \label{eq:hH}\tag{43}\] Since \(\nu_n(\ell + 1) = n+1 - H_n(\ell)\), we expand the product in 42 to get \[(h_n(\ell)-1)(n+1-H_n(\ell)) = (n+1)h_n(\ell) - h_n(\ell)H_n(\ell) - (n+1) + H_n(\ell).\] Taking, again, the expectation on both sides, multiplying by \(C_n\), and using Equation 42 and Equation 43 , gives us \[\begin{align} \mathop{\mathrm{totalD}}(n,\ell)-\mathop{\mathrm{totalDTrunc}}(n,\ell) &= \tfrac12\Bigl[(n+1)N(n,\ell) - \mathop{\mathrm{totalB}}(n,\ell)\Bigr] - \tfrac14 C_n\mathbb{E}[h_n(\ell)^2] - \tfrac14 N(n,\ell) \notag\\ &-\tfrac12(n+1)C_n\;+\;\tfrac12 C_n\mathbb{E}[H_n(\ell)]. \label{eq:exact} \end{align}\tag{44}\] Let \(s>0\) be a fixed constant and let \(\ell=s\sqrt n\), \(n\to\infty\). As pointed out in the proof of Theorem 15, in this case we have \(E[h_n(s\sqrt n)] = \mathcal{O}(\sqrt{n})\) and \(E[h_n(s\sqrt n)^{2}] = \mathcal{O}(n)\). Thus, \[N(n,\ell) = C_n\,\mathbb{E}[h_n(s\sqrt n)] = \mathcal{O}(\sqrt n\,C_n)=\mathcal{O}\!\mathopen{}\mathclose{\left(\tfrac{4^n}{n}}\right),\qquad C_n\,\mathbb{E}[h_n(s\sqrt n)^2] = \mathcal{O}(n\,C_n) = \mathcal{O}\!\mathopen{}\mathclose{\left(\tfrac{4^n}{\sqrt n}}\right),\] and trivially \(C_n\mathbb{E}[H_n(\ell)]\le (n+1)C_n = \mathcal{O}(4^n/\sqrt n)\). To see the latter, recall that \(C_n \sim \frac{4^{n}}{\sqrt{\pi}n^{3/2}}\). Hence every term in 44 except the first one is \(o(4^n)\).

For that first term, the known formulas for \(N(n,\ell)\) and \(\mathop{\mathrm{totalD}}(n,\ell)\) given by Equation 1 and Equation 2 , respectively, give \[n\cdot\frac{N(n,\ell)}{\mathop{\mathrm{totalD}}(n,\ell)} = n\frac{\frac{2\ell+1}{2n+1}\binom{2n+1}{n-\ell}}{\ell\binom{2n}{n-\ell}} = \frac{n(2\ell+1)}{\ell(n+\ell+1)}\;\xrightarrow[\ell=o(n)]{}\;2, \label{eq:nN}\tag{45}\] so that \((n+1)N(n,\ell)\sim 2\,\mathop{\mathrm{totalD}}(n,\ell)\) for \(\ell=s\sqrt n\). Thus, dividing 44 by \(4^n\) and taking \(n\to\infty\) gives \[\frac{\mathop{\mathrm{totalD}}(n,\ell)-\mathop{\mathrm{totalDTrunc}}(n,\ell)}{4^n}\;\longrightarrow\; g(s) - \tfrac12 B(s). \label{eq:diff}\tag{46}\] Combining 46 with 17 results in \[g(s)-\tfrac12 B(s) = g(s) - \Bigl(g(s)-\Delta(s)\Bigr) = \Delta(s),\] so \(\mathop{\mathrm{totalD}}(n,\ell)-\mathop{\mathrm{totalDTrunc}}(n,\ell) \sim 4^n\Delta(s)\), and therefore we proved the last major result of this paper, formulated below.

8 Further questions↩︎

To conclude this paper, we present the following questions for future study.

The results in Section 6 give asymptotics for BFS on general conditioned Galton–Watson trees. It would be interesting to develop a corresponding asymptotic theory for DFS-type quantities, including ordinary DFS and truncated DFS. One possible analytic approach would be to derive functional equations for the generating functions encoding the relevant score quantities in the framework of simply generated trees; see e.g. Drmota [35]. Such a method could potentially yield asymptotic results not only for ordered trees, but also for broader classes of simply generated trees, equivalently for associated conditioned Galton–Watson trees.

There may also be a probabilistic route through the continuum random tree. For BFS-type quantities, profile and local-time convergence are sufficient, since BFS depends essentially on the number of vertices at prescribed levels and on cumulative profiles. In contrast, DFS-type quantities are sensitive to the depth-first order of the vertices. A CRT approach to ordinary DFS or truncated DFS would therefore seem to require convergence of more refined functionals of the discrete contour process, such as time-indexed measures of level upcrossings. We are not aware of such a convergence result in a directly applicable form, but it seems to be a natural direction for future work. We ask the same question for the truncated DFS algorithm, as well.

The next question is related to Section 7. In the standard implementation of BFS, we push the root into a queue. Then, we push the children of the node at the top of the queue, until we traverse all of them. Then, we pop that node and continue in the same way with the new element that is at the top. DFS is executed in the same way, but the nodes are pushed onto a stack instead of a queue. It is sensible to allow pushing nodes on both sides of a double-ended queue (deque).

We believe that truncated DFS is not only faster in expectation than both BFS and DFS, but that it is faster in expectation than any algorithm that can be implemented with a deque.

Acknowledgments↩︎

We wish to recognize and thank Luz Grisales Gómez for her involvement at the beginning stages of this project. The first author is thankful to Svante Janson for pointing out reference [21]. The same author is also indebted to George Spahn for mentioning the idea of the truncated DFS algorithm. The first author was partially supported by an AMS-Simons Travel Grant. The second author is supported by the European Union’s NextGenerationEU, through the National Recovery and Resilience Plan of the Republic of Bulgaria, project No BG-RRP-2.004-0008. The third author was partially supported by an AMS-Simons Travel Grant and NSF grant DMS-2316181. Finally, Claude Sonnet 5 was used to obtain some of the results in Section 4.1 and in Section 7.1, as well as for catching mistakes throughout the paper.

References↩︎

---

1. We note that [29] and some other sources define Fibonacci polynomials slightly differently, by taking the coefficient of \(z^n\) in \(f_{n}(z)\) to be the number of square-domino tilings of a \(1\times n\) rectangle with \(k\) squares and \((n-k)/2\) dominoes.↩︎