Using oracle machine to speed up tree solution search
Here is an algorithm that will work in some cases: guess the first $n-k$ bits of the solution; fix them; and then solve the sub-problem where you ask what the remaining $k$ bits are.  In other words, iterate over all $2^{n-k}$ possibilities for the first $n-k$ bits, and for each such choice, use your oracle to find the remaining $k$ bits.

This works assuming fixing some bits of the problem leads to a sub-problem of the sort that can be solved by your oracle.



(I'm also assuming you can verify whether a candidate solution is correct in $O(1)$ time, you can find a correct solution in $O(2^{n-k})$ steps.  This seems to be required to achieve your $O(2^n)$ running time for tree search.  If the problem is in NP, then there's a way to verify in polynomial time, so instead of $O(2^{n-k})$ you have $O(2^{n-k} \cdot \text{poly}(n))$.)