vishal singla
Answered On : Apr 28th, 2006
this is a standard theorm you can search on net(N+1)(M-1)
Login to rate this answer.
Bharat Sarda
Answered On : May 5th, 2006
Correct Answer is : (n - 1)m + 1
1 User has rated as useful.
Login to rate this answer.
Divya
Answered On : Jun 27th, 2006
Hi,
Can anybody tell me what are the questions which are asked in ADOBE written test ?????
Login to rate this answer.
ramesh kumar
Answered On : Aug 11th, 2006
ans:m+1
exp: consider binary tree that having depth x
Login to rate this answer.
jeeves
Answered On : Aug 19th, 2006
N^(logMtobaseN)
Login to rate this answer.
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
Login to rate this answer.
Nav
Answered On : Sep 17th, 2006
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 Community
http://www.orkut.com/Community.aspx?cmm=13552733
Yahoo Group
http://www.yahoogroups.com/group/TheRevolutions
Login to rate this answer.
Vishnu Priya
Answered On : Sep 21st, 2006
it is (M-1)*N
Login to rate this answer.
vibhu
Answered On : Mar 29th, 2007
yes its M*(N-1)+1
Login to rate this answer.
abhishek
Answered On : Apr 18th, 2007
Let total height of N-ary tree == i
According to question leaf nodes exists only at last level , i.e at ith level
so
N^0 + N^1 + ...............+ N^(i-1) = M
on solving this, we get :
N^(i) = M(N-1) + 1
which is equal to total no. of leaf nodes
Login to rate this answer.
Siddharth Wighe
Answered On : Apr 26th, 2007
Most of the answers are correct!
Order of the ary tree: N
Depth of the tree: d (level of root/head=0 )
No. of non-lead nodes: M
No of leaf nodes: N^d
Total no. of non leaf nodes= M = 1 + N + N^2 + ... + N^(d-1) = (1-N^d)/(1-N)
Hence: M = (1-N^d)/(1-N)
=>M(1-N) = 1-N^d
=> 1 - M(1-N) = N^d
=>N^d = M(N-1) + 1which is nothing but the number of leaves :)
Please note that the ans. shouldn't be in terms of 'd'. Since it is not given, the answer should be only in terms of M & N.
Login to rate this answer.
Null Pointer Theorem
The Null Pointer Theorem s
Answered On : Sep 18th, 2007
Null Pointer Theorem
The Null Pointer Theorem states that given a regular n-ary tree, the number of nodes m is related to the number of null pointers p in the following way:
p = (n - 1)×m + 1 Proof
It is obvious that the number of pointers = n×m. Moreover, the fact that each node is pointed to by a pointer in an one-one correspondence except the the root node implies non-null pointers are totally m-1. Hence, by simple arithmetic,
n×m - (m - 1)
= (n - 1)×m + 1
p = (n - 1)×m + 1 Application to the case when n = 2
When n = 2, the tree is called a binary tree. By plugging in n = 2, we find that the number of null pointers and the number of nodes differ only 1! ie.
p = m + 1
Login to rate this answer.
Answer is M(h-1)+1, where h stands for height of the tree.
Login to rate this answer.
