Building a tree automatically from data

The Twenty Questions game is a traditional game where one of the players is the answerer who chooses an object (or a famous person in some variants), not revealing what it is to the other participants. All the other players are trying to guess what the object is by asking questions like Can I eat this? or Is it a human? where answers can only be yes or no.

If you have never heard about this game, refer to Wikipedia: https://en.wikipedia.org/wiki/Twenty_Questions.

This is essentially a tree learning algorithm. To win in a game, you should pose such questions that discriminate the most; for example, the question, Is it alive? in the beginning of the game is clearly better than Is it a cucumber?. This ability to dissect the hypothesis space in an optimal way is formalized in the notion of information gain criterion.