Series: Subject: Topic:
Question: 15 of 30

# An N-ary tree has N sub-nodes for each node, it has M non-leaf nodesFind the no of leaf nodes?

This question is related to Adobe Interview
Asked by: Interview Candidate | Asked on: Apr 22nd, 2006
Showing Answers 1 - 13 of 13 Answers
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.
neelimadahiya

Answered On : Sep 5th, 2006

View all answers by neelimadahiya

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.
sweetbla

Answered On : Mar 17th, 2010

View all answers by sweetbla

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

Login to rate this answer.

### Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

### Interview Question

Ask Interview Question?

### Interview & Career Tips

Get invaluable Interview and Career Tips delivered directly to your inbox. Get your news alert set up today, Once you confirm your Email subscription, you will be able to download Job Inteview Questions Ebook . Please contact me if you there is any issue with the download.