A set of n keys k1 kn is to be stored in an initially em

A set of n keys: {k1, . . . , kn} is to be stored in an initially empty binary search tree. Which of the following statements is always true?
(A) The resulting binary search tree has the same height, regardless of the order in which the

keys are inserted in the tree.
(B) If ki is the largest key, then in every binary search tree storing the above set of keys, the

right child of the node storing ki is a leaf.
(C) A preorder traversal of the tree visits the keys in increasing order of value.
(D) After inserting the keys, the key stored at the root of the tree is the same regardless of

the order in which the keys are inserted.
(E) None of the above statements is always true.

Solution

Answer (E) None of the above statements is always true.

Explanation :-

A set of n keys: {k1, . . . , kn} is to be stored in an initially empty binary search tree.

1. The resulting binary search tree has the same height, regardless of the order in which the keys are inserted in the tree.----> If we insert 5,10,20,30,40 in order 10, 20, 30, 40, 5 and 20, 10, 5, 30, 40 then height will be different.

2. If ki is the largest key, then in every binary search tree storing the above set of keys, the right child of the node storing ki is a leaf. ---->There will be no right child of largest key.

3. A preorder traversal of the tree visits the keys in increasing order of value.---> If we insert 10, 20, 30, 40, 5 then preorder will be 10,5,20,30,40.

4. After inserting the keys, the key stored at the root of the tree is the same regardless of the order in which the keys are inserted.--->If we insert 5,10,20,30,40 in order 10, 20, 30, 40, 5 and 20, 10, 5, 30, 40 then root will be different(10 and 20).