ALLInterview.com :: Home Page            
 Advertise your Business Here     
Browse  |   Placement Papers  |   Company  |   Code Snippets  |   Certifications  |   Visa Questions
Post Question  |   Post Answer  |   My Panel  |   Search  |   Articles  |   Topics  |   ERRORS new
   Refer this Site  Refer This Site to Your Friends  Site Map  Bookmark this Site  Set it as your HomePage  Contact Us     Login  |  Sign Up                      
Google
   
 
Categories >> Software >> Operating Systems >> Data Structures
 
 


 

 
 Windows interview questions  Windows Interview Questions (340)
 Linux interview questions  Linux Interview Questions (451)
 Unix interview questions  Unix Interview Questions (458)
 Solaris interview questions  Solaris Interview Questions (781)
 RTOS interview questions  RTOS Interview Questions (43)
 Bulnex interview questions  Bulnex Interview Questions (4)
 Operating Systems General Concepts interview questions  Operating Systems General Concepts Interview Questions (261)
 Data Structures interview questions  Data Structures Interview Questions (67)
 Operating Systems AllOther interview questions  Operating Systems AllOther Interview Questions (48)
Question
What is the maximum total number of nodes in a tree that has
N levels? Note that the root is level (zero)
 Question Submitted By :: Data-Structures
I also faced this Question!!     Answer Posted By  
 
Answer
# 1
2^(N+1)-1..

if N=0; it is 2-1=1,1 is the max no of node in the tree
if N=1; it is 4-1=3, 3 is the max no of nodes in the tree
if N=2; it is 8-1=7, 7 is the max

and it goes like that...........
 
Is This Answer Correct ?    97 Yes 5 No
Salmiya Thilsath.a
 
Answer
# 2
(2 pow n)-1,if root level is one and (2 pow n+1)-1, if root
level is zero.
 
Is This Answer Correct ?    25 Yes 9 No
Asharani K P
 
 
 
Answer
# 3
(2^(N+1))-1
Suppose level is 2 then total number of nodes will be
1 root
2 left of root and right of root
2 left and right of left of root
2 left and right of right of root
so total nodes are 1+2+2+2=7

by formula (2^(2+1))-1
8-1=7
 
Is This Answer Correct ?    22 Yes 8 No
Gaurav Gupta
 
Answer
# 4
2^(N+1)-1 
Is This Answer Correct ?    19 Yes 6 No
Deba
 
Answer
# 5
2^N -1 
Is This Answer Correct ?    13 Yes 6 No
Gopala Krishnan
 
Answer
# 6
if tree is binary tree then maximum no.of node is 2^(N+1)-1 
Is This Answer Correct ?    5 Yes 0 No
Bipin From Utkal University Mc
 
Answer
# 7
Infinite

In a tree a node can have any number of nodes independent
of the levels.
 
Is This Answer Correct ?    8 Yes 4 No
S. Sadagopan
 
Answer
# 8
to be more generic this kind of problem is best solved
recursivly.

To point out that 2 ^ N AND 3 ^ N are both wrong,
here's a few examples: (the exponet is the amount of levels)
2^0 = 1, correct
2^1 = 2, incorrect, should be 3
2^2 = 4, incorrect, should be 7

And a tree with three children
3^0 = 1, correct
3^1 = 3, incorrect, should be 4
3^2 = 9, incorrect, should be 13

Looking at that I'm sure you can see the pattern.
Let
C = "Number of Possible Children"
N = Levels

N
Σ C^N
j=0

or in C++ code
int NodeCount(int C, int N)
{
if (N < 0) return 0
return NodeCount(C, N-1) + C^N
}
 
Is This Answer Correct ?    7 Yes 4 No
Hex
 
Answer
# 9
If root is at level 0 then :
Case 0:
When level is 1 max nodes is 1
Case 1:
When level is 1 then max would be 3.
Case 2:
When level is 2 then max nodes would be 7

So formula would be 2^(n+1) -1

2^(0+1)-1=1
2^(1+1)-1=3
2^(2+1)-1=7
 
Is This Answer Correct ?    5 Yes 3 No
Vaishali Naidu
 
Answer
# 10
2^N-1

because root is at level 0. and there are n levels only.
so last level i.e level of leaves should be n-1. for maximum
we will consider complete binary tree which is full at level
n-1.

for 0 level -> 2^0 i.e 1 element
for 1 level -> 2^1
...
so on

for n-1 levle ->2^(n-1) nodes
---------------------------
sum = 2^n-1
 
Is This Answer Correct ?    2 Yes 1 No
Mahfooz
 

 
 
 
Other Data Structures Interview Questions
 
  Question Asked @ Answers
 
Evaluate the following prefix expression " ++ 26 + - 1324" Patni 22
Stack can be described as a pointer. Explain. Wipro 5
how to search an element in sorted linked list with time complexity is O(log n). Wipro 3
Write programs for Bubble Sort, Quick sort Cognizent 15
Parenthesis are never needed in prefix or postfix expressions. Why? Microsoft 11
Write the programs for Linked List (Insertion and Deletion) operations Persistent 9
how a polynomial such as 6x^6+4x^3-2x+10 can be represnted by linked list?write an algorithm that reads such an polynomial   1
what is atmost complete binary tree?   6
why do tree always takes o(log n) time? TCS 1
How will inorder, preorder and postorder traversals print the elements of a tree?   11
input function and output function in c language Tcs 2
wt is a datastructure CybAge 8
 
For more Data Structures Interview Questions Click Here 
 
 
 
 
 


   
Copyright Policy  |  Terms of Service  |  Articles  |  Site Map  |  RSS Site Map  |  Contact Us
   
Copyright 2013  ALLInterview.com.  All Rights Reserved.

ALLInterview.com   ::  KalAajKal.com