Please explain this question

#1

The number of nodes in a perfect binary tree of height h which are not leaf nodes are:

2^(2*h) + 1

2^h

2^(h+1) - 1

2^h - 1

#2

@KetanPandey, perfect binary tree is a binary tree in which every node has two children (except leaf node) so its at height x the tree has 2^x nodes , if the height of tree is h then the number of leaf nodes will be 2^h, and number of non leaf nodes will be 2^0+2^1+…2^(h-1)
which is 2^h - 1

#3

Q8. BST- Traversing 13) Postorder traversal of a given binary search tree is: 10, 3, 2, 5, 6, 4, 8, 11, 9, 15, 20, 19, 12, 7 The inorder traversal of the tree would be: Is not unique 7, 4, 2, 3, 6, 5,10, 12, 9, 8, 11, 19, 15, 20 20, 10, 2, 3, 5, 8, 9, 12 , 11 ,15 ,4, 6, 7, 19 2, 3, 4, 5, 6, 7, 8 , 9, 10, 11, 12, 15, 19, 20

#4

Please explain above question.I guess this question is wrong .how can 10 apper at first.If it is correct please explain answer

#5

I also know that ascending order is the right answer.But how can 10 appear at first in postorder traversal.

#6

@KetanPandey, nice observation , yes you are right the first element has to be the least valued node , since the problem only requires sorting , i don’t think problem setter thought of it as much

#7

Please also guide me on last two questions

#8

Q6. Binary Tree as array A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be. 2^(n) - 1 2nn n*n 2^n

#9

Q3. Perfect Binary Tree For a perfect binary tree of height h and n nodes the sum of heights of all the nodes is: O(hh) O(h) O(nn) O(n)

#10

For a right skewed binary tree, number of nodes will be 2^n – 1. For example, in below binary tree, node ‘A’ will be stored at index 1, ‘B’ at index 3, ‘C’ at index 7 and ‘D’ at index 15.

A
 \
  \
    B
      \
        \ 
         C
           \
             \
              D
#11

for q3 refer this discussion : Doubt in mcq question

#12

i didnt understood 3rd one,can you explain with the help of 2-3 examples

#13

@KetanPandey, Since , i have already provided you with a mathematical expression , i will try to explain this logically , this questions requires the observation that , as you go down the tree height will decrease and the number of node will increase which will compensate each other to a fixed value.
eg :-
for 2^(h-1) leaf nodes will have height of 1 and sum will be (2^(h-1)) * 1
root node will have height of h and sum will be 1 * h
here h is the height of tree which is log(n)+1

for a tree with height 3
sum=(2^2)*1+(2^1)*2+(2^0)*3;

for a tree with height 4
sum=(2^3)*1+(2^2)*2+(2^1)*3+(2^0)*4;

notice (height is inversely proportionate to number of nodes for a specific level)

#14

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.