There are relatively well accepted standard measurements for complexity of decision trees. The complexity of a decision tree can be represented by the number of leaf nodes [1]}, [2]} or the depth of the tree [3]}, [4]}.
Since a decision tree is constructed by recursively splitting the input space and proposing a local simple model for each resulting region [5]}, the number of leaf nodes in principle uses the number of resulting regions to represent the complexity of the tree. The depth of a decision tree as the complexity measure quantifies in the worst case the number of queries needed to make a classification [4]}.
A series of studies [1]}, [2]} investigate tree optimization based on the accuracy-complexity tradeoff.
Furthermore, Buhrman and De Wolf [4]} associate the complexity of decision trees with the complexity of functions represented by certificate complexity [10]}, sensitivity complexity [11]} and approximating polynomials [12]}, and use these complexity measures of functions to bound the complexity of decision trees.
