What is the maximum total number of nodes in a tree that has
N levels? Note that the root is level (zero)
Answers were Sorted based on User's Feedback
Answer / salmiya thilsath.a
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 ? | 124 Yes | 8 No |
Answer / asharani k p
(2 pow n)-1,if root level is one and (2 pow n+1)-1, if root
level is zero.
Is This Answer Correct ? | 26 Yes | 11 No |
Answer / gaurav gupta
(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 ? | 24 Yes | 10 No |
Answer / bipin from utkal university mc
if tree is binary tree then maximum no.of node is 2^(N+1)-1
Is This Answer Correct ? | 5 Yes | 0 No |
Answer / hex
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 ? | 8 Yes | 4 No |
Answer / vaishali naidu
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 ? | 6 Yes | 3 No |
Answer / s. sadagopan
Infinite
In a tree a node can have any number of nodes independent
of the levels.
Is This Answer Correct ? | 8 Yes | 6 No |
Can you sort a string?
What do u mean by array?
What is difference between rb tree and avl tree?
Which is faster hashmap or treemap?
Differentiate between iterable and iterator.
An array having 100 elements have numbers from 1 to 99 randomly out of which any number is repeated. Find the repeated number in minimum time and space complexity.
Does hashmap allow duplicate keys?
Differentiate between hashset and hashmap.
What is precision in data structures?
What is the Insertion Sort Code?.
Calculate the efficiency of sequential search?
Is merge sort better than quick?