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

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

 Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What is the best case time complexity of the binary tree sort?
 A O(n) B O(nlogn) C O(n2) D O(logn)
Question 5 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).

There are 5 questions to complete.