This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Binary Tree Sort”.
1. Consider the original array 17 8 12 4 26. How many comparisons are needed to construct the BST on the original array?
a) 5
b) 4
c) 7
d) 10
View Answer
Explanation: Original array is 17 8 12 4 26. The BST built on this array is shown in the figure below.
To built the BST, we travel down the tree until a leaf is reached. Therefore, for every element we compare the element with the internal nodes until we the leaves and then once again compare the element with its parent to decide whether it is right child or left child. So, for given array we need to perform 10 comparisons to build the BST.
2. In binary tree sort, we first construct the BST and then we perform _______ traversal to get the sorted order.
a) inorder
b) postorder
c) preorder
d) level order
View Answer
Explanation: In binary tree sort is a sort algorithm where a binary search tree is built from the elements to be sorted, and then we perform inorder traversal on the BST to get the elements in sorted order.
3. What is the worst case time complexity of the binary tree sort?
a) O(n)
b) O(nlogn)
c) O(n2)
d) O(logn)
View Answer
Explanation: For the binary tree sort the worst case when the BST constructed is unbalanced. BST gets unbalanced when the elements are already sorted. So, in the worst case, O(n2) time is required to built the BST and O(n) time to traverse the tree. Therefore, the worst case time complexity is O(n2) + O(n) = O(n2).
4. The insert() procedure, given below, builds the BST on the input elements, which is the first step of the binary tree sort. Choose the correct to fill the condition.
void insert(Tree* node, int newElement) { if(node== NULL) { node = createNewNode(); node-> value = newElement; node -> left = NULL; node -> right = NULL; return; } else if(__________________) { insert(node->left, newElement); } else { insert(node->right, newElement); } }
a) newElement > node->value
b) newElement < node->value
c) newElement == root->value
d) newElement != root->value
View Answer
Explanation: In binary tree sort, the BST is built on the input elements and the tree is traversed in in-order to get the sorted order. While building the BST, we travel down the tree until a leaf is reached. While traveling dawn the tree, we travel on left subtree if the new element is less than the node or to the right if the element is greater or equal to the node. So, correct option is newElement < node->value.
5. What is the best case time complexity of the binary tree sort?
a) O(n)
b) O(nlogn)
c) O(n2)
d) O(logn)
View Answer
Explanation: The best case occurs when the BST is balanced. So, when tree is balanced we require O(nlogn) time to build the tree and O(n) time to traverse the tree. So, the best case time complexity of the binary tree sort is O(nlogn).
6. Binary tree sort is an in-place sorting algorithm.
a) True
b) False
View Answer
Explanation: In binary tree sort it is required to reserve one tree node for each array element. Its implementation requires two pointer variables for each node. So, it requires extra memory. The worst case space complexity of binary tree sort is Θ(n). Therefore, binary tree sort is not an in-place sorting algorithm.
7. Which of the following is false?
a) Binary tree sort and quick sort have same running time
b) Binary tree sort used BST as work area
c) As the number of elements to sort gets larger, binary tree sort gets more and more efficient
d) Both quick sort and binary tree are in place sorting algorithms
View Answer
Explanation: Binary tree sort and quick sort have same running time i.e O(nlogn)
in average case and O(n2) in worst case. Binary tree is not in-place sorting algorithm.
8. Which of the following sorting algorithms can be considered as improvement to the binary tree sort?
a) Heap sort
b) Quick sort
c) Selection sort
d) Insertion sort
View Answer
Explanation: Heap sort is basically improvement to the binary tree sort. Heap sort builds a heap on the input element by adjusting the position of the elements within the original array, rather than creating nodes as in binary tree sort.
9. Consider the following statements related to the binary tree sort.
I. Element can be added gradually as they become available
II. It needs extra memory space
a) Statement I is true but Statement II is false
b) Both Statement I and Statement II are false
c) Both Statement I and Statement II are true
d) Statement II is true but Statement I is false
View Answer
Explanation: Binary tree sort is dynamic sorting, that is it gets more efficient as more the elements are added. So, we can add elements gradually as they become available. Binary tree sort requires extra memory space, its worst case space complexity is Θ(n).
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, 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]
- Check Design and Analysis of Algorithms Books
- Apply for Computer Science Internship
- Practice Data Structure MCQ
- Practice Programming MCQs
- Practice Computer Science MCQs
