Binary Tree Sort – Multiple Choice Questions and Answers (MCQs)

Data Structures & Algorithms Computer Science & Engineering

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Binary Tree Sort”.

1. 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: When the BST is balanced, the best case scenario happens. As a result, when the tree is balanced, it takes O(nlogn) time to construct it and O(n) time to traverse it. As a result, the binary tree sort’s best-case time complexity is O. (nlogn).

2. Binary tree sort is an in-place sorting algorithm.
A) True
B) False

Explanation: For each array element, one tree node must be reserved in binary tree sort. For each node, it necessitates the use of two pointer variables. As a result, it necessitates additional memory. Binary tree sort has a worst-case space complexity of (n). As a result, binary tree sort is not a sorting algorithm that can be used in place.

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

Explanation: In the average case, binary tree sort and fast sort take the same amount of time, i.e. O(nlogn) in the average case and O(n2) in the worst case. The binary tree sorting algorithm is not an in-place sorting algorithm.

4. 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 a better looking version of binary tree sort. Rather than generating nodes as in binary tree sort, heap sort creates a heap on the input element by changing the location of the elements within the original array.

5. 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

Explanation: Binary tree sorting is dynamic sorting, which means that as more elements are added, it becomes more effective. As a result, we can progressively add elements as they become functional. Binary tree sort takes up more memory and has a worst-case space complexity of (n).

6. 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: Binary tree sort is a sort algorithm in which the elements to be sorted are built into a binary search tree, and then the BST is traversed in order to get the elements in sorted order.

7. 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: The worst case scenario for the binary tree sort is when the BST built is unbalanced. When the elements are already sorted, BST becomes unbalanced. In the worst-case scenario, it will take O(n2) time to construct the BST and O(n) time to traverse the tree. As a result, in the worst-case scenario, the time complexity is O(n2) + O(n) = O. (n2).

8. 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: The BST is constructed on the input elements, and the tree is traversed in order to get the sorted order in binary tree sort. We fly down the tree until we hit a leaf when constructing the BST. If the new element is less than the node, we travel to the left subtree; if the element is greater or equal to the node, we travel to the right subtree. As a result, newElement node->value is the correct choice.

9. 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.

binary-tree-sort-questions-answers-q1

binary-tree-sort-questions-answers-q1
We move down the tree until we meet a leaf to build the BST. As a result, for each unit, we compare it to the internal nodes until we reach the leaves, and then we compare it to its parent to determine if it is a right or left child. To construct the BST, we must perform 10 comparisons for each array.

A tree sort is a sort algorithm that constructs a binary search tree from the elements to be sorted, then traverses the tree (in-order) to produce sorted results. Its most common use is online sorting of elements: after each insertion, the set of elements seen thus far is available in sorted order. Tree sort can be used as a one-time sort, but it is almost identical to quicksort in that both recursively partition the elements based on a pivot, and since quicksort is in-place and has lower overhead, it has few advantages. If a self-balancing tree is used, it has a lower worst-case complexity but a higher overhead.

Leave a Reply

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