My understanding of this stuff is pretty basic so my semantics may be off, but bare with me.
XGBoost and other gradient descent packages make the best possible split of the data right off the bat. Then with that subset of data, make the best possible split again. But what if the best possible tree is full of splits that require other splits to work?
For example, imagine there was this best possible perfect tree. But the first split on its own would be awful, and the second split on its own would be awful as well, BUT when you apply the second split to one of the subsets from the first split, it works really well?
Gradient descent would never explore this possibility, where each split on its own doesn't work but when you combine them its really effective.
The only way to find this "perfect" tree of splits would be some sort of genetic algorithm to make the trees that just tries weird stuff and sees if it is good?