surface between $R_1$ and $R_j, 2\le j\le m$. Therefore, the time complexity to compute the surface of the tree after partitioning is $O(d^2+md)$.

If one child node belongs to the minority class and the other belongs to the majority class, the problem becomes more complicated. Let $S_{01,j}(x_j)$ be the surface of the partitioned tree if $R_1$ is partitioned at $X[j]=x_j$ and the left child is labeled as $0$ and the right child is labeled as $1$. $S_{10,j}(x_j)$ is similarly defined. Both $S_{01,j}(x_j)$ and $S_{10,j}(x_j)$ are piecewise constant functions whose change points can only exist at borders of $R_j, 2\le j\le m$. Therefore, we first compute the analytical forms of $S_{01,j}(x_j)$ and $S_{10,j}(x_j)$ for all $1\le j\le m$. This requires us to find all the borders of $R_j, 2\le j\le m$, to compute all the overlapping surface between $R_1$ and $R_j, 2\le j\le m$ and to compute the surface of $R_1$ itself. The process of computing the analytical forms of $S_{01}(x_j)$ and $S_{10}(x_j)$ for all $1\le j\le m$, takes $O(d^2+md)$ time. The cost of evaluating $S_{01,j}(x_j)$ and $S_{10,j}(x_j)$ at a specific value $x_j$ can takes as much as $O(m)$ time; but if the samples are pre-sorted for all features, it only 