(Newbie) Decision Tree Randomness
From sklearn:


  The features are always randomly permuted at each split. Therefore, the best found split may vary, even with the same training data and max_features=n_features, if the improvement of the criterion is identical for several splits enumerated during the search of the best split. To obtain a deterministic behaviour during fitting, random_state has to be fixed.


If you manually set the random_state variable when you create your tree object, you'll find that it does become deterministic.  

In simpler terms, the data you are feeding it is a little small, and there are several splits that have the same information gain, so the split that is chosen is subject to random factors.