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
- Martin Minchev (ORCID: https://orcid.org/0000-0003-1647-9338)
- Yan Zhuang (ORCID: https://orcid.org/0000-0001-7351-377X)
- Stoyan Ivanov Dimitrov (ORCID: https://orcid.org/0000-0002-5265-0289)
Institutions
- Dartmouth College (US)
- Davidson College (US)
- Sofia University "St. Kliment Ohridski" (BG)
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
- National Science Foundation
- European Commission