recategorized by
1 flag 101,259 views
1 votes
1 votes

Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i of a binary tree is 

In the following answers, the operator '^' indicates power

a) 2^i-1
b)2^i
c)2^i+1
d)2^(i+1/2)
  • 🚩 Edit necessary | 👮 Zemansky | 💬 “instead of "the number of node on the level i" of , according to the accepted answer, it should be maximul number of nodes in the tree having i levels”
recategorized by
1 flag

7 Answers

2 votes
2 votes
Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i of a binary tree is :

if level is 3 then there will be maximum 7 nodes in the binary tree. which is 2^3-1=8-1=7. hence the answer is (A).
0 votes
0 votes
A should be ans 2^(k-1)..as level start from 1...had been case where level start from 0 ,2^k
0 votes
0 votes

if we have no level then number of nodes is 0.

To get maximum nodes for each internal node(node which has child) we must add two children nodes.

 

Method 1

substitute values of levels and check which option matches for corresponding number of nodes this is fast and easy.

checking option (A) 2$^i$-1

substitute i=1 we get 2$^1$-1 = 2 - 1 =1 

substitute i=2 we get 2$^2$-1 = 4 - 1 =3

substitute i=3 we get 2$^3$-1 = 8 - 1 =7

so option (A) is correct.

Method 2

If u see above table after increasing every level we double the nodes of previous level and add 1

i.e. if N(i) is the nodes at i$^t$$^h$ level then it can written as 

N(i) = 2N(i-1)+1

where N(i-1) is total nodes till level i-1

also N(0)=0 i.e. if there is no level in tree then there is no tree therefore no node

solving this recurrence by back substitution

N(i-1) = 2N(i-2) + 1

N(i-2) = 2N(i-3) + 1

now back substituting

N(i) = 2[2N(n-2)+1]+1

N(i) = 2$^2$N(n-2)+2+1

.

.

.

going to i$^t$$^h$ level in similar way we get

N(i) = 2$^i$N(i-i)+2$^i$$^-$$^1$+2$^i$$^-$$^2$+....+2+1

N(i) =  2$^i$N(0)+2$^i$$^-$$^1$+2$^i$$^-$$^2$+....+2+1

N(i) =  2$^i$*0+2$^i$$^-$$^1$+2$^i$$^-$$^2$+....+2+1

N(i) =  2$^i$$^-$$^1$+2$^i$$^-$$^2$+....+2+1

this is a G.P whose sum is 

1(2$^i$$^-$$^1$$^+$$^1$ - 1 )/2-1                             formula for GP

=2$^i$-1

so answer is option (A)

 

edited by

Related questions

0 votes
0 votes
5 answers
1
radha gogia asked Sep 30, 2015
1,607 views
If I am given an array $X$ of $n$ distinct integers which is interpreted as a complete binary tree, so if the parent is at index $i$, then it's left child would be at ind...
0 votes
0 votes
2 answers
2
sripo asked Dec 25, 2018
4,682 views
In a 3-array tree if internal nodes have exactly 3 children,the number of leaf nodes will be __ ?Does it vary for binary tree?What do you mean by internal nodes? Non roo...
2 votes
2 votes
1 answer
3
vijaycs asked May 25, 2016
12,731 views
4 votes
4 votes
1 answer
4
Shashank Chavan asked Jan 18, 2016
11,130 views
What's the difference between Binary tree height, level and depth? Sometimes it's confusing!Does there definition change according to question also, if mentioned?