Yes/no questions that sort: decision trees

Guess which animal I am thinking of — you may only ask yes/no questions.

Does it have fur?
├─ yes: Does it say meow?
│       ├─ yes: CAT
│       └─ no:  DOG
└─ no:  Can it fly?
        ├─ yes: BIRD
        └─ no:  FISH

That is a decision tree. Every question splits the pile in two. Computers build trees like this automatically from examples — one of the oldest kinds of machine learning.

Good question or bad one? With the animals cat, dog, bird, fish:

• «Does it have fur?» splits 2–2. Good.
• «Is it a cat?» splits 1–3. Worse — you need more questions afterwards.

The best question is the one that splits the pile as evenly as possible. Build a tree for four fruits (banana, apple, strawberry, orange). How few questions can you manage with? (Two are enough for four things if every question splits evenly.)