Consider the original array 17, 8, 12, 4, 26. How many comparisons are needed…

2024

Consider the original array 17, 8, 12, 4, 26. How many comparisons are needed to construct the BST on the original array?

  1. A.

    5

  2. B.

    10

  3. C.

    7

  4. D.

    More than one of the above

  5. E.

    None of the above

Attempted by 241 students.

Show answer & explanation

Correct answer: E

To construct a Binary Search Tree (BST) from the array [17, 8, 12, 4, 26], we insert elements sequentially. \\[n=5\\] elements require insertion into the tree, but we count comparisons made during each insertion.\\[n=1\\] First element (17) is the root; 0 comparisons. \\[n=2\\] Insert 8: compare with 17 (left) → 1 comparison. \\[n=3\\] Insert 12: compare with 17 (left), then with 8 (right) → 2 comparisons. \\[n=4\\] Insert 4: compare with 17 (left), then with 8 (left) → 2 comparisons. \\[n=5\\] Insert 26: compare with 17 (right) → 1 comparison. \\[n=Total\\] Total comparisons = 0 + 1 + 2 + 2 + 1 = 6. \\[n=Options\\] Options A (5), B (10), and C (7) are incorrect. Thus, 'None of the above' is correct.

Explore the full course: Up Lt Grade Assistant Teacher 2025