Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I know that it doesn’t have to be balanced so in theory given that the height of the tree is $h$, the minimal number of nodes is obtained when each node has 1 key and 1 child, and since the first level "doesn’t count" in the height, I should have $h+1$ nodes.
The maximal number of nodes in a $M-way- tree$ should be $\Sigma^h_{i=0} M^i$, when $i$ is the tree level.
Is this correct ? Thank you!
This looks correct.
Note that the sum of the geometric series can be expressed more concisely:
$$\sum\limits_{i = 0}^{h} M^{i} = \frac{M^{h + 1} - 1}{M - 1}$$
