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.