  We consider the following generalization of the binary search problem. A
search strategy is required to locate an unknown target node $t$ in a given
tree $T$. Upon querying a node $v$ of the tree, the strategy receives as a
reply an indication of the connected component of $T\setminus\{v\}$ containing
the target $t$. The cost of querying each node is given by a known non-negative
weight function, and the considered objective is to minimize the total query
cost for a worst-case choice of the target. Designing an optimal strategy for a
weighted tree search instance is known to be strongly NP-hard, in contrast to
the unweighted variant of the problem which can be solved optimally in linear
time. Here, we show that weighted tree search admits a quasi-polynomial time
approximation scheme: for any $0 \textless{} \varepsilon \textless{} 1$, there
exists a $(1+\varepsilon)$-approximation strategy with a computation time of
$n^{O(\log n / \varepsilon^2)}$. Thus, the problem is not APX-hard, unless $NP
\subseteq DTIME(n^{O(\log n)})$. By applying a generic reduction, we obtain as
a corollary that the studied problem admits a polynomial-time $O(\sqrt{\log
n})$-approximation. This improves previous $\hat O(\log n)$-approximation
approaches, where the $\hat O$-notation disregards $O(\mathrm{poly}\log\log
n)$-factors.
