A decision tree is similar to a 1-decision list, except now we allow the single literal decision conditions to be placed in a binary tree, with the decisin bits placed only at the leaves. To evaluate such a tree T on a input of a eplision {0,1)^n, we follow the path through T defined by starting at the root T and evaluating the literal at each node on input a, going left if the evaluation yields 0 and right if ti yields 1. The value T(a) is the bit value stored at the leaf reached by this path.