We consider the problem of building a binary decision tree, to locate an object
within a set by way of the least number of membership queries. This problem
is equivalent to the "20 questions game'' of information theory and is closely
related to lossless source compression. If any query is admissible, Huffman
coding is optimal. However, in many realistic scenarios, there are constraints
on which queries can be asked, and solving the problem optimally is NP-hard.
We
provide  novel polynomial time approximation algorithms where constraints are
defined in terms of "graph", general "cost", and "submodular" functions.