  We consider the following generalization of binary search in sorted arrays to
tree domains. In each step of the search, an algorithm is querying a vertex
$q$, and as a reply, it receives an answer, which either states that $q$ is the
desired target, or it gives the neighbor of $q$ that is closer to the target
than $q$. A further generalization assumes that a vertex-weight function
$\omega$ gives the query costs, i.e., the cost of querying $q$ is $\omega(q)$.
The goal is to find an adaptive search strategy requiring the minimum cost in
the worst case. This problem is NP-complete for general weight functions and
one of the challenging open questions is whether there exists a polynomial-time
constant factor approximation algorithm for an arbitrary tree? In this work, we
prove that there exist a constant-factor approximation algorithm for trees with
a monotonic cost function, i.e., when the tree has a vertex $v$ such that the
weights of the subsequent vertices on the path from $v$ to any leaf give a
monotonic (non-increasing or non-decreasing) sequence $S$. This gives a
constant factor approximation algorithm for trees with cost functions such that
each such sequence $S$ has a fixed number of monotonic segments. Finally, we
combine several earlier results to show that the problem is NP-complete when
the number of monotonic segments in $S$ is at least $4$.
