Tree models are among the most popular representations in machine learning.
In particular, decision trees [1]}, [2]} are models of paramount importance
in XAI, as they can be easily read by recursively breaking a choice into sub-choice until a decision is reached.
Formally, a (Boolean) decision tree is a binary tree \(T\) , where each internal node is labeled with a Boolean variable
in \(\mathcal {X}_n\) , and each leaf is labeled 0 or 1. Without loss of generality, every variable is assumed to appear
at most once on any root-to-leaf path (this is called the read-once property). The value \(T(\mathbf {x})\)  of \(T\)  on
an input instance \(\mathbf {x} \in \mathbb {B}^n\)  is given by the leaf reached from the root as follows: for each internal node
labeled by \(x_i\) , go to the left or right child depending on whether the corresponding value \(x_i\)  of \(\mathbf {x}\)  is 0 or 1, respectively.
The size of \(T\)  is given by the number of its nodes.
