BFS versus DFS for fixed-level targets in ordered trees

Stoyan Dimitrov, Martin Minchev, Yan Zhuang

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…