Here is a suggestion of how the Bayesian CART model from Hu et al (2011) might be implemented in WinBUGS. This method requires you to fix the tree depth in advance. Given a complete binary tree, any node at depth 1 (i.e. children of the root) can be identified by an indicator $b_1$. Any node at depth 2 can be identified by a pair of indicators $(b_1,b_2)$. And so on. Let $x[i,v]$ be the $v$th predictor variable in the $i$th instance. We can encode the path through the tree by thresholding $x[i,v]$ according to the parameters of the chosen node at each depth. This code works for trees of depth 3:
for(i in 1:n) {
b1[i] <- 1 + step(x[i,variable1] - split1)
b2[i] <- 1 + step(x[i,variable2[b1[i]]] - split2[b1[i]])
b3[i] <- 1 + step(x[i,variable3[b1[i],b2[i]]] - split3[b1[i],b2[i]])
y[i] ~ dnorm(mean[b1[i],b2[i],b3[i]], prec[b1[i],b2[i],b3[i]])
}
You just need to add appropriate priors for $variable$ (the splitting variable at each node), $split$ (the splitting threshold at each node), and $(mean, prec)$ of the leaves. There are 8 possible leaves, but they need not all be used. For example, if one of the splits is outside the range of the data then it effectively prunes away part of the tree. You could encourage such pruning with an appropriate prior on splits.
for
loops and do much more programming (BUGS does not), so if I would to try to implement what Tom Minka suggests below, I wouldn't even bother with BUGS and use Stan from the beginning. However, I didn't ever try this kind of models in Stan so sorry I am unable to tell you more. Try the Stan users mailing list: groups.google.com/forum/#!forum/stan-users $\endgroup$