BFS versus DFS for Fixed-Level Targets in Ordered Trees

Abstract. We find the average time complexity of the breadth-first search (BFS) and the depth-first search (DFS) algorithms, when one searches for a target node selected uniformly at random among all nodes at level [Formula: see text] in the set of ordered trees with [Formula: see text] edges. Intuition suggests that on average BFS must be asymptotically faster than DFS if and only if [Formula: see text], as a function of [Formula: see text], is below a certain threshold. We confirm this intuition by showing that there exists a unique constant [Formula: see text], such that in expectation BFS is asymptotically faster than DFS if and only if [Formula: see text]. This gives us a practical rule to select between the two algorithms, even when we do not know the exact value of [Formula: see text], but only an estimate of it. Furthermore, we find the asymptotic average time complexity of BFS in the given setting for an arbitrary class of Galton–Watson trees, which includes ordered trees, binary trees, and other popular classes. We use results on the occupation measure of Brownian excursions, as well as combinatorial identities related to lattice paths. Finally, we consider the simple truncated DFS algorithm, which can be shown easily to be asymptotically faster than both BFS and DFS when [Formula: see text] is known in advance. We show that in fact its asymptotic time complexity is [Formula: see text] of the asymptotic complexity of BFS, when [Formula: see text] for any constant [Formula: see text]. Several further questions are also raised.

Authors

Institutions

Publication Details

Journal
SIAM Journal on Discrete Mathematics
Published
2026-11-13
DOI
https://doi.org/10.1137/25m1760891
Citations
1
Primary Topic
Stochastic processes and statistical mechanics
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

BFS versus DFS for Fixed-Level Targets in Ordered Trees

Martin Minchev, Yan Zhuang, Stoyan Ivanov Dimitrov
1 citations
SIAM Journal on Discrete Mathematics
Stochastic processes and statistical mechanics
article

BFS versus DFS for Fixed-Level Targets in Ordered Trees

Martin Minchev, Yan Zhuang, Stoyan Ivanov Dimitrov
article en
1 citations

Abstract

Abstract. We find the average time complexity of the breadth-first search (BFS) and the depth-first search (DFS) algorithms, when one searches for a target node selected uniformly at random among all nodes at level [Formula: see text] in the set of ordered trees with [Formula: see text] edges. Intuition suggests that on average BFS must be asymptotically faster than DFS if and only if [Formula: see text], as a function of [Formula: see text], is below a certain threshold. We confirm this intuition by showing that there exists a unique constant [Formula: see text], such that in expectation BFS is asymptotically faster than DFS if and only if [Formula: see text]. This gives us a practical rule to select between the two algorithms, even when we do not know the exact value of [Formula: see text], but only an estimate of it. Furthermore, we find the asymptotic average time complexity of BFS in the given setting for an arbitrary class of Galton–Watson trees, which includes ordered trees, binary trees, and other popular classes. We use results on the occupation measure of Brownian excursions, as well as combinatorial identities related to lattice paths. Finally, we consider the simple truncated DFS algorithm, which can be shown easily to be asymptotically faster than both BFS and DFS when [Formula: see text] is known in advance. We show that in fact its asymptotic time complexity is [Formula: see text] of the asymptotic complexity of BFS, when [Formula: see text] for any constant [Formula: see text]. Several further questions are also raised.

SIAM Journal on Discrete MathematicsVol. 40(4)
Dartmouth College (US), Davidson College (US), Sofia University "St. Kliment Ohridski" (BG)
National Science Foundation, European Commission
Stochastic processes and statistical mechanics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon