A 'secret weapon' that has served me very well for learning classifiers is to first learn a good linear classifier. I am almost hesitant to give this away (kidding).

Use the non-thresholded version of that linear classifier output as one additional feature-dimension over which you learn a decision tree. Then wrap this whole thing up as a system of boosted trees (that is, with more short trees added if needed).

One of the reasons why it works so well, is that it plays to their strengths:

(i) Decision trees have a hard time fitting linear functions (they have to stair-step a lot, therefore need many internal nodes) and

(ii) linear functions are terrible where equi-label regions have a recursively partitioned structure.

In the decision tree building process the first cut would usually be on the synthetic linear feature added, which would earn it the linear classifier accuracy right away, leaving the DT algorithm to work on the part where the linear classifier is struggling. This idea is not that different from boosting.

One could also consider different (random) rotations of the data to form a forest of trees build using steps above, but was usually not necessary. Or rotate the axes so that all are orthogonal to the linear classifier learned.

One place were DT struggle is when the features themselves are very (column) sparse, not many places to place the cut.