Data Structure Questions and Answers – Threaded Binary Tree

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Threaded Binary Tree”.

1. What are double and single threaded trees?
A) when both left, right nodes are having null pointers and only right node is null pointer respectively
B) having 2 and 1 node
C) using single and double linked lists
D) using heaps and priority queues

Explanation: They are properties of binary trees of double and single threads, respectively.

2. What is wrong with below code for inorder traversal of inorder threaded binary tree:

   inordertraversal(threadedtreenode root):
   threadedtreenode q = inorderpredecessor(root)
   while(q!=root):
   q=inorderpredecessor(q)
   print q.data

A) inordersuccessor instead of inorderpredecessor must be done
B) code is correct
C) it is code for post order
D) it is code for pre order

Explanation: The left node with inorder predecessor information and the right node with inorder successor information are stored in an inorder threaded binary tree.

data-structure-questions-answers-threaded-binary-tree-q8

3. What is inefficient with the below threaded binary tree picture?

A) it has dangling pointers
B) nothing inefficient
C) incorrect threaded tree
D) space is being used more

Explanation: The nodes on the far left and right are pointing to nothing and may be useful.

4. What is a threaded binary tree traversal?
A) a binary tree traversal using stacks
B) a binary tree traversal using queues
C) a binary tree traversal using stacks and queues
D) a binary tree traversal without using stacks and queues

Explanation: Neither a stack nor a queue will be used in this form of tree traversal.

5. What are the disadvantages of normal binary tree traversals?
a) there are many pointers which are null and thus useless
b) there is no traversal which is efficient
c) complexity in implementing
d) improper traversals

Explanation: We use threaded binary trees so the majority of pointers with null values are wasted.

6. In general, the node content in a threaded binary tree is ________
A) leftchild_pointer, left_tag, data, right_tag, rightchild_pointer
B) leftchild_pointer, left_tag
C) leftchild_pointer, left_tag, right_tag, rightchild_pointer
D) leftchild_pointer, left_tag, data

Explanation: Over and above the normal binary tree node structure, it has an extra two pointers.

7. What are null nodes filled with in a threaded binary tree?
A) inorder predecessor for left node and inorder successor for right node information
B) right node with inorder predecessor and left node with inorder successor information
C) they remain null
D) some other values randomly

Explanation: If you use preorder or postorder, the information about your predecessor and successor is saved.

8. Which of the following tree traversals work if the null left pointer pointing to the predecessor and null right pointer pointing to the successor in a binary tree?
A) inorder, postorder, preorder traversals
B) inorder
C) postorder
D) preorder

Explanation: The null left pointer in threaded binary trees points to the ancestor, while the null right pointer points to the successor. To visit every node in a threaded binary tree, we can use in-order, preorder, and postorder traversals.

A threaded binary tree is a binary tree variant in computing that allows traversal in a specific order (often the same order as the tree itself). A threaded tree adds extra information to any or all nodes, making it easier to find the “next” node. Threaded binary trees are designed to make inorder traversal faster while avoiding stack and recursion. Threading a binary tree is accomplished by allowing all right child pointers that would otherwise be NULL point to the node’s inorder successor (if it exists). Threaded binary trees are divided into two groups.

Leave a Reply

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