A binary decision tree is a graph that uses a set of boolean tests t1, t2, .. tm to classify a set of objects x1, x2, .. x3 into correct categories. Each object has corresponding boolean value for each test as well as a correct classification. For example, suppose our objects are mushrooms and we want to tell whether or not they are poisonous. We have the following set of mushrooms:

Mushroom Spotted Yellow Smelly Poisonous T1 T2 T3 T4 T5 T7 T8 We have the following three tests: isSpotted, is Yellow, isSmelly and the following two cate- gories: Poisonous, Not Poisonous. We can use these and our observations to construct the following tree: is Spotted isSmelly isY ellow Poisonous isYellouw Poisonous Not Poison ous Poisonous Not Poisonous