Data Structure Questions and Answers – Binary Trees using Linked Lists

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

1. Advantages of linked list representation of binary trees over arrays?
a) dynamic size
b) ease of insertion/deletion
c) ease in randomly accessing a node
d) both dynamic size and ease in insertion/deletion
View Answer

Answer: d
Explanation: It has both dynamic size and ease in insertion and deletion as advantages.

2. Disadvantages of linked list representation of binary trees over arrays?
a) Randomly accessing is not possible
b) Extra memory for a pointer is needed with every element in the list
c) Difficulty in deletion
d) Random access is not possible and extra memory with every element
View Answer

Answer: d
Explanation: Random access is not possible with linked lists.Also it includes extra memory space for each element thereby increasing its space complexity.

3. Which of the following traversing algorithm is not used to traverse in a tree?
a) Post order
b) Pre order
c) Post order
d) Randomized
View Answer

Answer: d
Explanation: Generally, all nodes in a tree are visited by using preorder, inorder and postorder traversing algorithms.
advertisement
advertisement

4. Level order traversal of a tree is formed with the help of
a) breadth first search
b) depth first search
c) dijkstra’s algorithm
d) prims algorithm
View Answer

Answer: a
Explanation: Level order is similar to bfs.

5. Identify the reason which doesn’t play a key role to use threaded binary trees?
a) The storage required by stack and queue is more
b) The pointers in most of nodes of a binary tree are NULL
c) It is Difficult to find a successor node
d) They occupy less size
View Answer

Answer: d
Explanation: Threaded binary trees are introduced to make the Inorder traversal faster without using any stack or recursion. Stack and Queue require more space and pointers in the majority of binary trees are null and difficulties are raised while finding successor nodes. Size constraints are not taken on threaded binary trees, but they occupy less space than a stack/queue.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. The following lines talks about deleting a node in a binary tree.(the tree property must not be violated after deletion)
i) from root search for the node to be deleted
ii)
iii) delete the node at
what must be statement ii) and fill up statement iii)
a) ii)-find random node,replace with node to be deleted. iii)- delete the node
b) ii)-find node to be deleted. iii)- delete the node at found location
c) ii)-find deepest node,replace with node to be deleted. iii)- delete a node
d) ii)-find deepest node,replace with node to be deleted. iii)- delete the deepest node
View Answer

Answer: d
Explanation: We just replace a to be deleted node with last leaf node of a tree. this must not be done in case of BST or heaps.

7. What may be the psuedo code for finding the size of a tree?
a) find_size(root_node–>left_node) + 1 + find_size(root_node–>right_node)
b) find_size(root_node–>left_node) + find_size(root_node–>right_node)
c) find_size(root_node–>right_node) – 1
d) find_size(root_node–>left_node + 1
View Answer

Answer: a
Explanation: Draw a tree and analyze the expression. we are always taking size of left subtree and right subtree and adding root value(1) to it and finally printing size.
advertisement

8. What is missing in this logic of finding a path in the tree for a given sum (i.e checking whether there will be a path from roots to leaf nodes with given sum)?

checkSum(struct bin-treenode *root , int sum) :
  if(root==null)
    return sum as 0
  else :
     leftover_sum=sum-root_node-->value
     //missing

a) code for having recursive calls to either only left tree or right trees or to both subtrees depending on their existence
b) code for having recursive calls to either only left tree or right trees
c) code for having recursive calls to either only left tree
d) code for having recursive calls to either only right trees
View Answer

Answer: a
Explanation: if(left subtree and right subtree) then move to both subtrees
else if only left subtree then move to left subtree carrying leftover_sum parameter
else if only right subtree then move to right subtree carrying leftover_sum parameter.
advertisement

9. What must be the missing logic below so as to print mirror of a tree as below as an example?
The swapping of left & right nodes to print mirror of a tree as an example

if(rootnode):
  mirror(rootnode-->left)
  mirror(rootnode-->right)
 
  //missing
 
end

a) swapping of left and right nodes is missing
b) swapping of left with root nodes is missing
c) swapping of right with root nodes is missing
d) nothing is missing
View Answer

Answer: a
Explanation: Mirror is another tree with left and right children of nodes are interchanged as shown in the figure.

10. What is the code below trying to print?

void print(tree *root,tree *node)
{
  if(root ==null) return 0
  if(root-->left==node || root-->right==node) || print(root->left,node)
  ||printf(root->right,node)
  {
     print(root->data)
  }
}

a) just printing all nodes
b) not a valid logic to do any task
c) printing ancestors of a node passed as argument
d) printing nodes from leaf node to a node passed as argument
View Answer

Answer: c
Explanation: We are checking if left or right node is what the argument sent or else if not the case then move to left node or right node and print all nodes while searching for the argument node.

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.