full n-ary tree has m non-leaf nodes.txt

来自「It is an ebook about trees」· 文本 代码 · 共 33 行

 full N-ary tree has M non-leaf nodes, how many leaf nodes does it have? 

Discuss it!          


Use Geometric progression. 


M + (N ^ (n-1)) = (1 - (N ^ n)) / (1 - N) 

Here (N ^ (n-1)) is the number of leaf-nodes. 

Solving for this leads to the answer 

Leaf nodes = M * (N - 1) + 1 



Suppose you have a 3-ary tree 


                A 
      B         C         D 
   E  F  G   H  I  J   K  L  M 



So, here M=4 and N=3. So using the formula above, 


Leaf nodes = M * (N - 1) + 1 = 4 * (3 - 1) + 1 = 9