 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\ge \lceil {\log }_{2}N\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.