  We consider the problem of collaborative tree exploration posed by
Fraigniaud, Gasieniec, Kowalski, and Pelc where a team of $k$ agents is tasked
to collectively go through all the edges of an unknown tree as fast as
possible. Denoting by $n$ the total number of nodes and by $D$ the tree depth,
the $\mathcal{O}(n/\log(k)+D)$ algorithm of Fraigniaud et al. achieves the
best-known competitive ratio with respect to the cost of offline exploration
which is $\Theta(\max{\{2n/k,2D\}})$. Brass, Cabrera-Mora, Gasparri, and Xiao
consider an alternative performance criterion, namely the additive overhead
with respect to $2n/k$, and obtain a $2n/k+\mathcal{O}((D+k)^k)$ runtime
guarantee. In this paper, we introduce `Breadth-First Depth-Next' (BFDN), a
novel and simple algorithm that performs collaborative tree exploration in time
$2n/k+\mathcal{O}(D^2\log(k))$, thus outperforming Brass et al. for all values
of $(n,D)$ and being order-optimal for all trees with depth $D=o_k(\sqrt{n})$.
Moreover, a recent result from Disser et al. implies that no exploration
algorithm can achieve a $2n/k+\mathcal{O}(D^{2-\epsilon})$ runtime guarantee.
The dependency in $D^2$ of our bound is in this sense optimal. The proof of our
result crucially relies on the analysis of an associated two-player game. We
extend the guarantees of BFDN to: scenarios with limited memory and
communication, adversarial setups where robots can be blocked, and exploration
of classes of non-tree graphs. Finally, we provide a recursive version of BFDN
with a runtime of $\mathcal{O}_\ell(n/k^{1/\ell}+\log(k) D^{1+1/\ell})$ for
parameter $\ell\ge 1$, thereby improving performance for trees with large
depth.
