Placement Assistance Question:
An N-ary tree has N sub-nodes for each node, it has M non-leaf nodes
Find the no of leaf nodes?
Answer:
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
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
| Previous Question | Next Question |
| Interview procedure for Non-voice tech support: | Adobe India Written Test: |