# Which kind of distributions can decision trees learn (well)?

Suppose I have a classification task in $$\mathbb{R}^d$$, given by a distribution $$P$$ and training data $$D$$. The decision boundary is $$B = \{x \; : \; P(Y=1|x) = P(Y=0|x)\}$$ Assume I am learning a decision tree (not a random forest) of a given depth $$k$$, trying to classify the data correctly in each leaf. The loss function is the distance to the decision boundary. Of course, it depends on the geometry of $$B$$ on how well this task can be performed. If $$B$$ can be approximated by axis-aligned cuts, we can almost perfectly learn $$B$$ using the tree.

My question: Is there research on distributional (not so much geometric) assumptions on $$P$$ that give bounds on how good the optimal tree is?