vishal singla

• Apr 28th, 2006

 

this is a standard theorm you can search on net(N+1)(M-1)

Bharat Sarda

• May 5th, 2006

 

Correct Answer is :  (n - 1)?m + 1

Divya

• Jun 27th, 2006

 

Hi,

Can anybody tell me what are the questions which are asked in ADOBE written test ?????

ramesh kumar

• Aug 11th, 2006

 

ans:m+1

exp: consider binary tree that having depth x

jeeves

• Aug 19th, 2006

 

N^(logMtobaseN)

neelimadahiya

 Profile Answers by neelimadahiya 

• Sep 5th, 2006

 

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

Nav

• 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

Vishnu Priya

• Sep 21st, 2006

 

it is (M-1)*N

vibhu

• Mar 29th, 2007

 

yes its M*(N-1)+1

abhishek

• 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

Siddharth Wighe

• 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) + 1             which 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.

Null Pointer Theorem The Null Pointer Theorem s

• 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

sweetbla

 Profile Answers by sweetbla 

• Mar 17th, 2010

 

Answer is M(h-1)+1, where h stands for height of the tree.