Engineering Questions with Answers - Multiple Choice Questions

# Binary Tree Sort MCQ’s

1 - Question

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

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

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

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

What is the worst case time complexity of the binary tree sort?
a) O(n)
b) O(nlogn)
c) O(n2)
d) O(logn)

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

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

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

What is the best case time complexity of the binary tree sort?
a) O(n)
b) O(nlogn)
c) O(n2)
d) O(logn)

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

Binary tree sort is an in-place sorting algorithm.
a) True
b) False

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

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 algorithmsAnswer: d
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.

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

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

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

Consider the following statements related to the binary tree sort.