the rest of the paper, the word “tree” refers specifically to classification trees that specify a class label associated with each leaf node.

Notations
---------

Training data are denoted as $\mathscr{D}_n = \{(X_i, Y_i)\}_{i=1}^n$, with $X_i \in \Omega \subset \mathbb{R}^d$ a vector of features and $Y_i \in \{0,1\}$ a class label. Uppercase letters $(X, Y)$ denote random variables, while lowercase $x, y$ denote specific values. We denote the $j$th feature of $X$ as $X[j]$. The true distribution of $(X_i, Y_i)$ is denoted by $\mathbb{P}$, while the empirical distribution, which assigns mass $1/n$ to each training data point, is denoted by $\mathbb{P}_n$. For a constant $\alpha>1$, let $\mathbb{P}_\alpha$ modify $\mathbb{P}$ to up weight minority class samples by $\alpha$. That is, for any subset $A\subset \Omega$, $$\mathbb{P}_\alpha(A\times\{1\}) = \frac{\alpha\mathbb{P}(A\times\{1\})}{\mathbb{P}(\Omega\times\{0\})+\alpha\mathbb{P}(\Omega\times\{1\})}, \;\; \;\mathbb{P}_\alpha(A\times\{0\}) = \frac{\mathbb{P}(A\times\{0\})}{\mathbb{P}(\Omega\times\{0\})+\alpha\mathbb{P}(\Omega\times\{1\})}.$$ Similarly, let $\mathbb{P}_{n,\alpha}$ be the weighted version of $\mathbb{P}_n$. To avoid complex subscripts, with some abuse of notation, we also use $\mathbb{P}, \mathbb{P}_\alpha, \mathbb{P}_n, \mathbb{P}_{n,\alpha}$ to denote the corresponding marginal probability measures on $X$. For example, $$\mathbb{P}_\alpha(A) \triangleq \mathbb{P}_\alpha(A\times\{0,1\}) = \frac{\mathbb{P}(A\times\{0\})+\alpha\mathbb{P}(A\times\{1\})}{\mathbb{P}(\Omega\times\{0\})+\alpha\mathbb{P}(\Omega\times\{1\})}.$$ Whether they refer to the joint distribution of $(X, Y)$ or the marginal distribution of $X$ should be clear from the context. When discussing the probability of certain 