Since decision tree algorithm splits the training dataset one feature at a time, how the heck is possibly that it suffers from curse of dimensionality ?
Every machine learning algorithm suffers from curse of dimensional to different degrees. The primary issue is the sparsity of observations as the number of dimensions increase.
Since decision trees are greedy, they are one of the most robust machine learning algorithms to sparsity. Decision trees will automatically find the single feature to that best creates the most pure regions. This process is recursively repeated. Decision trees will learn to ignore dimensions that are less informative.