An algorithm to calculate total last level nodes in a complete X-children tree, without recursive addition, from total number of nodes provided. Each non-leaf node of the tree must have a common number of children, greater than one.
The total number of last level nodes can be given the following expression
H - 1
X - 1
Leaf Nodes = N - ----------
X - 1
where, N is the total number of nodes
X is the number of non-zero child a node can have
H is the height of the tree, starting from index 1
[X^(H-1) - 1]/[X - 1] is the total number of nodes, except the nodes at last level
We know that
__ n - 1 r
\ X
/__ r = 0
is equal to the number of nodes in completely filled X-child tree up to n-1 level.
We can prove that
n
__ n - 1 r X - 1
\ X = -------
/__ r = 0 X - 1
using the principle of mathematical induction.
Subtracting this value from the total number of nodes (N) will give the number of nodes present in the last level.