Drzewo decyzyjne to reprezentacja funkcji, która odwzorowuje wektor wartości atrybutów na pojedynczą wartość wyjściową — „decyzję”. Drzewo decyzyjne podejmuje decyzję, wykonując sekwencję testów, zaczynając od korzenia i podążając za odpowiednią gałęzią, aż do osiągnięcia liścia. Każdy węzeł wewnętrzny w drzewie odpowiada testowi wartości jednego z atrybutów wejściowych, gałęzie z węzła są oznaczone możliwymi wartościami atrybutu, a węzły liści określają, jaka wartość ma zostać zwrócona przez funkcję. Ogólnie rzecz biorąc, wartości wejściowe i wyjściowe mogą być dyskretne lub ciągłe, ale na razie rozważymy tylko dane wejściowe składające się z wartości dyskretnych i wartości wyjściowych, które są albo prawdziwe (przykład pozytywny), albo fałszywe (przykład negatywny). Nazywamy to klasyfikacją Boole’a. Użyjemy j do indeksowania przykładów (xj jest wektorem wejściowym dla j-tego przykładu, a yj jest wyjściem), a xj,i dla i-tego atrybutu j-tego przykładu. Drzewo reprezentujące funkcję decyzyjną używaną przez SR do problemu restauracji pokazano na rysunku.
Podążając za gałęziami widzimy, że przykład z Patrons=Full i WaitEstimate=0–10 zostanie sklasyfikowany jako pozytywny (tzn. tak, poczekamy na stolik)