Is there an algorithm for finding an item that matches certain properties, like a 20 questions game?

Question

A question about 20 questions games was asked here:

However, if I'm understanding it correctly, the answers seem to assume that each question will go down a hierarchal branching tree. A binary tree should work if the game went like this:

1. Is it an animal? Yes.
2. Is it a mammal? Yes.
3. Is it a feline? Yes.

Because feline is an example of a mammal and mammal is an example of an animal. But what if the questions go like this?

1. Is it a mammal? Yes.
2. Is it a predator? Yes.
3. Does it have a long nose? No.

You can't branch down a tree with those kinds of questions, because there are plenty of predators that aren't mammals. So you can't have your program just narrow it down to mammal and have predators be a subset of mammals.

So is there a way to use a binary search tree that I'm not understanding or is there a different algorithm for this problem?

Just to clarify, I'm only using 20 questions as an example, so my question is about this kind of search problem in general, not other problems involved specifically in a 20 questions game.

Answer 1

It's likened to a binary search in that each question is yes/no, and so every answer partitions your remaining set into two parts. However, the data set would likely not be stored in an actual binary tree, because as you realize, that'd only work if the questions were always asked in the same order as the tree split dimension.

Also, you could easily have more than exactly 20 dimensions ('properties') on which to split things, and some set of those twenty could be shared by more than one object (so the leaf node of a 20-level binary tree wouldn't necessarily contain just one item).

Thus, the "binary search" is just a metaphor for what's actually going on, in that at each step you try to pick the property which best splits your remaining set into two equal halves. As far as actual data structures go, you'd have to use something else.