My problem is a little complex to explain because I'm not a english native speaker and I don't know the word in this matter, but I will try to explain it. If you think you have keyword to help me, don't hesitate, thanks.

So, I was explaining the binary tree concept to a beginner, and I gave him the formula "2^n - 1". So if the binary tree is full and have a depth of 3, there will be "2^3 - 1 = 7" element in the binary tree.

Then the beginner asked "what if there is not only 2 child (left and rigth) but 3 ? What the formula will be ?" (okay, if each element have 3 child, it's not a binary tree anymore, but bear with me, it's for the sake of the argument).

So a procede to found the formula but failed to do so.

I know that the solution is :

n

Ʃ 3^(x-1)

x = 1

but I can't found the "simplified" version, like

n

Ʃ 2^(x-1)

x = 1

give 2^n - 1

Did the formula exist ? Can we have a general formula with 'C' as the number of child the tree have ?

Sorry for my english, and thanks for reading.

1 Answers

2
collapsar On Best Solutions

The number of nodes C_{m,k} of a complete tree of height k with m-ary fanout is given by the formula

C_{m,k} = (m^(k+1) - 1) / (m-1);

Proof:

Observation: at level i there are precisely m^i nodes in the tree. 'Level' means distance to the root node (consequentially, the root node's level is 0). Therefore,

C_{m,k} = sum_{i=0..k} ( m^i )

The summation is a finite geometric progression ( ie. the quotient between consecutive summation elements is a constant ). The general formula is ...

C_{m,k} = (m^(k+1) - 1) / (m-1);

... which can easily be proven by induction