Intersection of Decision Tree Boundaries in Higher Dimensions
Yuval Filmus has articulated an elegant solution, which I'll expand on.
Given a leaf of a decision tree, it is easy to characterize the set of values of $x$ that reach that leaf.  Namely, you take the conjunction of all the conditions along the path from the root to the leaf.  For trees of the form you list, this will have the form $[\ell_1,u_1] \times \cdots \times [\ell_4,u_4]$, i.e., the set of all $x$ such that $\ell_1 \le x_1 \le u_1 \land \cdots \land \ell_4 \le x_4 \le u_4$, where you can explicitly compute $\ell_1,\dots,\ell_4,u_1,\dots,u_4$.
Now apply the following algorithm:

For each pair of leaves, with one leaf in the first tree and the other leaf in the second tree, such that the two leaves lead to different classifications:

Compute the set of values $x$ that reach the first leaf, the set of values $x$ that reach the second leaf, and compute their intersection.  Output the intersection (this is one set of points where the decision trees differ).



The union (i.e., disjunction) of all of those outputs will be the complete set of points where the two trees give a different decision.

It is possible to come up with algorithms that might be faster; however, I'm not sure whether they will lead to a significant improvement in higher dimensions.
One approach is to construct a new tree via a &quot;product construction&quot;.  Thus, each node in the new tree is a pair $(u,v)$, where $u$ is a node in your first tree and $v$ is a node in your second tree.  The root of the tree is $(r_1,r_2)$, where $r_1$ is the root of your first tree and $r_2$ is the root of your second tree.  You can build the new tree top-down, starting from $(r_1,r_2)$, then splitting using the condition at one of these two nodes ($r_1$ or $r_2$).  As you build the tree, keep track of the set of values that can reach each new node $(u,v)$.  If this set is empty, you can prune it and don't need to explore any of its children.  This might reduce the number of nodes you need to expand.  In the worst case, there is no speedup, but in practice, it might help a little.

It gets more interesting if each classifier is an ensemble/forest of trees; then the best solution would probably be to use a SMT solver.