GeekInterview.com
   Home |  Tech FAQ  |   Interview Questions |  Placement Papers |  Tech Articles |  Learn |  Freelance Projects |  Online Testing |  Geeks Talk |  Job Postings |  Knowledge Base | Site Search |  Add/Ask Question

  GeekInterview.com  >  Placement Papers  >  Adobe

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




September 09, 2006 01:05:09 #6
 neelimadahiya   Member Since: September 2006    Total Comments: 1 

RE: An N-ary tree has N sub-nodes for each node, it ha...
 

Well, I have an answer with the explanation:

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

     

 

Back To Question