Doubts related to Quiz on Trees

#1

1)For a perfect binary tree of height h and n nodes the sum of heights of all the nodes is:

O(h*h)

O(h)

O(n*n)

O(n)

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

#2

…

it is O(N) ,proof is same as time complexity of build heap . in heap we are calculating the same thing.

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
#3

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.