Data Structure Questions and Answers – Binary Trees using Linked Lists

Uncategorized

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

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

Explanation: We simply substitute a to-be-deleted node with the tree’s last leaf node. In the case of BST or heaps, this must not be achieved.

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

Explanation: Make a tree diagram and examine the expression. We always take the size of the left and right subtrees, add root value(1) to it, and then print the size.

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

Explanation: If (left subtree and right subtree) is true, then move to both subtrees; otherwise, if only the left subtree is true, then move to the left subtree with the leftover sum parameter; otherwise, if only the right subtree is true, then move to the right subtree with the leftover sum parameter.

data-structure-questions-answers-binary-trees-linked-lists-q9

4. What must be the missing logic below so as to print mirror of a tree as below 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

Explanation: As seen in the diagram, a mirror tree is one in which the left and right children of nodes are swapped.

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

Explanation: We’re checking whether the argument sent the left or right node, and if that’s not the case, we’ll switch to the left or right node and print all nodes while looking for the argument node.

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

Explanation: It has the advantages of both dynamic scale and ease of insertion and deletion.

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

Explanation: Random access is not possible with linked lists.

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

Explanation: Preorder, inorder, and postorder traversing algorithms are used to visit all nodes in a tree.

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

Explanation: Level order is similar to bfs.

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

Explanation: Threaded binary trees are used to speed up Inorder traversal by avoiding the use of a stack or recursion. Stack and Queue take up more space, and pointers in the majority of binary trees are null, making finding successor nodes more difficult. Threaded binary trees have no size limits, but they take up less space than a stack or queue.

A binary tree is a type of tree with only two children at each node. A node in a linked list has a previous node and a next node, while a node in a binary tree has a left child, right child, and parent. The term “binary” refers to the fact that each branch can only be connected to a maximum of two other branches. The idea is to use a queue to traverse the partially constructed Binary Tree in Level order while also traversing the linked list. At each point, we remove the parent node from the queue, add the next two linked list nodes as children of the parent node, and return the parent node to the queue.

Leave a Reply

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