"The point is that once you have an optimal tree, you can find the questions that work"

I am not sure this assumption is true, unless you allow questions like:

Is it in the group 'cow, fish, chicken, rhinoceros, amoeba, phoenix, suckling pigs, Those that tremble as if they were mad?

If we are limited to more normal questions such as 'Does it live in water', 'Is it a mammal' Then will we always be able to find a question to divide each set of candidates? It looks like you are going to need to analyse all questions asked before and find the ones that split the list of all animals most optimally for your tree, probably adapting the tree to fit the possible questions as you go. Or interface to Wikipedia and get real AI like.

Cheers,
R.