Finding the no of leaf nodes

Question

An N-ary tree has N sub-nodes for each node. If the tree has M non-leaf nodes, How to find the no of leaf nodes?

Answer 1

First of all if the root is level 0, then the K-th level of the tree will have N^K nodes. You can start incrementing a counter level by level until you get M nodes. This way you will find how many levels is the tree consisting of. And the number of leaf nodes is the number of nodes on the last level - it is N^lastLevel.

Here is an example: N = 3, M = 4.

First level = 3^0 = 1
Second level = 3^1 = 3
1 + 3 = 4

So we found that the tree has two levels(counting from 0). The answer is 3^2 = 9.

Note: You can find the level number also directly, by noticing that M is a sum of geometric progression: 1 + 3 + 9 + 27 ... = M

Hope it is clear.

Answer 2

Mathematically speaking the nodes increase in the geometric progression.

0th level - 1
1st level - n
2nd level - n ^2
3rd level - n ^ 3
.... mth level - n ^ m

So the total number of nodes at m-1st level is 1 + n + n^2 + .. + n ^ m-1.

Now there is a good formula to calculate 1 + a + a^2 + a^3 + ... + a^m , which is (1 - n^(m+1))/(1-n), lets call this quantity K.

Now what we need is the number of leaf nodes which is n ^ m, and what we have is K. i.e. total number of non-leaf nodes. Doing some mathematical formula adjustment you will find that
n ^ m = K *(n-1) + 1.

e.g. Lets say in 3-ary tree the total number of non-leaf nodes are 40, then using this formula you get the total number of leaf-nodes as 81 which is the right answer.