Why decision tree needs categorical variable to be encoded?
...why is encoding needed on categorical variables?


That isn't true; decision trees can be built on both continuous and categorical features.  (Why don&#39;t tree ensembles require one-hot-encoding? )  Some implementations, however, do not support categorical variables (notably sklearn (for now, update) and xgboost (their politics)).

Now, there is a question of efficiency: the number of bipartitions of the set of categories is exponential in the number of categories, so a complete search of the possible splits is only practical for categorical variables with few categories.
There turns out to be a (surprising?) simplification though: if the underlying problem is a regression with MSE, or a binary classification with cross-entropy or Gini index, then the optimal split can be found by ordering the categories according to their average response value and treating it now as an ordinal variable split.  (That said, still having many categories, especially small ones, might lead to heavy overfitting.)  See Elements of Statistical Learning, section 9.2.4.

Some implementations perform the exhaustive bipartition search but cap the number of categories allowed.  LightGBM and rpart perform the ordered search.  (some R discussion, LightGBM).