[imtringued]

The solver only has to enumerate every optimal solution.

If you found any optimal solution, you already have the optimal upper and lower bound and therefore you're just iterating through the tree and comparing against the problem relaxation at that point. The worst case scenario for finding multiple solutions is that every solution is optimal but the worst case for a single solution is that you cannot save any work and must check every solution. In other words: the worst case never changes. The algorithm does not get worse in terms of complexity.