Default implementations of Bayesian Additive Regression Trees (BART) represent categorical predictors using several binary indicators, one for each level of each categorical predictor. Regression trees built with these indicators partition the levels using a “remove one a time strategy.” Unfortunately, an overwhelming majority of partitions of the levels cannot be built with this strategy, severely limiting BART’s ability to “borrow strength” across groups of levels. We overcome this limitation with a new class of regression trees built around decision rules based on linear combinations of these indicators. Motivated by spatial applications with areal data, we introduce a further decision rule prior that partitions the areas into spatially contiguous regions by deleting edges from random spanning trees of a suitably defined network. We implemented our new regression tree priors in the flexBART package, which, compared to existing implementations, often yields improved out-of-sample predictive performance without much additional computational burden. We will conclude by describing how the flexBART implementation can be further extended to fit BART models over much more general input spaces.