# What is the max number of leaf nodes in a classifcation decision tree?

Let's assume that we have n observations and p predictors and we have in a n>>p situation. All predictors are binary. What is the max number of leaf nodes that we can have in the tree? and what are the maximal number of internal nodes? What is the math behind this, can someone offer some insight?

• Welcome to DataScienceSE. Is this homework? If so please show your work and/or explain your difficulty. Apr 28, 2022 at 15:11
• it is a mock exam question. To be honest I don't know how many leaves a decision tree should have, there is no right answer as the tree is generated using different algorithm and different parameters so all trees will be different. This is my understanding. Apr 28, 2022 at 20:12
• The question doesn't depend on which algorithm, it depends only on general properties of decision trees. Remember that every internal node is made of a condition on a particular feature, and since the features are binary there are exactly two branches under each internal node. Using this you can obtain the max depth of a tree and then the answers. Apr 28, 2022 at 21:53
• if I consider the root as dept zero the max leaves that it can have will be will be 2 to the power of the depth. So a tree with depth 2 will have max 4 leaves. Apr 29, 2022 at 19:31
• Yes, that's correct. Also you know the max depth because it depends on the number of features. Apr 29, 2022 at 21:39

Since all predictors are binary, each predictor can either be 0 or 1. Ergo, the maximum number of leaf nodes is equal to the total number of unique combinations of the predictors.

The formula therefore is 2^p

The maximum possible number of leaf nodes is the total number of samples (n). This will occur when all the samples are classified in a different leaf node, a case of overfitting.