= Binary decision tree
A <binary decision tree> represents a procedure whose internal nodes ask two-outcome questions and whose leaves specify results. A path records the answers obtained so far; its length counts the questions on that execution. Distinguishing $N$ possibilities requires at least $N$ leaves, so a depth-$d$ <binary tree> can distinguish at most $2^d$ outcomes. This gives $d\geq\lceil\log_2N\rceil$ for an exact worst-case identification problem. The bound relies on the questions really having only two outcomes; comparisons with an equality branch need a stated convention.
Back to article page
