Data Structure Questions and Answers – Binary Trees using Array

Uncategorized

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

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

Explanation: Trees of any form cannot be represented by an array. It can only be used in cases where there are no gaps in the tree. If each node stores information about which of its children is present in the list, elements can be easily accessed.

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

  //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)

   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;


Explanation: The current level must be one+next level, and the I value must skip over all nodes in the next level.

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

Explanation: In the case of sparse trees (one node per level in worst-case scenarios), the array size is (2h)-1, where h is the height, but only h indexes are filled, leaving (2h)-1-h nodes unused, resulting in wasted room.

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

Explanation: The pointer address for the next node in memory might not be adjacent or close to each other, and arrays have fantastic caching power from the operating system, so manipulating pointers is a waste of time. A complete binary tree is often the data structure of a heap.

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

Explanation: For tree forming, we need two traversals, but if any extra stuff or techniques are used when storing a tree in an array, one traversal will help, such as storing null values of nodes in an array.

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

Explanation: Can have atmost 2 nodes.

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

Explanation: In normal arrays, the array size is set. Before declaring an array, we need to know how many nodes there are in the tree. The biggest drawback of using arrays to represent binary trees is this.

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

Explanation: The maximum number of elements in a tree of height ‘L’ (in the worst case, a complete binary tree) is 2L-1. As a result, the array size is 2L-1.

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

Explanation: Since the root node is at index 0 in the array and to access any index location in the array, the left child is usually 2w, while the right child is 2w+1.

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

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

The tree elements are stored in an array in the sequential representation. The size of the array used is determined by the number of nodes in a binary tree. The array’s first index is the root node of the binary tree. We can easily insert the left and right nodes by selecting their parent node using this principle. We’ll start by inserting the first element in the array as the root node at level 0 in the tree and then traversing the array, inserting all child nodes left and right in the tree for each node i.

Leave a Reply

Your email address will not be published. Required fields are marked *