Data Structure Questions and Answers – Binary Trees using Array

«
»

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Binary Trees using Array”.

1. How many children does a binary tree have?
a) 2
b) any number of children
c) 0 or 1 or 2
d) 0 or 1
View Answer

Answer: c
Explanation: Can have atmost 2 nodes.
advertisement

2. What is/are the disadvantages of implementing tree using normal arrays?
a) difficulty in knowing children nodes of a node
b) difficult in finding the parent of a node
c) have to know the maximum number of nodes possible before creation of trees
d) difficult to implement
View Answer

Answer: c
Explanation: The size of array is fixed in normal arrays. We need to know the number of nodes in the tree before array declaration. It is the main disadvantage of using arrays to represent binary trees.

3. What must be the ideal size of array if the height of tree is ‘l’?
a) 2l-1
b) l-1
c) l
d) 2l
View Answer

Answer: a
Explanation: Maximum elements in a tree (complete binary tree in worst case) of height ‘L’ is 2L-1. Hence size of array is taken as 2L-1.
advertisement
advertisement

4. What are the children for node ‘w’ of a complete-binary tree in an array representation?
a) 2w and 2w+1
b) 2+w and 2-w
c) w+1/2 and w/2
d) w-1/2 and w+1/2
View Answer

Answer: a
Explanation: The left child is generally taken as 2*w whereas the right child will be taken as 2*w+1 because root node is present at index 0 in the array and to access every index position in the array.

5. What is the parent for a node ‘w’ of a complete binary tree in an array representation when w is not 0?
a) floor(w-1/2)
b) ceil(w-1/2)
c) w-1/2
d) w/2
View Answer

Answer: a
Explanation: Floor of w-1/2 because we can’t miss a node.
advertisement

6. If the tree is not a complete binary tree then what changes can be made for easy access of children of a node in the array?
a) every node stores data saying which of its children exist in the array
b) no need of any changes continue with 2w and 2w+1, if node is at i
c) keep a seperate table telling children of a node
d) use another array parallel to the array with tree
View Answer

Answer: a
Explanation: Array cannot represent arbitrary shaped trees. It can only be used in case of complete trees. If every node stores data saying that which of its children exists in the array then elements can be accessed easily.

7. What must be the missing logic in place of missing lines for finding sum of nodes of binary tree in alternate levels?

advertisement
  //e.g:-consider -complete binary tree:-height-3, [1,2,3,4,5,6,7]-answer must be 23
  n=power(2,height)-1; //assume input is height and a[i] contains tree elements
  for(i=1;i<=n;)
  {
        //present level is initialized to 1 and sum is initialized to  0
        for(j=1;j<=pow(2,currentlevel-1);j++) 
        {
           sum=sum+a[i];
           i=i+1;
        }
     //missing logic
  }

a)

advertisement
   i=i+pow(2,currentlevel);
   currentlevel=currentlevel+2;
   j=1;

b)

   i=i+pow(2,currentlevel);
   currentlevel=currentlevel+2;
   j=0;

c)

   i=i-pow(2,currentlevel);
   currentlevel=currentlevel+2;
   j=1;

d)

   i=i+pow(2,currentlevel);
   currentlevel=currentlevel+1;
   j=1;
View Answer
Answer: a
Explanation: The i value must skip through all nodes in the next level and current level must be one+next level.
 
 

8. Consider a situation of writing a binary tree into a file with memory storage efficiency in mind, is array representation of tree is good?
a) yes because we are overcoming the need of pointers and so space efficiency
b) yes because array values are indexable
c) No it is not efficient in case of sparse trees and remaning cases it is fine
d) No linked list representation of tree is only fine
View Answer

Answer: c
Explanation: In case of sparse trees (where one node per level in worst cases), the array size (2h)-1 where h is height but only h indexes will be filled and (2h)-1-h nodes will be left unused leading to space wastage.

9. Why is heap implemented using array representations than tree(linked list) representations though both tree representations and heaps have same complexities?

for binary heap
-insert: O(log n)
-delete min: O(log n)
 
for a tree
-insert: O(log n)
-delete: O(log n)

Then why go with array representation when both are having same values ?
a) arrays can store trees which are complete and heaps are not complete
b) lists representation takes more memory hence memory efficiency is less and go with arrays and arrays have better caching
c) lists have better caching
d) In lists insertion and deletion is difficult
View Answer

Answer: b
Explanation: In memory the pointer address for next node may not be adjacent or nearer to each other and also array have wonderful caching power from os and manipulating pointers is a overhead. Heap data structure is always a complete binary tree.

10. Can a tree stored in an array using either one of inorder or post order or pre order traversals be again reformed?
a) Yes just traverse through the array and form the tree
b) No we need one more traversal to form a tree
c) No in case of sparse trees
d) Yes by using both inorder and array elements
View Answer

Answer: b
Explanation: We need any two traversals for tree formation but if some additional stuff or techniques are used while storing a tree in an array then one traversal can facilitate like also storing null values of a node in array.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter