Data Structure Questions and Answers-Binary Trees using Array

YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

CLICK HERE TO DOWNLOAD

Data Structure Questions and Answers-Binary Trees using Array

Question 6 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 6 Explanation: 
Array cannot represent arbitrary shaped trees it can only be used in case of complete trees hence option a must be done which is one of several ways to use array in such situations.

Question 7 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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;) { for(j=1;j<=pow(2, currentlevel-1);j++) //present level is initialized to 1 and sum is initialized to 0 { 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;
Question 7 Explanation: 
The i value must skip through all nodes in the next level and current level must be one+next level.

Question 8 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 8 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 which was actually main theme of question.

Question 9 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 by it's property are complete
B
lists representation takes more memory hence memory efficiency is less and go with arrays
C
array have better caching
D
all of the mentioned
Question 9 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.

Question 10 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
None of the mentioned
Question 10 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.

There are 10 questions to complete.