If you use ID3 or CART for classification than any bijective transformation of the nominal variables will not alter the decision tree. If you transform also the numeric variables with keeping the ordering, the decision tree will be inferred.
You can encrypt your data given the ordinal constraint for numerical variables and infer a tree. They will have to have a mapping between any nominal label to any encoded nominal label, and between any numerical variable value to the encoded numerical value. If they have this, they can safely apply the inverted mapping to the inferred tree and get back a meaningful result.
However, some caution you must have before proceeding with this kind of things. Usually if the data is clean, you will have no problem, but if the data set is not clean (and there are pretty good chances that if they are not able to build a decision tree, they will not notice the problems, you will end up have problems also). This is what I call Garbage in, garbage out principle. As an example, they can use -999 as a missing data placeholder. Or they can even use multiple such missing data placeholders. If they encode that, you are doomed. And because the data inspection is not only a preliminary step, but a very important and essential preliminary step, there are good chances that you will en up with problems.