Placement Assistance Interview Question:

An N-ary tree has N sub-nodes for each node, it has M non-leaf nodes
Find the no of leaf nodes?

Submitted by: Administrator

consider a N-ary tree with depth d

Total no of nodes in the tree, T=1+N+N^2+...+N^d= (1-N^(d+1))/(1-N) --(1)

No. of non leaf nodes, M=(1-N^d)/(1-N) ---(2)

No. of leaf nodes = T-M = N^d ---(3)

from eq (2), d= log(base N) [MN-M+1] ---(4)

Therefore, no of leaf nodes = N^d = MN-M+1
Submitted by: Administrator