We consider the average time complexity of breadth-first search (BFS) and depth-first search (DFS), when we have a uniformly random target node selected among all nodes at level m in all ordered trees with n edges. Intuition suggests that for a fixed n, BFS should have better average performance when m is small, while DFS must have an advantage when m is large. But where exactly is the threshold, for m as a function of n, and is it unique?

We answer this question by using results on the occupation measure of Brownian excursions and an identity related to lattice paths. 

At the end we ask some interesting further questions.