0
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ Welcome to DataScienceSE. Is this homework? If so please show your work and/or explain your difficulty. $\endgroup$
    – Erwan
    Apr 28, 2022 at 15:11
  • $\begingroup$ 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. $\endgroup$ Apr 28, 2022 at 20:12
  • $\begingroup$ 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. $\endgroup$
    – Erwan
    Apr 28, 2022 at 21:53
  • $\begingroup$ 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. $\endgroup$ Apr 29, 2022 at 19:31
  • $\begingroup$ Yes, that's correct. Also you know the max depth because it depends on the number of features. $\endgroup$
    – Erwan
    Apr 29, 2022 at 21:39

2 Answers 2

0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    May 4, 2023 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.