Summary: It has been shown that there exists a transition in the average-case complexity of tree search problems, from exponential to polynomial in the search depth. We develop a new method, called \(\varepsilon\)-transformation, which makes use of this complexity transition, to find a suboptimal solution. With a random tree model, we show that, as the tree depth approaches infinity, the expected number of nodes expanded by branch-and-bound (BnB) using \(\varepsilon\)-transformation is at most cubic in the search depth, and that the relative error of the solution cost found with respect to the optimal solution cost is bounded above by a small constant. We also present an iterative version of \(\varepsilon\)-transformation that can be used to find both suboptimal and optimal goal nodes. Depth-first BnB (DFBnB) using iterative \(\varepsilon\)-transformation significantly improves upon DFBnB on random trees with large branching factors and deep goal nodes, finding a better solution sooner. We then present experimental results for \(\varepsilon\)-transformation and iterative \(\varepsilon\)-transformation on the asymmetric traveling salesman problem (ATSP) and the maximum Boolean satisfiability problem, and identify the conditions under which these two methods are effective. On the ATSP, DFBnB using \(\varepsilon\)-transformation outperforms a well-known local search method, and DFBnB using iterative \(\varepsilon\)-transformation improves upon DFBnB.