# Binary Tree Sort Multiple choice Questions and Answers (MCQs)

## Click on any option to know the CORRECT ANSWERS

 Question 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

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

 Question 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

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

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

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

 Question 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

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

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