I can reproduce this problem for an even more easily separable dataset:
The ideal tree for it should be as follows:
However, when I run DecisionTreeClassifier with the maximal depth = 2 in scikit-learn many times, it splits the dataset randomly and never gets it right.
This is an example of 4 different runs:
The problem is that scikit-learn has only two ...