  We study quantum algorithms on search trees of unknown structure, in a model
where the tree can be discovered by local exploration. That is, we are given
the root of the tree and access to a black box which, given a vertex $v$,
outputs the children of $v$.
  We construct a quantum algorithm which, given such access to a search tree of
depth at most $n$, estimates the size of the tree $T$ within a factor of $1\pm
\delta$ in $\tilde{O}(\sqrt{nT})$ steps. More generally, the same algorithm can
be used to estimate size of directed acyclic graphs (DAGs) in a similar model.
  We then show two applications of this result: a) We show how to transform a
classical backtracking search algorithm which examines $T$ nodes of a search
tree into an $\tilde{O}(\sqrt{T}n^{3/2})$ time quantum algorithm, improving
over an earlier quantum backtracking algorithm of Montanaro (arXiv:1509.02374).
b) We give a quantum algorithm for evaluating AND-OR formulas in a model where
the formula can be discovered by local exploration (modeling position trees in
2-player games). We show that, in this setting, formulas of size $T$ and depth
$T^{o(1)}$ can be evaluated in quantum time $O(T^{1/2+o(1)})$. Thus, the
quantum speedup is essentially the same as in the case when the formula is
known in advance.
