Total Answers and Comments: 12
Last Update: September 18, 2007 Asked by: D Sridhar
No best answer available. Please pick the good answer available or submit your answer.
Sorting Options
Latest First
Oldest First
By Rating
September 05, 2006 01:05:09 #6
neelimadahiya
Member Since: September 2006 Contribution: 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
Is this answer useful? Yes | No
September 17, 2006 00:36:19 #7
Nav
RE: An N-ary tree has N sub-nodes for each node, it ha... Yep, the answer is ((1 - N^(h-1)) / ( 1 - N)) + M
where, N: N-ary tree h: Height of N-ary tree M: No of leaf nodes
Example: Suppose we are having 3-nary tree as shown below:
(h:1) (1)
(h:2) ((2) (3) (4))
(h:3) ((5) (6) (7)) ((8) (9) (10)) ((11) (12) (13)) (h:4) ((14) (15) (16)) ((17)) <-------- M (i.e. 4) Leaf Nodes
Here, N: 3-ary tree h: 4, Height of 3-ary tree M: 4, No of leaf nodes
Now, Apply the formaula:
= ((1 - 3^(4-1)) / ( 1 - 3)) + 4
= 17 Hence Proved.
Solution by:
The Revolutions (Comp Sci RnD) A Orkut's Communityhttp://www.orkut.com/Community.aspx?cmm=13552733 Yahoo Grouphttp://www.yahoogroups.com/group/TheRevolutions
Is this answer useful? Yes | No
Go To Top