why do decision tree packages convert factor variable into two binary variables Why are decision tree packages like say, rpart slow with increasing the number of factor levels in R. 
I read that it basically converts each factor variable into two binary variables representing 0/1 as it prepares the model matrix. But why is that needed? Can't it just keep it as a category and carry on creating a tree structure?
Isn't that what decision tree is supposed to do?
 A: The factor variables are always kept as factor variables. But many of the implementations (by default) use only binary splits rather than multiway splits because this typically yields smaller trees, especially if the factor has many categories. The cost for this is that it is computationally burdensome to search over all splits into two groups of k categories. This grows exponentially in k.
The search can be simplified if the k factor levels are ordered, then the search complexity grows only linearly in k.
For certain types of responses and loss functions, an ordering of the levels can always be used, thus simplifying the search. But as this is not possible for all types of responses (to the best of my knowledge), most R packages do not exploit this simplification.
If you have prior knowledge which splits are likely to yield improvements, then you can supply the simplified factors. For example, if you have a factor "ethnicity" with levels Caucasian, African-American, Asian-American, Hispanic, Other, then it might make sense to use a factor "minority" with levels yes and no instead.
