Can decision stumps have more than 2 leaves? I understand decision stump: a shallow 1-level decision tree is often used as base-leaner in ensemble methods such as AdaBoost. What is not immediately clear to me is using such ensemble methods in multi-class classification task.
Can a decision stump have more than 2 leaves? Or each decision stump picks only 2-classes of the multi-class and fits model on?
I want to understand how decision stump works in a multiclass classification task. Which of this illustrations (my drawing) describe how it works (3-class problem for instance)?

 A: You used the tag cart; CART trees always use binary splits.  However, the Quinlan family of decision tree algorithms support multiple-arity splits for categorical features, and such a stump could be used as the base learner for AdaBoost.
However, that doesn't say anything about multiclass targets.  All trees support multiclass problems, by using a version of impurity measures that take into consideration multiple classes.  Each node contains a subset of your training set, and we record the number in each class.  The final class prediction is still just the majority class in a leaf, so a CART stump will predict at most 2 classes (but across the AdaBoost ensemble, probably all of the classes will eventually show up).  For example, a stump for the iris dataset (using just two features to keep it from being too good a split to be instructive):

The left leaf contains a large majority from the first class, so a row with first feature <=5.45 would be classified as the first class.  The right leaf contains nearly an even split between the second and third classes, but with the third class slightly more prevalent, and so predictions there will be the third class.  This leaves the second class un-predicted, so all of its examples are misclassified, and AdaBoost will increase its focus on them in future trees.
The trees can also produce "soft" predictions, the proportion of samples in a leaf for each class; this is done for random forests, but not in AdaBoost to my knowledge, since the reweighting uses information about the misclassified examples.  (In the example above, the right leaf would predict probabilities of 5/98, 44/98, and 49/98.)
All that said, you could produce multiple binary models in either a one-vs-one or one-vs-rest fashion if desired instead of relying on the trees' internal multiclass approach.
A: @Ben Reiniger has a more complete answer with lots of useful details about random forests; definitely read that first.
I, on the other hand, want to elaborate on one single point: each decision in a tree-based model splits examples according to a single feature.
Consider the following example: we have n continuous features Xi and a categorical response with three levels y1, y2, y3. At each split the model chooses feature Xi and comes up with a decision rule such as:

If Xi < some number x, then the example belongs to the left child of the root. If Xi $\geq$ x, then it belongs to the right child.

What would a three-way split look like?

If Xi < some number x1, go left; if Xi is between x1 and x2, go in the middle; if Xi $\geq$ x2 then go right.

You suggest that since the target has three levels, three-way splits might be more appropriate. However:

*

*Three-way splits are more complex to estimate: we need to find two cutoff values x1 and x2 instead of just one x by optimizing a metric such as impurity.

*One three-way split is equivalent to two consecutive two-way splits so a tree-based model with binary decisions is just as flexible.

*There is no guarantee that any given feature Xi separates all three classes from each other. (Maybe both y1 and y2 instances tend to have low Xi and only y3 instances tend to have high Xi).

