Would infinitely deep decision tree on a binary classification task guarantee to achieve 100% accuracy?

Question

Would then infinitely deep decision tree on a binary classification task guarantee to achieve 100% accuracy on a training set with N examples such that there is no examples with the same feature values, but a different class label?

Answer 1

Yes, it's possible to create a decision tree like this. It wouldn't need to be infinitely deep, either - just ceil(log(2, N)) levels deep, where N is the number of examples. Assuming that each training example had a unique set of feature values, then the model could get 100% accuracy.

However, a decision tree like this would probably generalize pretty poorly. The model is essentially memorizing each training example. The accuracy on examples that were not part of the original training set would likely be pretty bad. That's one reason why decision tree models typically either set a minimum split size (e.g. don't split any leaves with less than 10 examples) or use a random forest, which train many different trees and average their predictions.