Decision Tree - Preprocessing for very sparse features
There are many feature engineering options for sparse categorical data. A couple of common options:

Remove features - Drop columns that are sparse
Feature reduction - One example is singular value decomposition (SVD)
Reduce number of categories - Using domain knowledge, group together related low frequency categories
Use sparse representation - only stores nonzero elements